
_START_ARTICLE_
A*搜尋演算法
_START_SECTION_
伪代码
_START_PARAGRAPH_
//Matlab語言 function A*(start,goal)     closedset := the empty set                 //已经被估算的節點集合openset := set containing the initial node //將要被估算的節點集合，初始只包含start_NEWLINE_     came_from := empty map_NEWLINE_     g_score[start] := 0                        //g(n)_NEWLINE_     h_score[start] := heuristic_estimate_of_distance(start, goal)    //通過估計函數 估計h(start)_NEWLINE_     f_score[start] := h_score[start]            //f(n)=h(n)+g(n)，由於g(n)=0，所以省略while openset is not empty                 //當將被估算的節點存在時，執行循環x := the node in openset having the lowest f_score[] value   //在將被估計的集合中找到f(x)最小的節點if x = goal            //若x為終點，執行_NEWLINE_             return reconstruct_path(came_from,goal)   //返回到x的最佳路徑_NEWLINE_         remove x from openset      //將x節點從將被估算的節點中刪除_NEWLINE_         add x to closedset      //將x節點插入已經被估算的節點_NEWLINE_         for each y in neighbor_nodes(x)  //循環遍歷與x相鄰節點_NEWLINE_             if y in closedset           //若y已被估值，跳過continue_NEWLINE_             tentative_g_score := g_score[x] + dist_between(x,y)    //從起點到節點y的距離_NEWLINE__NEWLINE_             if y not in openset          //若y不是將被估算的節點_NEWLINE_                 tentative_is_better := true     //暫時判斷為更好elseif tentative_g_score < g_score[y]         //如果起點到y的距離小於y的實際距離_NEWLINE_                 tentative_is_better := true         //暫時判斷為更好else_NEWLINE_                 tentative_is_better := false           //否則判斷為更差if tentative_is_better = true            //如果判斷為更好came_from[y] := x                  //將y設為x的子節點_NEWLINE_                 g_score[y] := tentative_g_score    //更新y到原點的距離_NEWLINE_                 h_score[y] := heuristic_estimate_of_distance(y, goal) //估計y到終點的距離_NEWLINE_                 f_score[y] := g_score[y] + h_score[y]_NEWLINE_                 add y to openset         //將y插入將被估算的節點中_NEWLINE_     return failure  function reconstruct_path(came_from,current_node)     if came_from[current_node] is set_NEWLINE_         p = reconstruct_path(came_from,came_from[current_node])_NEWLINE_         return (p + current_node)_NEWLINE_     else_NEWLINE_         return current_node