Search Problem

Question 1

Search problem in AI

Answer 1

In AI, a search problem refers to the process of finding a solution or path from an initial state to a goal state, based on certain conditions or constraints. It is fundamental in areas like planning, pathfinding, and decision-making

Question 2

Components of search problem

Answer 2

Question 3

Another name of Uninformed search

Answer 3

Blind search

Question 4

Uninformed search

Answer 4

Uninformed search (also called blind search) refers to search algorithms that explore a search space without any additional knowledge about the goal beyond the information available in the problem definition. These algorithms operate without domain-specific heuristics, meaning they do not use any guidance to prioritize certain paths over others.

Question 5

Common uninformed search algorithms

Answer 5

Breadth-First Search (BFS)
Depth-First Search (DFS)
Uniform Cost Search (UCS)
Depth-Limited Search (DLS)
Iterative Deepening Depth-First Search (IDDFS)

Question 6

Backtracking search

Answer 6

It has to search every leaf node, every possible solution then he can only came to know that which is optimal or minimum cost path

Question 7

Two parameters in backtracking search

Answer 7

b: actions per state
D: Depth of the actions

Question 8

Memory complexity of backtracking. Also reason

Answer 8

O(D)
Here D is Depth of the actions i.e. depth of tree
It needs to keep the history of actions taken for the solution

Question 9

Time complexity of backtracking. Also reason

Answer 9

O(bᴰ)
[Here b: actions per state, D: Depth of the actions]
It needs to reach all leaf nodes to get the solution (very huge)

Question 10

Cost of backtracking

Answer 10

Any cost

Question 11

Algorithm of backtracking search

Answer 11