0

给定一个 N 个整数的未排序数组和一个函数getNextIndexOf (int k)，它返回值为 'k' 的下一个元素的索引，如何以最少的调用次数到达最后一个元素（即索引 N）到getNextIndexOf (int k) ？

*换句话说，使用什么值 k 1 , k 2 , ... , k m应该调用 getNextIndexOf(int k) 以便第m次调用返回“N”，并且m尽可能小？

**编辑：您可以假设getNextIndexOf可以跟踪它返回的最后一个索引
（例如，就像 C 中的静态局部变量）。第一次调用它只返回第一个元素的索引等于它的参数（int k）。

4

2 回答 2

1

由于数组是完全随机且未排序的，因此没有先验理由选择任何特定数字。所以你不能更喜欢一个数字。

我会尝试分支和绑定方法。见这里。在要选择的下一个整数上进行分支 k 并限制已采取的步数。将所有分支保留在优先级队列中，并始终扩展队列的头部。

这保证找到最优解。

编辑：

这是一些伪代码：

Let A be the set of all integers that occur in the array.
Let Q be the priority queue

foreach integer k in A do
  Add result of getNextIndexOf(k) to Q

while(Q is not empty && end of array not reached)
  q = head(Q)
  Dequeue(q)

  foreach(integer k in A do)
    Add result of getNextIndexOf(k) to Q (using q)
于 2011-05-20T07:19:51.803 回答
0

一个可能的解决方案（用Java编写！）：

public static List<Integer> getShortest(int[] array) 
{
   int[] nextChoice = new int[array.length];
   HashMap<Integer,Integer> readable = new HashMap<Integer,Integer>();

   readable.put(Integer(array[array.length-1]), Integer(array.length-1));
   for(int i = array.length-1; i>=0; i--)
   {
      for(Map.Entry<Integer,Integer> entry: readable.entrySet())
      {
         if(entry.getValue().intValue() > nextChoice[i])
            nextChoice[i] = entry.getKey();
      }
      readable.put(Integer(array[i]),i);
   }

   List<Integer> shortestList = new LinkedList<Integer>(array.length);
   for(int i = 0; i < array.length; i++)
      shortestList.add(nextChoice[i]);

   return shortestList;
}
于 2011-05-29T05:25:56.447 回答