[go: up one dir, main page]
Scribd
Upload
29 views10 pages

Module 2 - AIDS1 - BFS

The document explains the A* Algorithm, which finds the most cost-effective path from a start node to a goal node using a heuristic function. It details the steps involved in the algorithm, including maintaining OPEN and CLOSED lists, evaluating nodes, and expanding paths until the goal is reached. The document also provides an example of applying the A* Algorithm to find a path from node A to node J, highlighting its effectiveness and limitations regarding path optimality.

Uploaded by

zeroday2021
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
29 views10 pages

Module 2 - AIDS1 - BFS

The document explains the A* Algorithm, which finds the most cost-effective path from a start node to a goal node using a heuristic function. It details the steps involved in the algorithm, including maintaining OPEN and CLOSED lists, evaluating nodes, and expanding paths until the goal is reached. The document also provides an example of applying the A* Algorithm to find a path from node A to node J, highlighting its effectiveness and limitations regarding path optimality.

Uploaded by

zeroday2021
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/ 10

Department of Information Technology | APSIT

Department of Information Technology | APSIT


Department of Information Technology | APSIT
Department of Information Technology | APSIT
Department of Information Technology | APSIT
A* Algorithm extends the path that minimizes the following function-
f(n) = g(n) + h(n)

Here,
 ‘n’ is the last node on the path
 g(n) is the cost of the path from start node to node ‘n’
 h(n) is a heuristic function that estimates cost of the cheapest path from node ‘n’ to the goal
node

Algorithm-

 The implementation of A* Algorithm involves maintaining two lists- OPEN and CLOSED.
 OPEN contains those nodes that have been evaluated by the heuristic function but have not
been expanded into successors yet.
 CLOSED contains those nodes that have already been visited.

The algorithm is as follows-

Step-01:

 Define a list OPEN.


 Initially, OPEN consists solely of a single node, the start node S.

Step-02:

If the list is empty, return failure and exit.

Department of Information Technology | APSIT


Step-03:

 Remove node n with the smallest value of f(n) from OPEN and move it to list CLOSED.
 If node n is a goal state, return success and exit.

Step-04:

Expand node n.

Step-05:

 If any successor to n is the goal node, return success and the solution by tracing the path
from goal node to S.
 Otherwise, go to Step-06.

Step-06:

For each successor node,


 Apply the evaluation function f to the node.
 If the node has not been in either list, add it to OPEN.

Step-07:

Go back to Step-02.

Department of Information Technology | APSIT


The numbers written on edges represent the distance between the nodes.
The numbers written on nodes represent the heuristic value.
Find the most cost-effective path to reach from start state A to final state J using A* Algorithm.

Solution-

Step-01:

 We start with node A.


 Node B and Node F can be reached from node A.

A* Algorithm calculates f(B) and f(F).


 f(B) = 6 + 8 = 14
 f(F) = 3 + 6 = 9

Since f(F) < f(B), so it decides to go to node F.

Department of Information Technology | APSIT


Path- A → F

Step-02:

Node G and Node H can be reached from node F.

A* Algorithm calculates f(G) and f(H).


 f(G) = (3+1) + 5 = 9
 f(H) = (3+7) + 3 = 13

Since f(G) < f(H), so it decides to go to node G.

Path- A → F → G

Step-03:

Node I can be reached from node G.

A* Algorithm calculates f(I).


f(I) = (3+1+3) + 1 = 8
It decides to go to node I.

Path- A → F → G → I

Step-04:

Node E, Node H and Node J can be reached from node I.

A* Algorithm calculates f(E), f(H) and f(J).


 f(E) = (3+1+3+5) + 3 = 15

Department of Information Technology | APSIT


 f(H) = (3+1+3+2) + 3 = 12
 f(J) = (3+1+3+3) + 0 = 10

Since f(J) is least, so it decides to go to node J.

Path- A → F → G → I → J

It is important to note that-


 A* Algorithm is one of the best path finding algorithms.
 But it does not produce the shortest path always.
 This is because it heavily depends on heuristics.

Department of Information Technology | APSIT

You might also like