Theory

A* Search algorithm is one of the best and popular techniques used in path-finding and graph traversals. It is a searching algorithm that is used to find the shortest path between an initial and a final point. The A* Search Algorithm also uses a heuristic function that provides additional information regarding how far away from the goal node we are.

Algorithm For A* search

1. Initialization:
• Define two lists: OPEN and CLOSED.
• Add the start node S to the OPEN list.
2. Check OPEN List:
• If the OPEN list is empty, the algorithm fails to find a solution and exits.
3. Select Node:
• Remove the node with the smallest value of f(n) from the OPEN list.
• Move this node to the CLOSED list.
• If the selected node is the goal state, return success and exit.
4. Expand Node:
• Expand the selected node by generating its successor nodes.
5. Goal Test:
• For each successor node, check if it is the goal node.
• If a successor is the goal node, return success and the solution by tracing the path from the start node to the goal node.
• If not, proceed to the next step.
6. Evaluation and Add to OPEN List:
• For each successor node:
• Apply the evaluation function f to calculate its value.
• If the successor node has not been visited (neither in OPEN nor CLOSED list), add it to the OPEN list.
7. Repeat:
• Go back to step 2 and continue the process until a solution is found or the OPEN list is empty.

For example:

Step - 1 Enter the number of nodes and number of links, then click on "Generate Random graph"

Step - 2 Enter Source node and Destination node

Step - 3 Observe the operation. If the OPEN list is empty, the algorithm fails to find a solution and exits.

Step - 4 Final output is displayed