`A*`从fronti删除节点

Question

这是我写的一个A*算法，在评估中，我被告知“当一个继承者被添加到边界时，您的实现执行目标测试，而不是当它被删除时：这会损害优化”。什么意思是“当它被移除的时候就不需要了”？在

我的代码是：

def solve(problem, heuristic) :
    """ 
    A* search algorithm finding the shortest path.

    Returns:
        A list of actions.
    """
    s0 = problem.get_initial_state()
    queue = PriorityQueue()
    queue.push((0,s0,[]),0)  # second 0 is priority
    cost_so_far = dict()
    cost_so_far[s0] = 0

    while not queue.is_empty():
        current_cost, s, actions = queue.pop()
        for successor, action, cost in problem.get_successors(s):
            new_cost = current_cost + cost
            if problem.goal_test(successor):
                return actions + [action]
            else:
                h = heuristic(successor, problem)
                if successor not in cost_so_far or cost_so_far[successor] > new_cost + h:
                    cost_so_far[successor] = new_cost + h
                    queue.push((new_cost, successor, actions + [action]), new_cost + h)

修改版本（更新）

^{pr2}$

Answer 1

假设您的图表如下所示：

    9
S   - G
 \     /
 1\   /1
   \ /
    W

您需要从起始节点S到目标节点G，路径尽可能便宜。S-G边的代价为9，而连接到分段点W的每条边的代价是2。

您的算法将通过S的邻居来向边界添加节点，找到G，并立即返回昂贵的直接S-G路径，而不必找到通过路径W的路径。

相反，当您pop来自优先级队列的节点时，需要对该节点执行目标测试。在这一点上，可以保证您已经找到了到节点的最便宜的路径，而不仅仅是一些到节点的路径。

Answer 2

在你引用之前的维基百科：“上面的伪代码假设启发式函数是单调的”。

你的代码会在这个图表和启发式中给出错误的答案（字母是节点，数字是成本）：

Get from X to Z: 

  1   2
X - Y - Z
1 \ W / 3 

h(X) = 2, h(Y) = 2, h(W) = 1, h(Z) = 0

节点将按X, W, Z, Y, Z的顺序展开。但是，您的程序将在第一次找到Z后退出，并报告路径X>W>Z，其成本为4，这不是最佳的。