Artificial Intelligence : Unit - 2 Part - 7 : A* Algorithm

 

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*

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.”