در علوم کامپیوتر، الگوریتم A* یک الگوریتم کامپیوتری است که به طور وسیع در پیمایش گراف و یافتن مسیر بین دو نقطه که گره نامیده می‌شوند، مورد استفاده قرار می‌گیرد. به علت
عملکرد و دقت بالای این الگوریتم استفاده گسترده‌ای از آن می‌شود. پیتر ای هارت (به انگلیسی: Peter E. Hart)، نیلز نیلسون و برترام رافائل اولین کسانی بودند که آن را در سال ۱۹۶۸
میلادی شرح دادند. این الگوریتم درواقع تعمیمی از الگوریتم دیکسترا می‌باشد. A* با استفاده از آروین(heuristic) عملکرد بهتری نسبت به زمان به دست می‌آورد.
عملکرد و دقت بالای این الگوریتم استفاده گسترده‌ای از آن می‌شود. پیتر ای هارت (به انگلیسی: Peter E. Hart)، نیلز نیلسون و برترام رافائل اولین کسانی بودند که آن را در سال ۱۹۶۸
میلادی شرح دادند. این الگوریتم درواقع تعمیمی از الگوریتم دیکسترا می‌باشد. A* با استفاده از آروین(heuristic) عملکرد بهتری نسبت به زمان به دست می‌آورد.
کد:
function A[COLOR=#000040]*[/COLOR][COLOR=#008000]([/COLOR]start,goal[COLOR=#008000])[/COLOR]
closedset[COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] the empty set [COLOR=#666666]// The set of nodes already evaluated.[/COLOR]
openset[COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] [COLOR=#008000]{[/COLOR]start[COLOR=#008000]}[/COLOR] [COLOR=#666666]// The set of tentative nodes to be evaluated,[/COLOR]
[COLOR=#666666]// initially containing the start node[/COLOR]
came_from[COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] the empty map [COLOR=#666666]// The map of navigated nodes.[/COLOR]
g_score[COLOR=#008000][[/COLOR]start[COLOR=#008000]][/COLOR][COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] [COLOR=#0000dd]0[/COLOR] [COLOR=#666666]// Cost from start along best known path.[/COLOR]
h_score[COLOR=#008000][[/COLOR]start[COLOR=#008000]][/COLOR][COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] heuristic_cost_estimate[COLOR=#008000]([/COLOR]start, goal[COLOR=#008000])[/COLOR]
f_score[COLOR=#008000][[/COLOR]start[COLOR=#008000]][/COLOR][COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] g_score[COLOR=#008000][[/COLOR]start[COLOR=#008000]][/COLOR] [COLOR=#000040]+[/COLOR] h_score[COLOR=#008000][[/COLOR]start[COLOR=#008000]][/COLOR] [COLOR=#666666]// Estimated total cost[/COLOR]
[COLOR=#666666]// from start to goal through y.[/COLOR]
[COLOR=#0000ff]while[/COLOR] openset is not empty
x[COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] the node in openset having the lowest f_score[COLOR=#008000][][/COLOR] value
[COLOR=#0000ff]if[/COLOR] x [COLOR=#000080]=[/COLOR] goal
[COLOR=#0000ff]return[/COLOR] reconstruct_path[COLOR=#008000]([/COLOR]came_from, came_from[COLOR=#008000][[/COLOR]goal[COLOR=#008000]])[/COLOR]
[COLOR=#0000dd]remove[/COLOR] x from openset
add x to closedset
foreach y in neighbor_nodes[COLOR=#008000]([/COLOR]x[COLOR=#008000])[/COLOR]
[COLOR=#0000ff]if[/COLOR] y in closedset
[COLOR=#0000ff]continue[/COLOR]
tentative_g_score[COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] g_score[COLOR=#008000][[/COLOR]x[COLOR=#008000]][/COLOR] [COLOR=#000040]+[/COLOR] dist_between[COLOR=#008000]([/COLOR]x,y[COLOR=#008000])[/COLOR]
[COLOR=#0000ff]if[/COLOR] y not in openset
add y to openset
tentative_is_better[COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] [COLOR=#0000ff]true[/COLOR]
[COLOR=#0000ff]else[/COLOR] [COLOR=#0000ff]if[/COLOR] tentative_g_score [COLOR=#000080]<[/COLOR]g_score[COLOR=#008000][[/COLOR]y[COLOR=#008000]][/COLOR]
tentative_is_better[COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] [COLOR=#0000ff]true[/COLOR]
[COLOR=#0000ff]else[/COLOR]
tentative_is_better[COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] [COLOR=#0000ff]false[/COLOR]
[COLOR=#0000ff]if[/COLOR] tentative_is_better [COLOR=#000080]=[/COLOR] [COLOR=#0000ff]true[/COLOR]
came_from[COLOR=#008000][[/COLOR]y[COLOR=#008000]][/COLOR][COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] x
g_score[COLOR=#008000][[/COLOR]y[COLOR=#008000]][/COLOR][COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] tentative_g_score
h_score[COLOR=#008000][[/COLOR]y[COLOR=#008000]][/COLOR][COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] heuristic_cost_estimate[COLOR=#008000]([/COLOR]y, goal[COLOR=#008000])[/COLOR]
f_score[COLOR=#008000][[/COLOR]y[COLOR=#008000]][/COLOR][COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] g_score[COLOR=#008000][[/COLOR]y[COLOR=#008000]][/COLOR] [COLOR=#000040]+[/COLOR] h_score[COLOR=#008000][[/COLOR]y[COLOR=#008000]][/COLOR]
[COLOR=#0000ff]return[/COLOR] failure
function reconstruct_path[COLOR=#008000]([/COLOR]came_from, current_node[COLOR=#008000])[/COLOR]
[COLOR=#0000ff]if[/COLOR] came_from[COLOR=#008000][[/COLOR]current_node[COLOR=#008000]][/COLOR] is set
p[COLOR=#008080]:[/COLOR][COLOR=#000080]=[/COLOR] reconstruct_path[COLOR=#008000]([/COLOR]came_from, came_from[COLOR=#008000][[/COLOR]current_node[COLOR=#008000]])[/COLOR]
[COLOR=#0000ff]return[/COLOR] [COLOR=#008000]([/COLOR]p [COLOR=#000040]+[/COLOR] current_node[COLOR=#008000])[/COLOR]
[COLOR=#0000ff]else[/COLOR]
[COLOR=#0000ff]return[/COLOR] current_node
