Scribd
Upload
6 views3 pages

Class Notes

The document outlines the A* (A star) Algorithm, which is used to find the shortest path in various applications, including game search problems and mapping. It explains the algorithm's process, including the calculation of cost parameters g, h, and f, and provides an example of its application in graph traversal. The conclusion emphasizes the algorithm's effectiveness in efficiently reaching a goal state by selecting the minimum f-value node at each step.

Uploaded by

renughewande2004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views3 pages

Class Notes

The document outlines the A* (A star) Algorithm, which is used to find the shortest path in various applications, including game search problems and mapping. It explains the algorithm's process, including the calculation of cost parameters g, h, and f, and provides an example of its application in graph traversal. The conclusion emphasizes the algorithm's effectiveness in efficiently reaching a goal state by selecting the minimum f-value node at each step.

Uploaded by

renughewande2004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Assignment- 2

TITLE :
To study A star (A*) Algorithm

OBJECTIVE :
To understand the concept of A star (A*) Algorithm.

PROBLEM STATEMENT:
Implement A star (A*) Algorithm for any game search problem.

ALGORITHM:

A* Algorithm():

• Add start node to list


• For all the neighbouring nodes, find the least cost F node
• Switch to the closed list o For 8 nodes adjacent to the current node o If the node is
not reachable, ignore it. Else
If the node is not on the open list, move it to the open list and calculate f, g, h.
If the node is on the open list, check if the path it offers is less than the current
path and change to it if it does so.
• Stop working when o You find the destination o You cannot find the
destination going through all possible points

THEORY:

A * algorithm is a searching algorithm that searches for the shortest path between the initial and the final
state. It is used in various applications, such as maps.

In maps the A* algorithm is used to calculate the shortest distance between the source (initial state) and
the destination (final state).

How it works

Imagine a square grid which possesses many obstacles, scattered randomly. The initial and the final cell
is provided. The aim is to reach the final cell in the shortest amount of time.
Here A* Search Algorithm comes to the rescue:

Explanation

A* algorithm has 3 parameters:

• g : the cost of moving from the initial cell to the current cell. Basically, it is the sum of all the cells
that have been visited since leaving the first cell.
• h : also known as the heuristic value, it is the estimated cost of moving from the current cell to
the final cell. The actual cost cannot be calculated until the final cell is reached. Hence, h is the
estimated cost. We must make sure that there is never an over estimation of the cost. f:
it is the sum of g and h. So, f = g + h

The way that the algorithm makes its decisions is by taking the f-value into account. The algorithm
selects the smallest f-valued cell and moves to that cell. This process continues until the algorithm
reaches its goal cell.

Example

A* algorithm is very useful in graph traversals as well. In the following slides, you will see how the
algorithm moves to reach its goal state.

Suppose you have the following graph and you apply A* algorithm on it. The initial node is A and the goal
node is E.

To explain the traversal of the graph above, check out the slides below.

At every step, the f-value is being re-calculated by adding together the g and h values. The minimum
fvalue node is selected to reach the goal state. Notice how node B is never visited.
CONCLUSION:

You might also like