algorithm - A* 検索ネイバーの取り扱い説明

Question

A* 検索アルゴリズムの仕組みを学んでいます。このアルゴリズムの説明をいくつか見つけましたが、それらはすべて少し異なっているように思えます。つまり、for ループでの隣接ノードの処理方法が異なります。はすべて同等だと思いますが、理由がわかりません。あなたの場合、なぜそれらが同等であるかを誰かが説明できますか?

ウィキペディアの記事から：

 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 の A* ページから:

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* 疑似コード:

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年秋のUC BerkeleyイントロからAIコースまでです。

講義 3: インフォームド サーチ (A*)

これにより、A* がどのように機能するかがよくわかるはずです。また、彼は多くの良い例を示しています。さらに深く掘り下げるには、「 Artificial Intelligence: A Modern Approach」の「Informed (Heuristic) Search Strategies」というタイトルの第 3 章セクション 3.5 を学習することをお勧めします。かなり分厚い本ですが、とても簡潔です。特に、必要な疑似コードが含まれています。今ブラウジングしたら出てきた

" [A*] アルゴリズムは、A* が g の代わりに g + h を使用することを除いて、Uniform-Cost-Searchと同じです"

... ここで、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ます。

疑似コードをよりよく理解するには、本を読む必要があるかもしれません。