Search Algorithms in Artificial Intelligence
1. Definition and Purpose
A search algorithm takes a search problem as input and returns either:
A solution path to reach the goal state, or
An indication of failure if no solution exists.
Example:
Problem: Finding the shortest route from your home in Hyderabad to Bangalore.
Input: Map of all cities (states), roads (actions), starting city (Hyderabad), and goal city (Bangalore).
Output (Solution): The sequence of cities (Hyderabad → Kurnool → Anantapur → Bangalore).
Failure: If roads are blocked or no path exists, the algorithm returns “No solution found.”
2. Search Tree and State Space
State space: The set of all possible states and actions in the problem domain (can be infinite).
Example: All cities in South India with all possible connecting roads.Search tree: A tree structure superimposed over the state space, representing paths from the initial state to goal states.
Example:Root node: Hyderabad
Branches: Possible routes explored (Hyderabad → Kurnool, Hyderabad → Mahbubnagar)
Paths: Sequences explored towards Bangalore.
Differences:
3. Components of Search Tree
Node: Represents a state in the search process.
Edge: Represents an action leading to a new state.
Root node: The initial state.
Child node / Successor node: A node generated by expanding its parent.
Parent node: The node from which a child is generated.
Example: Route Finding from Hyderabad to Bangalore
Hyderabad
|
(Edge)
|
Kurnool
|
(Edge)
|
Anantapur
|
(Edge)
|
Bangalore
🔷 Explanation
Root node:
The tree starts with Hyderabad, which is the initial state and root node.Node:
Each city like Hyderabad, Kurnool, Anantapur, and Bangalore is a node representing a state in the search process.Edge:
The lines between the cities represent edges, which are actions (travelling along roads) that move you from one state to another.Child node / Successor node:
Kurnool is a child (successor) node of Hyderabad because it is generated by expanding Hyderabad. Similarly, Anantapur is a child of Kurnool, and Bangalore is a child of Anantapur.Parent node:
For example, Hyderabad is the parent node of Kurnool, because Kurnool was generated by expanding Hyderabad. Likewise, Kurnool is the parent node of Anantapur.
4. Expansion and Generation
Expand a node:
Check all available actions from its state.
Use the RESULT function to generate new states.
Create child nodes for each resulting state.
Example: Route Finding from Hyderabad to Bangalore
Hyderabad
/ \
Kurnool Mahbubnagar
|
Anantapur
|
Bangalore
🔷 Expansion and Generation Explained
Expand a node:
Suppose you are in Hyderabad. To expand Hyderabad:
Check all available actions:
From Hyderabad, you can go to Kurnool or Mahbubnagar.Use the RESULT function:
Applying each action (taking the road) leads to a new state (new city).Create child nodes:
You generate Kurnool and Mahbubnagar as child nodes under Hyderabad.
✅ In the tree above, Hyderabad has been expanded, generating its two children.
5. Frontier and Reached States
Frontier:
The set of nodes that have been generated but not yet expanded.
Also called Open list in some references.
Reached states:
All states for which at least one node has been generated (expanded or not).
Interior: States whose nodes have been expanded.
Exterior: States not yet reached (no nodes generated for them).
Example : Frontier and Reached States Explained
Frontier:
After expanding Hyderabad, the frontier consists of Kurnool and Mahbubnagar.
➔ These are nodes that have been generated but not yet expanded.Reached states:
All the cities for which you have generated nodes so far. In this example:Reached states = Hyderabad, Kurnool, Mahbubnagar.
Interior:
States whose nodes have been expanded.Here, Hyderabad is in the interior because it has already been expanded.
Exterior:
States that have not yet been reached (no nodes generated for them).For example, Anantapur and Bangalore are exterior at this stage, as you haven’t generated nodes for them yet.
6. Search Process
The algorithm chooses which node in the frontier to expand next.
Example in the tree above:
Initially, you expanded Hyderabad, generating Kurnool and Mahbubnagar in the frontier.
Now, you must choose between Kurnool and Mahbubnagar for the next expansion.
The essence of search:
Exploring one option now while storing others for later exploration.
Example of Essence of Search
✔️ Explore one option now (e.g. expand Kurnool)
✔️ Store other options (Mahbubnagar) for later exploration.
➡️ This strategy allows systematic exploration without forgetting alternative paths.
7. Graph Search vs Tree Search
Graph Search:
Avoids revisiting the same state.
Uses a closed list to record expanded states, preventing cycles.
Example:
If you reach Kurnool via Hyderabad and later find another longer route to Kurnool via Mahbubnagar, graph search ignores the duplicate because it has already visited Kurnool.
Benefit:Prevents cycles and redundant work. Efficient for problems with loops.
Tree Search:
May generate duplicate nodes for the same state.
No mechanism to avoid revisiting.
Example: You reach Kurnool via Hyderabad, then later again via Mahbubnagar → Hyderabad → Kurnool.
Tree search treats this as a new node, leading to redundant expansion.
Drawback: May explore unnecessary paths repeatedly, especially in graphs with cycles..
0 Comments