UNIT - II
Topic: A Algorithm*
Part A: Introduction
✅ What is A* Algorithm?
A* (pronounced A star) is a popular informed search algorithm used to find the shortest
path to the goal efficiently by combining:
The actual cost to reach a node, and
The estimated cost from the node to the goal (heuristic)
It is one of the most powerful and widely used search algorithms in Artificial Intelligence.
Part B: A Algorithm Explained*
✅ A* Evaluation Function
The A* algorithm uses an evaluation function:
f(n)=g(n)+h(n)f(n) = g(n) + h(n)f(n)=g(n)+h(n)
Symbol Meaning
f(n) Total estimated cost of the cheapest path through node n
g(n) Actual cost from the start node to node n
h(n) Heuristic estimate of cost from n to goal
✅ The node with the lowest f(n) is chosen for expansion first.
Part C: A Algorithm Working – Step-by-Step*
1. Start at the initial node.
2. Calculate f(n) = g(n) + h(n) for all neighbors.
3. Select the node with the lowest f(n).
4. Repeat the process until the goal node is reached.
5. The path with the lowest total cost is returned as the optimal solution.
✅ Example:
Consider finding the shortest path from City A to City G on a map.
g(n) = road distance covered so far
h(n) = straight-line distance to goal (heuristic)
A* considers both: how far you've come + how far you likely still need to go.
Part D: Properties of A Algorithm*
Property Description
Type Informed Search (uses heuristic)
Completeness ✅ Yes, it always finds a solution if one exists
Optimality ✅ Yes, if heuristic is admissible and consistent
Time Complexity High in large spaces (depends on heuristic quality)
Space Complexity High (stores all paths in memory)
✅ Admissible Heuristic
A heuristic is admissible if:
It never overestimates the cost to reach the goal.
It is optimistic.
Example: Straight-line distance in a road map is admissible because the real road distance can
never be shorter.
✅ Consistent Heuristic
A heuristic is consistent if:
h(n)≤c(n,n′)+h(n′)h(n) \leq c(n, n') + h(n')h(n)≤c(n,n′)+h(n′)
Where:
h(n) = heuristic at node n
c(n, n') = cost from node n to n'
h(n') = heuristic at successor node n'
Part E: A Algorithm Pseudocode*
plaintext
CopyEdit
A*(start, goal):
open_list = {start}
closed_list = {}
while open_list is not empty:
current = node in open_list with lowest f(n)
if current == goal:
return path from start to goal
move current from open_list to closed_list
for each neighbor of current:
if neighbor in closed_list:
continue
calculate g(n), h(n), f(n)
if neighbor not in open_list:
add neighbor to open_list
Part F: Advantages and Disadvantages
Advantages Disadvantages
✅ Finds the shortest/optimal path ❌ Uses a lot of memory (stores all possible paths)
✅ More efficient than BFS or DFS ❌ Slower if heuristic is poor or not admissible
✅ Flexible and works for many problems ❌ Complexity grows with state space size
✅ Applications of A* Algorithm
GPS Navigation (finding shortest driving route)
Robot Path Planning
Game Development (pathfinding for game characters)
Puzzle Solving (e.g., 8-puzzle, 15-puzzle)
Part G: A vs Other Algorithms*
Feature A* Search Greedy Best-First BFS
Uses Heuristic ✅ Yes (h(n)) ✅ Yes (h(n)) ❌ No
Uses Path Cost ✅ Yes (g(n)) ❌ No ❌ No
Optimal? ✅ Yes (if h(n) is good) ❌ No ✅ Yes (equal cost)
Complete? ✅ Yes ❌ No ✅ Yes
Memory Use ❌ High ✅ Medium ❌ High
📝 Summary
A* is a smart, informed search that combines path cost and heuristics.
It is complete and optimal if the heuristic is admissible and consistent.
Used in navigation, robotics, and games to find efficient paths.
f(n) = g(n) + h(n) is the core of A*, balancing what we know and what we guess.
Think of A* as “smart navigation that considers how far you’ve come and how far you need
to go.”
