Introduction to A star search Algorithm

Background

I have to review the algorithm of A star search algorithm (also know as A* algorithm) cause I recently worked on a project related to A star search algorithm.

Introduction

  • A star algorithm has two important measure functions. One is heuristic function that estimates the cost of current computing node to the final goal node with regarding to h(x) and h(x) is a heuristic function that can be defined for different demands, the other one is the cost function that calculates the cost from start node to current computing node, with regarding to g(x) and g(x) is defined by the map itself. f(x) is a function that estimates the A star value of each node in the map and it’s just the sum of the former two functions. In other words:

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

    where x is just a node from the map.

  • There are also two lists in A star algorithm. One is Open List which maintains the set of the nodes that need to be calculates by function f(x), it usually refers to set of the surrounding nodes of the current computing node, and the other one is Close List which maintains the set of nodes that has been calculated by f(x) and has already been chosen as the computing node so far.

    1. A star algorithm always chooses the node with smallest value of f(x) among *Open List as the next computing node.
    2. After choosing a new node, the value of f(x) of all surrounding nodes of that new node will be recalculated if it’s smaller than the former value and assign current computing node as the new node’s parent. P.S. if a node is not included in Open List but it’s next to current computing node, then add the node into Open List and calculate its f(x)
    3. repeat 1-2 until the next node is the goal and then find its parent until the last parent is the start node.

Details

  • Pseudocode from another blog:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Add START to OPEN list
while OPEN not empty
get node n from OPEN that has the lowest f(n)
if n is GOAL then return path
move n to CLOSED
for each n' = CanMove(n, direction)
g(n') = g(n) + 1
calculate h(n')
if n' in OPEN list and new n' is not better, continue
if n' in CLOSED list and new n' is not better, continue
remove any n' from OPEN and CLOSED
add n as n's parent
add n' to OPEN
end for
end while
if we get to here, then there is No Solution

Video

  • You can get more direct answer here by video