درخواست توضیح این چند خط پازل 8 با استفاده از روش A-Star.

di4mond

عضو جدید
سلام.

این شبه کد مربوط میشه به حل معمای 8 (پازل 8) با استفاده از روش A-Star.

ولی برام نامفهومه، خوده تعریف a-star رو متوجه شدم، ولی این شبه کد رو خوب متوجه نمیشم.
توضیحش بدید واقعا ممنون میشم.


کد:
[LEFT]function A*(start,goal)
  closedset := the empty set                 % The set of nodes already evaluated.     
  openset := set containing the initial node % The set of tentative nodes to be evaluated.
  g_score[start] := 0                        % Distance from start along optimal path.
  h_score[start] := heuristic_estimate_of_distance(start, goal)
  f_score[start] := h_score[start]           % Estimate d total distance from start to goal through y.
  while openset is not empty
      x := the node in openset having the lowest f_score[] value
      if x = goal
        [B]return reconstruct_path(came_from,goal)[/B]
      remove x from openset
      add x to closedset
      foreach y in neighbor_nodes(x)
          if y in closedset
              continue
[B]          tentative_g_score := g_score[x] + dist_between(x,y)[/B][/LEFT]
 
[LEFT][B]          if y not in openset[/B]
[B]              add y to openset[/B][/LEFT]
 
[LEFT][B]              tentative_is_better := true[/B]
[B]          elseif tentative_g_score < g_score[y][/B]
[B]              tentative_is_better := true[/B]
[B]          else[/B]
[B]              tentative_is_better := false[/B]
[B]          if tentative_is_better = true[/B]
[B]              came_from[y] := x[/B]
[B]              g_score[y] := tentative_g_score[/B]
[B]              h_score[y] := heuristic_estimate_of_distance(y, goal)[/B]
[B]              f_score[y] := g_score[y] + h_score[y][/B]
[B]  return failure[/B][/LEFT]
 
[LEFT][B]function reconstruct_path(came_from,current_node)[/B]
[B]  if came_from[current_node] is set[/B]
[B]      p = reconstruct_path(came_from,came_from[current_node])[/B]
[B]      return (p + current_node)[/B]
[B]  else[/B]         return the empty path[/LEFT]
 
بالا