Home > Courses > Artificial intelligence (CSC 309) > Search Algorithm in AI

Search Algorithm in AI

Subject: Artificial intelligence (CSC 309)
Search algorithms in AI are methods used to explore possible solutions in a problem space, helping machines make decisions, find paths, or solve puzzles. They are broadly divided into uninformed (blind) and informed (heuristic) approaches, each with unique strengths depending on the problem.

Examples of problems:
- Finding the shortest route on Google Maps
- Solving a puzzle (8-puzzle, chess moves)
- Game playing (finding the best move)
- Pathfinding in robotics

Components of a Search Problem


Every AI search problem has:
1. Initial state – where you start
2. Goal state – what you want to reach
3. Actions/operators – possible moves
4. State space – all possible states
5. Cost function (optional) – cost of each move

Types of Search Algorithms


1. Uninformed (Blind) Search


These algorithms don’t use domain-specific knowledge; they explore systematically. i.e they do not use extra knowledge about the goal.

a. Breadth-First Search (BFS): BFS is a graph/tree traversal algorithm.
It explores nodes level by level (like ripples spreading out in water).
- Start at the root (or starting node).
- Visit all neighbors first.
- Then move to the next level of neighbors.
- It uses a queue (FIFO: First In, First Out) to keep track of nodes to visit.




Why BFS ?
-Guarantees shortest path in an unweighted graph (fewest edges).
- Easy to implement with a queue.
- Commonly used in GPS navigation (shortest route), Social networks (finding degrees of connection), Puzzle solving (minimum moves)


b. Depth-First Search (DFS): Goes deep into one branch before backtracking; memory-efficient but not always optimal.





Depth-First Search (DFS) explores a graph or tree by diving deep into one branch before backtracking. It’s ideal for problems where you need to explore all possibilities or paths, like puzzles or maze solving.

DFS is a graph traversal algorithm that uses a stack (or recursion) to explore nodes. It goes as far as possible down one path before backtracking and trying other paths.

Step-by-Step DFS Traversal:
1. Start at A → Stack = [A]
2. Visit A, push B → Stack = [B]
3. Visit B, push D → Stack = [D]
4. Visit D → No children → Backtrack
5. Back to B, push E → Stack = [E]
6. Visit E → No children → Backtrack
7. Back to A, push C → Stack = [C]
8. Visit C, push F → Stack = [F]
9. Visit F → Done ✅

Order of visiting:
A → B → D → E → C → F








c. Iterative Deepening Depth-First Search (IDDFS): Combines DFS’s low memory use with BFS’s completeness. It is a clever hybrid of Depth-First Search (DFS) and Breadth-First Search (BFS). It combines the space efficiency of DFS with the completeness and optimality of BFS, making it ideal for large search spaces where the depth of the solution is unknown.


d. Bidirectional Search: Searches forward from start and backward from goal simultaneously.
Bidirectional Search is a powerful search strategy in Artificial Intelligence that reduces search time by simultaneously exploring from both the start state and the goal state until the two searches meet in the middle.





How It Works
Instead of searching forward from the start all the way to the goal (like BFS or DFS), Bidirectional Search runs two BFS searches at once:
1. One forward from the start node.
2. One backward from the goal node.
When the two searches meet, the path is found by connecting the two halves.

This drastically reduces the number of nodes explored compared to a single BFS.


2. Informed (Heuristic) Search


Informed (Heuristic) Search is a category of search algorithms in Artificial Intelligence that use extra knowledge (heuristics) to guide the search more intelligently toward the goal, instead of blindly exploring like BFS or DFS.

a. Greedy Best-First Search:
- Chooses the path that looks closest to the goal (based only on heuristic). For example, In GPS navigation, it picks the road that seems closest to the destination.
- Fast but not always optimal.





https://www.geeksforgeeks.org/dsa/activity-selection-problem-greedy-algo-1/



DFS vs BFS




By: Vision University

Comments

No Comment yet!

Login to comment or ask question on this topic

Previous Topic