如果两个节点的权重相等，则哪个节点在优先级队列中首先弹出

Question

我正在使用这个 GraphSearch psuedo-code 算法来找到从起始位置到目标的最短路径：

function GRAPH-SEARCH(problem,fringe,strategy) return a solution, or failure
   closed <-- an empty set
   fringe <-- INSERT(MAKE-NODE(INITIAL-STATE[problem]),fringe)
   loop do
      if fringe is empty then return failure
      node <-- REMOVE-FRONT(fringe,strategy)
      if STATE[node] is not in closed then
         add STATE[node] to closed
         for child-node in EXPAND(STATE[node],problem) do
            fringe <-- INSERT(child-node,fringe)
         end
   end

我正在实施 A* 从起始位置寻找目标的策略。 A* 搜索使用公式：

f(n) = g(n) + h(n)

其中 g(n) 是达到当前 child-node 的成本，h(n) 是达到目标的启发式值（我们假设启发式确定 是admissable)，而 f(n) 是我们在 fringe.

中分配给 node 的组合值

在A*搜索中，一个PriorityQueue用于确定哪个child-node到pop()接下来测试目标状态and/or扩展到更多children，在本例中是具有最低值的 child-node。

这是我的问题：

我的电流PriorityQueue如下：

     S -> B = 1 + 3 = 4  // The cost to B + the heuristic value to goal
     S -> A = 1 + 3 = 4  // The cost to A + the heuristic value to goal
          S = 0 + 0 = 0  // Has been popped & expanded

其中S为起始位置，A和B为child个节点。有两条路径分配了下一个最低值 4，那么下一个 PriorityQueue pop() 是哪条路径？

Answer 1

我了解到，根据 PriorityQueue 的性质，如果下一项的优先级值相等，则该结构将被简单地视为 Queue。

在这种情况下，这意味着由于 S -> A = 1 + 3 = 4 是第一个进来的，所以它将是第一个出去的。

Answer 2

进口java.util.PriorityQueue； class你好世界{

static class pair implements Comparable<pair>
{
    int ver;
    int wt;
    
    
    pair(int i, int j)
    {
        this.ver = i ;
        this.wt = j;
      
    }
    
    public int compareTo(pair p)
    {
        return this.wt - p.wt;
    }
    
}
public static void main(String[] args) {
    PriorityQueue<pair> pq = new PriorityQueue<pair>();

    pq.offer(new pair(0,2));
    pq.offer(new pair(1,4));
    pq.offer(new pair(2,2));
    
    pair p = pq.poll();
    System.out.println("this pop" + p.ver);

}

}

输出* 这个 pop0

如果两个节点的权重相等，则哪个节点在优先级队列中首先弹出

Which Node Is Popped First in Priority Queue if Two Are Equal Weight

python

search

stack

priority-queue

nodes