我写了一个迷宫求解程序,它应该支持 DFS、BFS、A*、Dijkstra 和贪心算法。无论如何,我选择 PriorityQueue 作为我的前沿数据结构,因为我认为优先级可以表现得像队列、堆栈或优先级队列,这取决于比较器的实现。
这就是我实现比较器以将优先级队列转换为队列的方式:
/由于优先级队列的“自然排序”在头部具有最少元素,并且传统比较器在第一个小于第二个时返回 -1,因此被破解的比较器总是返回 1,因此当前(最后一个)方格将是放在尾部(这应该递归地工作) /
public int compare(Square square1, Square square2)
{
return 1;
}
然而,在我进行 BFS 之后,我的迷宫解决方案并不是最优的。
迷宫从坐标(35,1)的右上角开始,我的程序检查左边,然后向上,然后向下,然后是右边的邻居。这是我做的println:
轮询 (35,1)
添加 (34,1)
添加 (35,2)
轮询 (34,1)
添加 (33,1)
添加 (34,2)
轮询 (35,2)
添加 (35,3)
轮询 (33,1)
添加 (32,1)
添加 (33,2)
轮询 (34,2)
添加 (34,3)
投票 (32,1)
……
注意 BFS (35,3) 应在 (32,1) 之前轮询,因为前者在后者之前添加到队列中。真正让我感到困惑的是,数据结构的行为就像一个队列——所有新成员都是从后面添加的——直到我添加了 (32,1),它被放置在队列的头部。
我认为我的比较器应该强制优先级队列将新来者放在后面。更让我感到陌生的是,数据结构的性质从队列变成了中间的堆栈。
非常感谢你们,并为我糟糕的英语感到抱歉,真诚的,肖恩