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以下讲座。这是加州大学伯克利分校介绍到AI当然，在2012年秋季

Lecture 3: Informed Search (A*)

这应该给你如何A *作品良好的手感，他给很多很好的例子。为了更深入地研究，我建议学习第3章第3.5节题为“知情（启发式）搜索策略”的Artificial Intelligence: A Modern Approach。这本书非常庞大，但非常简洁。特别是，它具有您需要的伪代码。现在浏览它，我横跨

来到

“[A *]算法是相同的Uniform-Cost-Search除了A *使用克+ H而不是克”

...其中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。

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