Uninformed search

Question 1

Another name of uninformed search

Answer 1

Blind search algorithms

Question 2

Uninformed search

Answer 2

No additional information about states beyond that provided in the problem definition

Question 3

On what basis, search strategies distinguished

Answer 3

All search strategies are distinguished by the order in which nodes are expanded

Question 4

Types of uninformed search algo

Answer 4

1. Breadth first search (BFS)
2. Depth first search (DFS)
3. Depth limited search (DLS)
4. Iterative deepening depth-first search (DFS-ID)
5. Uninformed cost search (UCS)
6. Bidirectional search

Question 5

DS used in BFS

Answer 5

Queue

Question 6

DS used in DFS

Answer 6

Stack

Question 7

DS used in UCS

Answer 7

Priority Queue

Question 8

DFS
* DS
* Completeness
* Optimaility
* Time complexity
* Space complexity
* Action cost
* Idea
* Example

Answer 8

Depth First Search
* DS: Stack
* Completeness:
Finite search space - complete,
Infinite seach space - Incomplete
* Optimality: Not optimal
* Time complexity: O(bᴰ) [Here b:Branching factor, D is depth of the actions] or O(V+E)
* Space complexity: O(D) or O(bd)
* Action cost i.e. cost(s,a) = 0
* Idea : Backtracking search + stop when finding the goal
* Example: (Exhaustively search) game playing (15 puzzle, maze)

Question 9

BFS
* DS
* Completeness
* Optimaility
* Time complexity
* Space complexity
* Action cost
* Idea
* Example

Answer 9

Breadth First Seacrh
* DS : Queue
* Completeness:
Finite search space - complete,
Infinite seach space - Complete if solution exist
* Optimaility: Yes
* Time complexity : O(bᵈ)
* Space complexity : O(bᵈ)
* Action cost i.e. cost(s,a) =c some c>=0
* Example: Valuable for shortest path or ptimal solution. (In path finding algorithms for ex: robotics or GPS navigation)

Question 10

compare memory efficiency of BFS and DFS

Answer 10

BFS consume more memory than DFS

Question 11

Compare time efficiency of BFS and DFS

Answer 11

both same
(for small d, DFS better)

Question 12

DLS
* Definition
* Variation
* Key feature
* Completeness
* Optimality
* Time Complexity
* Space Complexity

Answer 12

• Definition: DLS (Depth Limited Search) is a variation of DFS (Depth First Search) that imposes a predefined limit on the depth of the tree.
• Key feature : Depth limit: The algo explores nodes only upto specified depth, called cutoff limit
• Completeness: If l>d: completeness but not optimal solution
  If l<d: not complete. (not get any solution. algo will terminate) [here d: depth of goal state]
• Optimality : Not optimal since it does not guarantee finding the shortest path to the goal
• Time Complexity: O(bˡ)
• Space Complexity: O(bl)

Question 13

IDS
* Keyword
* All names and shortforms
* Definition
* Completeness
* Otimality
* Time Complexity
* Sapce Complexity
* When preffered
* When worst
* Action Cost

Answer 13

• IDS: Iterative Deepening Search
• DFS-ID: Depth First Search with Iterative Deepening
• IDDFS: Iterative Deepening Depth First Search
• Keyword: Like dog with leash, Combine the benefits of DFS and BFS
• Definition: IDS starts with depth limit 0 and gradually increase the linit until goal is found or search is exhausted
• Completness:
  Finite search space - complete,
  Infinite seach space - Incomplete
• Optimality:
  For Uniform Cost per Step: If all actions have the same cost, IDS is optimal because it finds the shallowest goal node, ensuring the least number of steps to the goal.
  For Non-Uniform Costs: IDS is not optimal if the costs of actions vary, as it does not account for the cumulative path cost. In such cases, algorithms like Uniform Cost Search (UCS) are preferred for optimality.
• Time Complexity: O(bᵈ) same as BFS
• Space Complexity: O(d) (saved)
• IDS is preferred for large search spaces when the depth of solution is unknown
• When worst : If we found a solution at end then DFS-ID is worst than DFS and BFS.
• Action cost i.e. cost(s,a) = for some c>=0

Question 14

UCS
* Another name
* DS
* Definition (Advantage)
* Evaluation Function
* Completeness
* Optimality
* Action cost
* Remeber in appraoch
* Disadvantage
* Time Complexity
* Space Complexity
* Use

Answer 14

UCS (Uniform Cost Search)
* Another name: Branch and Bound
* DS: Priority Queue
* Definition: UCS is a graph search algorithm that finds the least cost path from starting s to a goal state.
* Evaluation Function: f(n) = g(n), ignoring h(n) [Here g(n): cumulative cost (path cost)]
Cumulative cost: Cumulative cost means total cost incurred to to travel from the start node to current node along a specific path.
* Completeness and Optimality: UCS is optimal and complete, making it a fundamental algorithm for path finding and AI problems.
* Action Cost: Assumption all action costs are non-negative (There is exception which causes disadvantage)
* Unexplored list should be empty in the last
* Diadvantage: If graph has zero-cost actions, it will stuck in infinite loop.
* Use for both acyclic and cyclic graphs

Question 15

Exlplored, Frontier, Unexplored

Answer 15

Explored: Visted and processed, Closed List
Frontier: Discovered not fully explored or expanded (waiting to be expanded in future), Open List
Unexplored:Not discovered yet