java.util.PriorityQueue的元素在poll上不会向上移动

我在一个图上实现了一个BFS，其中节点由一个State类的对象标记（我实现了一个用于比较的隐式equals方法）。java.util.PriorityQueue的元素在poll上不会向上移动

我已经实现了用一个PriorityQueue用，因为我想扩展程序来处理DFS，爱仕达等，我可以通过只改变比较

这里是内部的逻辑做返回1，比较我的队列相关代码：

//BFSComparator.java

import java.util.Comparator; 

public class BFSComparator implements Comparator<State>{ 
    @Override public int compare(State x, State y) { 
     return 1; 
    } 
}

//solver.java

Comparator comparator = new BFSComparator(); 
PriorityQueue<State> frontierList = new PriorityQueue<State>(500,comparator); //List of nodes to be expanded 
frontierList.add(seed state0); 
while (!frontierList.isEmpty()){ 
     curState = frontierList.poll(); 
     //handle, expand and add child states to frontierList

虽然遍历列表并打印出现元素，但我发现某些元素不会向上移动（例如，{a，b，c，d，e}）上的轮询变为{b，e，c，d}在poll（）而不是{b，c，d，e}），因此它不执行FIFO。

for(State x:frontierList) { 
      //print x 
}

1）我的比较器有什么问题吗？

2）有没有更好的方法来做到这一般？也就是说，比改变排序逻辑时我可以添加到的优先级队列更好的容器，而不是使用具有不同调用名称（如push和pop）的队列和堆栈？当我稍后根据启发式对它们进行排序时，这会很有帮助。或者我应该只使用链接列表并执行基于插入排序的方法？

编辑：我想使它更清楚一点。我试图实现一个集合，我可以使用普通的add（State）或State x = remove（）抛出东西，而不考虑DFS或BFS（FIFO或LIFO）或其他基于优先级的算法，如A-Star和Beam Search 。

我可能会扩展收集和实现添加和其他方法。

来源

2013-02-23 orderof1

Erm ...你有一个比较器返回...'1'。你为什么期望它能对任何东西进行排序？ – 2013-02-23 06:31:52

由于1总是表示更大，-1表示更小，所以我使用-1作为DFS，1使用BFS – orderof1 2013-02-23 06:33:32

哦，我的。我想你正在寻找[链表]（http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html）。 – Perception 2013-02-23 06:39:23

public int compare(State x, State y)

此方法返回一个正值表示X> Y，一个负值意味着X < y和0表示X ==收率

我thouht你应该使用队列来声明frontierList代替

当你需要DFS，使用LinkedList的<国家>

当你需要BFS，使用的PriorityQueue <国家>和比较<国家>返回分钟或最大状态你想

来源

2013-02-23 08:51:21 kdlan

java.util.PriorityQueue的元素在poll上不会向上移动

回答

相关问题