algorithm - A*搜索邻居处理说明

Question

我正在学习 A* 搜索算法的工作原理。我找到了几个关于这个算法的描述，在我看来它们都有点不同。也就是说，它们在 for 循环中处理邻居节点的方式不同。我想它们都是等价的，但我不明白为什么。如果你是，谁能解释为什么它们是等价的？

来自 Wikipedia article :

 function A*(start,goal)
     closedset := the empty set    // The set of nodes already evaluated.
     openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
     came_from := the empty map    // The map of navigated nodes.

     g_score[start] := 0    // Cost from start along best known path.
     // Estimated total cost from start to goal through y.
     f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

     while openset is not empty
         current := the node in openset having the lowest f_score[] value
         if current = goal
             return reconstruct_path(came_from, goal)

         remove current from openset
         add current to closedset
         for each neighbor in neighbor_nodes(current)
             tentative_g_score := g_score[current] + dist_between(current,neighbor)
             if neighbor in closedset and tentative_g_score >= g_score[neighbor]
                     continue

             if neighbor not in closedset or tentative_g_score < g_score[neighbor] 
                 came_from[neighbor] := current
                 g_score[neighbor] := tentative_g_score
                 f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                 if neighbor not in openset
                     add neighbor to openset

     return failure

 function reconstruct_path(came_from, current_node)
     if current_node in came_from
         p := reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node

来自 Amit’s A* Pages :

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): **
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers

另一个A* pseudocode :

1    Create a node containing the goal state node_goal
2    Create a node containing the start state node_start
3    Put node_start on the open list
4    while the OPEN list is not empty
5    {
6    Get the node off the open list with the lowest f and call it node_current
7    if node_current is the same state as node_goal we have found the solution; break from the while loop
8        Generate each state node_successor that can come after node_current
9        for each node_successor of node_current
10       {
11           Set the cost of node_successor to be the cost of node_current plus the cost to get to node_successor from node_current
12           find node_successor on the OPEN list
13           if node_successor is on the OPEN list but the existing one is as good or better then discard this successor and continue
14           if node_successor is on the CLOSED list but the existing one is as good or better then discard this successor and continue
15           Remove occurences of node_successor from OPEN and CLOSED
16           Set the parent of node_successor to node_current
17           Set h to be the estimated distance to node_goal (Using the heuristic function)
18            Add node_successor to the OPEN list
19       }
20       Add node_current to the CLOSED list
21   }

我知道在一致(单调)启发式 A* 算法的情况下可以简化，但我对启发式不一定一致的一般情况感兴趣。

Answer 1

我建议先看Pieter Abbeel的讲座.它来自加州大学伯克利分校 2012 年秋季的 AI 入门类(class)。

Lecture 3: Informed Search (A*)

这应该让您对 A* 的工作原理有一个很好的了解，他提供了很多很好的例子。为了更深入，我建议学习标题为“知情(启发式)搜索策略”的第 3 章第 3.5 节 Artificial Intelligence: A Modern Approach .这是一本相当大的书，但它非常简洁。特别是，它具有您需要的伪代码。正在浏览，我遇到了

“[A*] 算法与 Uniform-Cost-Search 相同，只是 A* 使用 g + h 而不是 g”

... 其中 g 是到达节点的成本，h 是从该节点到达目标的成本。

这是本书为 UCS 提供的伪代码:

function UCS(problem) return a solution, or failure
    
    node ← a node with STATE = problem.INITIAL-STATE, PATH-COST=0
    frontier ← a priority queue ordered by PATH-COST, with node as the only element
    explored ← an empty set

    loop do
        if EMPTY?(frontier) then return failure
        node ← POP(frontier)
        if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
        add node.STATE to explored

        for each action in problem.ACTIONS(node.STATE) do
            child ← CHILD-NODE(problem, node, action)
            if child.STATE ins not in explored or frontier then 
                frontier ← INSERT(child, frontier)
            else if child.STATE is in frontier with higher PATH-COST then
                replace that frontier node with child

要将其变为 A*，您需要做的就是更改边界的实现，以便优先级队列按 PATH-COST + HEURISTIC-VALUE 排序。

您可能需要阅读本书以更好地理解伪代码。