Please enable JavaScript.
Coggle requires JavaScript to display documents.
Uninformed search strategies - Coggle Diagram
Uninformed search strategies
Breadth-first Search
First root node is expanded
All the successors of the root node are expanded
Implementation
Implemented using FIFO queue
Properties of BFS:
Complete
Optimal if path cost is non-decreasing function of depth of node
Total Number of nodes generated by root of search tree = b+b2+b3+...+(b to the power of (d+1)-b)
Time Complexity = O(b to the power of (d+1))
Space Complexity = O(b to the power of (d+1))
Uniform cost search
An extension of BFS
Expands node n with lowest path cost
Expands nodes in order of increasing the path cost
Identical to BFS when path costs are equal
Implementation
Call tree-search with fringe ordered by path cost
Properties
Complete (if every step cost is positive)
Optimal (if every step cost is positive)
Depth first search
Always expands the deepest node in the current frontier
The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors
Depth-first search uses LIFO queue
Can also be implemented using recursive function
Properties
Incomplete(complete in finite state space)
Time complexity = O("b" to the power of "m"); m-max depth of any node
Space Complexity = O(bm); store only a single path from root to leaf node, with remaining un-expanded sibling node for each node on the path
Not optimal
Depth limited search
DFS with a limited depth
DLS with l=infinity is identical to DFS
Incomplete if l<d, depth of shallowest goal node
Non-optimal if L>d
Time complexity: O("b" to the power of "l")
Space complexity O(bl)
Not easy to determine the limit until we have solved the problem
Failures:
Failure: Indicate no solution
Cutoff: Indicate no solution within the depth limit
Iterative deepening DFS
Gradually increase the limit of DLS
combines the benefits of depth-first and breadth-first search
Like depth-first search, its memory requirements are modest: O(bd)
Like breadth-first search, it is complete when the branching factor is finite
optimal when the path cost is a non-decreasing function of the depth of the node
Properties:
Complete when branching factor is finite
Time complexity: O("b" : : to the power of "d")
Optimal when path cost is non-decreasing function of depth of node
Number of nodes generated by root:
IDS preferred for large search space and when the depth of the solution is unknown
Bidirectional Search
Run two simultaneous searches - One forward, other backward from goal
Implementation
Both the search checks each node whether it is expanded to see whether it is in the fringe of other search tree
Properties
IF both directions use BFS,
Complete if b is finite
Time complexity: O(b to the power d/2)
Space complexity: O(b to the power d/2)
Optimal if step costs are identical
backward searches are more difficult to implement
It requires a PREDECESSOR_FN(x) that returns all states that have x as a successor
Bidirectional search is very difficult when goal states are
implicit
Avoidance of repeated states
avoid states that have already been expanded
Infinite trees are reduced to finite sizes by pruning repeated states
Search should detect repeated states
If found (2 paths to same state), discard one
Need to keep two lists; closed list (store expanded nodes), open list (store un-expanded nodes)
Graph Search algorithm
On problems with many repeated states, graph is efficient than tree search
If current node match a node in closed list, discards it
Properties:
Time, space requirement
Not optimal in general
Searching with partial observation
Limitation in uninformed search strategies
It assumes deterministic environment
It assumes that agent know the effects of all actions
In searching with partial observation
Knowledge of action and states is incomplete
Hence cannot use uninformed search strategies
The incompleteness leads to different type of problems
Sensor-less problem
