`A*` 从边界移除一个节点

Question

这是我写的一个A*算法，在评价的时候被告知"Your implementation performs the goal test when a successor is added to the frontier, not when it's removed: this compromises optimality"。 "not when it's removed" 是什么意思？

这是我的代码：

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)

修改版本（更新）

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((s0,[]),0)  # 0 is the priority
    cost_so_far = {s0:0}

    while not queue.is_empty():
        s, actions = queue.pop()

        if problem.goal_test(s):
                return actions

        for successor, action, cost in problem.get_successors(s):
            successor_cost = current_cost + cost
            new_cost = successor_cost + heuristic(successor, problem)

            if successor not in cost_so_far or cost_so_far[successor] > new_cost:
                    cost_so_far[successor] = new_cost
                    queue.push((successor, actions + [action]), new_cost)

Answer 1

来自维基百科，就在您引用之前："the above pseudocode assumes that the heuristic function is monotonic"。

您的代码将在此图和启发式上给出错误答案（字母是节点，数字是成本）：

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 后退出，并会报告成本为 4 的路径 X>W>Z，这不是最优的。

Answer 2

假设您的图表如下所示：

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

您需要沿着最便宜的路径从起始节点 S 到达目标节点 G。 S-G 边的成本为 9，而连接到航路点 W 的边每条成本为 2.

您的算法将查看 S 的邻居以将节点添加到边界，立即找到 G 和 return 昂贵的直接 S-G 路径，而不会找到通过航点 W.

的路径

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

`A*` 从边界移除一个节点

`A*` removing a node from frontier

python

algorithm

a-star