需要 Java 优先级队列帮助

Question

我正在处理一个旅行推销员问题，我的 p-queue 没有运行，它只是取了最后添加的项目。我想知道是否有人可以帮助我找出错误。这是我的节点类(添加到队列中的节点):

import java.util.*; 

public class Node implements Comparable< Node >{

    //level of node
    int level;
    //stores path of node
    ArrayList< Integer > path = new ArrayList< Integer >();
    //bound of node
    int bound;

    /** Over-rides compareTo for priority queue handling
       * @return int desired sorting value
       */
    public int compareTo(Node aNode) 
    {               
      if (this.bound<aNode.bound)
      {
          return 1;
      }
      if (this.bound>aNode.bound)
      {
          return -1;
      }
      else
      {
          return 0;
      }
    }
}

这里是 p-queue 的实现:

PriorityQueue< Node > theQ = new PriorityQueue< Node >();

算法正确实现 p 队列只是没有将最低边界作为头部。我什至反转了 compareTo 的返回值，对 p-queue 输出没有影响(对我来说，队列没有排序。我浪费了几个小时试图弄清楚，还问了一些同学(没有人能辨别问题)在这里拍一张照片，看看是否有人知道为什么队列会这样..

Answer 1

您的代码对我来说工作得很好。

我怀疑你正在做的是改变单个对象的 bound 值并重复添加它，给你一个充满相同对象的队列(很多对它的引用) course 具有您设置的单个(最后一个)值。

public static void main(String[] args)
{
    PriorityQueue< Node > theQ = new PriorityQueue< Node >();
    Node n = new Node();
    n.bound = 6;
    theQ.add(n);
    n = new Node();
    n.bound = 9;
    theQ.add(n);
    n = new Node();
    n.bound = 4;
    theQ.add(n);
    while ((n = theQ.poll()) != null)
        System.out.println("Bound = " + n.bound);
}

输出:

Bound = 9
Bound = 6
Bound = 4