Skip to content
Search

A star search algorithm

lastmod 2024-07-15created 2015-11-066 edits

In computer science, the A* algorithm (A* algorithm, pronounced "A-star algorithm") is one of the graph/tree search algorithms that finds the shortest path from a given start vertex to a goal vertex (in other words, one that passes a test able to determine that a path is the shortest path to the given goal vertex).

It is a pathfinding algorithm built by extending Dijkstra's algorithm. It is read as "A-star algorithm".

Principle

The most basic formula is as follows. 

f(x)=g(x)+h(x)

It works as follows.

  1. Insert the node into an ascending priority queue by f(x).
  2. Pop the priority queue.
  3. Find the nodes reachable from that node.
  4. Compute f(x) for those nodes.
  5. Insert those nodes into the priority queue.
  6. Repeat until the goal node is reached.

The pseudocode is as follows. 

PQ.push(start_node, g(start_node) + h(start_node))       //우선순위 큐에 시작 노드를 삽입한다.

while PQ is not empty       //우선순위 큐가 비어있지 않은 동안
    node = PQ.pop       //우선순위 큐를 pop한다.

    if node == goal_node       //만일 해당 노드가 목표 노드이면 반복문을 빠져나온다.
        break

    for next_node in (next_node_begin...next_node_end)       //해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안
        PQ.push(next_node, g(node) + cost + h(next_node))       //우선순위 큐에 다음 노드를 삽입한다.

print goal_node_dist       //시작 노드에서 목표 노드까지의 거리를 출력한다.

See also

Favorite site

References

  1. Astar-algorithm_basic.pdf ↩

author Zer0 sitemap