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”