Uninformed search Flashcards
Another name of uninformed search
Blind search algorithms
Uninformed search
No additional information about states beyond that provided in the problem definition
On what basis, search strategies distinguished
All search strategies are distinguished by the order in which nodes are expanded
Types of uninformed search algo
- Breadth first search (BFS)
- Depth first search (DFS)
- Depth limited search (DLS)
- Iterative deepening depth-first search (DFS-ID)
- Uninformed cost search (UCS)
- Bidirectional search
DS used in BFS
Queue
DS used in DFS
Stack
DS used in UCS
Priority Queue
DFS
* DS
* Completeness
* Optimaility
* Time complexity
* Space complexity
* Action cost
* Idea
* Example
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)
BFS
* DS
* Completeness
* Optimaility
* Time complexity
* Space complexity
* Action cost
* Example
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 optimal solution. (In path finding algorithms for ex: robotics or GPS navigation)
compare memory efficiency of BFS and DFS
BFS consume more memory than DFS
Compare time efficiency of BFS and DFS
both same
(for small d, DFS better)
DLS
* Definition
* Variation
* Key feature
* Completeness
* Optimality
* Time Complexity
* Space Complexity
- 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)
IDS
* Keyword
* All names and shortforms
* Definition
* Completeness
* Otimality
* Time Complexity
* Sapce Complexity
* When preffered
* When worst
* Action Cost
- 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
UCS
* Another name
* DS
* Definition (Advantage)
* Evaluation Function
* Completeness
* Optimality
* Action cost
* Remeber in appraoch
* Disadvantage
* Time Complexity
* Space Complexity
* Use
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
Exlplored, Frontier, Unexplored
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
Internal nodes
Nodes except leaf nodes
Relation between leaf nodes and internal nodes
No. of leaf nodes > no. of internal nodes
Derive total nodes and internal nodes formula
BIDIRECTIONAL SEARCH
* Definition
* Where it meets
* Follow which search techniques
* Goal test
* Optimal (additional point)
* Time complexity
* Space complexity
* Optimality
* Completeness
BIDIRECTIONAL SEARCH
- Definition: Advanced graph search algo that operates simulatneously exlporing the search space from both the start and goal states
- Where it meets: It aims to meet in the middle, where two search frontiers intersect
- Follow which search techniques : follow any search techniques BFS, DFS etc
- Goal test: It aims to meet in the middle, where two search frontiers intersect
- Optimal (additional point)
- Time complexity : reduced time complexity comapred to traditional seach algos. In worst case, bidirectional search TC is O(b^(d/2)) when both uses Breadth first search
- Space complexity : O(b^(d/2)) with the need to keep atleast one of the frontiers in memory for intersection checking, which is a notable limitation.
- Optimality : (Optimality tradeoff) While bidirectional search can find a potential solution faster, the first solution encountered may not be optimal.
- Completeness: yes if the goal node is present
