0

我正在图上实现 BFS，其中节点由 State 类的对象标记（我已经实现了隐式等于方法进行比较）。

我已经使用带有返回 1 的比较器的 PriorityQueue 实现了我的队列，因为我想扩展程序以处理 DFS、Astar 等，我可以通过更改比较器内部的逻辑来实现

以下是相关代码：

//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

在遍历列表并打印存在的元素时，我发现某些元素不会向上移动（例如，poll 上的 {a,b,c,d,e} 在 poll( ) 而不是 {b,c,d,e})，因此它不执行 FIFO。

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

1) 我的比较器有问题吗？

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

编辑：我想让它更清楚一点。我正在尝试实现一个集合，无论 DFS 或 BFS（FIFO 或 LIFO）或其他基于优先级的算法（如 A-Star 和 Beam 搜索）如何，我都可以使用常见的 add(State) 或 State x = remove() 扔东西.

我可能会扩展集合并实现 add 和其他方法。

4

1 回答 1

1 
public int compare(State x, State y)

此方法返回正值表示 x > y，负值表示 x < y，0 表示 x==y。

我认为你应该使用 Queue 来声明 frontierList

当你需要 DFS 时，使用 LinkedList<State>

当你需要 BFS 时，使用 PriorityQueue<State> 和 Comparator<State> 返回你想要的最小或最大状态

于 2013-02-23T08:51:21.147 回答