Uninformed Search

Week#2-Intelligent System

Building a Problem-Solving Agent

• States
• Any state
• Actions
• Transition Model
• Goal Test
• Path cost

Evaluations of search strategies

• Completeness -> Can find a solution
• Optimality -> Is it guaranteed to be optimal
• Time complexity -> How long does it take to find a solution
• Space Complexity -> How much memory is used by the algorithm

Uninformed search is a class of general-purpose search algorithms which operates in brute force-way. Uninformed search algorithms do not have additional information about state or search space other than how to traverse the tree, so it is also called blind search.

Breadth-First Search

Queue(FIFO) used to order nodes, add to rear

Time Complexity O(b^(d+1))

• D = Depth of the solution
• B = is the branching factor

DFS: Depth first search

Stack (LIFO), add to front

Time complexity O(b^m)
Space complexity O(bm)

• B = Branching factor
• M = maximum depth

Depth-limited search

DFS with limited depth

Useful for when there is a cycle within the graph

• Not complete if l<d
• Not optimal if l>d

l = limit
d = depth

UCS (Uniform-Cost Search)

Uniform Cost Search is the best algorithm for a search problem, which does not involve the use of heuristics. It can solve any general graph for optimal cost. Uniform Cost Search as it sounds searches in branches which are more or less the same in cost

IDS : Iterative-Deepening Search

It’s the same like Depth-Limited Search but we can increase the limited level iteratively. As for me from my understanding its like “Dynamic Depth Limited Search”