Please enable JavaScript.
Coggle requires JavaScript to display documents.
Uninformed Search - Coggle Diagram
Uninformed Search
Lecture Outline
Logistics and Recap
Markov Assumption
Properties of Algorithms and Search Graphs
Depth First Search
Breath First Search
Depth First Search (DFS)
follows LIFO
time complexity - O(b^m)
Space complexity - O(mb)
Advantages
All solutions at same approx length
Memory is restricted
Disadvantage
Infinite Solution exists
Shallow solutions
Breath First Search (BFS)
follows FIFO
time complexity - O(b^m)
Space complexity - O(b^m)
Disadvantage
Large branching factor
All solutions are deep in the leaves
Memory restricted
Advtantage
resistant to infinite solutions
When looking for shallow solutions
To find the shortest path, not necessarily the best one
Search Graph properties
Forward branch factor (b) - max neighbours
Maximum path length (m) - max path length
Presence of cycle
Length of the shortest path to goal node
Algorithm properties
Complete algorithm - always finds a solution when it exists
Time complexity - Worst case here
Space complexity - Worst case for memory
Markov Assumption
It is like a test, at every stage, so can assume
The state is planned in such a way that it tells me about its history so I don't have to look back.
Recap
Graph Search
Successor function
Goal function
start state
State
Action function
Which value selected from the Frontier defines the search strategy
Iterative Deepening Search
See next lecture