Artificial Intelligence · Unit 3
Search Algorithms and Techniques
Exam-focused notes for Search Algorithms and Techniques (Artificial Intelligence, BIT252): what the TU syllabus asks and how it has actually been tested, with 10 solved past questions from this unit.
What this unit covers
- Depth first search
- Breadth first search
- Depth limited search
- Iterative deepening search
- Hill climbing search
- Greedy best first search
- A* search algorithm
- AO* search for multiple goals
- Alpha beta pruning in game trees
- Search algorithm evaluation factors
Iterative deepening search
How iterative deepening search is used to find goal in state space? Illustrate using example. [5]
Iterative Deepening Search (IDS) is a search strategy that combines the space efficiency of Depth-First Search (DFS) and the optimality/completeness of Breadth-First Search (BFS). It works by repeatedly applying depth-limited search with increasing depth li...
Full solved answer →Depth limited search
How do Depth Limited Search solve the problem of Depth First Search and discuss about its limitations? Illustrate the concept of AO* search in multiplication of any 3 matrices.[10]
--- DFS suffers from a critical problem: it can get trapped in infinite loops or go down infinitely deep paths in graphs/trees that have infinite depth or contain cycles. This means DFS may never find a solution even if one exists, making it incomplete. ---...
Full solved answer →Hill climbing search
Discuss about Hill climbing search with its limitations. [5]
Hill Climbing is a local search algorithm that continuously moves in the direction of increasing value (uphill) to find the peak (optimal solution). It is an iterative algorithm that starts with an arbitrary solution and attempts to find a better solution b...
Full solved answer →Justify that AI can't exist without searching? Solve the following 8 puzzle problem using Hill climbing search algorithm.
Initial State: $$\begin{array}{|c|c|c|}\hline 1 & 2 & 4 \ \hline 5 & & 7 \ \hline 3 & 6 & 8 \ \hline\end{array}$$
Goal State: $$\begin{array}{|c|c|c|}\hline 1 & 4 & 7 \ \hline 2 & 5 & 8 \ \hline 3 & 6 & \ \hline\end{array}$$
[10]
Search is the process of systematically exploring a state space to find a sequence of actions leading from an initial state to a goal state. Justification: 1. Problem formulation is universal in AI. Almost every AI problem is formulated as an initial state,...
Full solved answer →Alpha beta pruning in game trees
What is the purpose of alpha beta pruning? Explain. [5]
The purpose of alpha-beta pruning is to reduce the number of nodes evaluated in the minimax search tree without affecting the final result. It allows the minimax algorithm to search deeper in the same amount of time by eliminating (pruning) branches that ca...
Full solved answer →Search algorithm evaluation factors
How do you evaluate any searching algorithm? What are constraint satisfaction problems? Differentiate between Greedy Best First Search and A* search.[10]
--- A searching algorithm is evaluated based on the following four standard criteria: - A search algorithm is complete if it is guaranteed to find a solution whenever one exists. - Example: BFS is complete (for finite branching factor); DFS is not complete ...
Full solved answer →Depth first search
Distinguish between Depth First Search and Breadth First Search. [5]
Note: Reference notes were not available for this topic. The following answer is based on standard, correct Computer Science knowledge appropriate for TU BSc CSIT curriculum. --- DFS explores a graph by going as deep as possible along each branch before bac...
Full solved answer →Differentiate between DFS and BFS. [5]
DFS (Depth First Search) and BFS (Breadth First Search) are two fundamental graph/tree traversal algorithms. They differ in strategy, data structure used, and application. --- Aspect DFS (Depth First Search) BFS (Breadth First Search) --------- Strategy Exp...
Full solved answer →AO* search for multiple goals
Illustrate the concept of AO* search with an example. Which search will work on multiple goals environment? What are the four evaluation factors of searching algorithm?[10]
AO (And-Or Star) search is a heuristic search algorithm used to solve problems that can be decomposed into sub-problems using AND-OR graphs. It is an extension of the A algorithm designed for problem reduction (decomposition) rather than simple state-space ...
Full solved answer →A* search algorithm
Define agent. Describe the heuristic function of A* search? [5]
An agent is anything that can be perceived its environment through sensors and acts upon that environment through actuators. - A human agent has eyes, ears (sensors) and hands, legs (actuators). - A software agent has programs and data as sensors and actuat...
Full solved answer →Make Unit 3 stick
Practice BIT252 with flashcards & quizzes