Please enable JavaScript.
Coggle requires JavaScript to display documents.
Uninformed Search Strategies
(Blind Search)
~ Have no additional…
Uninformed Search Strategies
(Blind Search)
~ Have no additional information about states
~ Uses only information available in problem definition
~ All they can do is generate successors and
distinguish a goal state from a non-goal state
~ All search strategies are distinguished by the
order in which nodes are expanded
Breadth-first Search 
:memo: BFS algorithm starts searching from the root node of the tree and expands all successor node at the current depth before moving to nodes of next depth.
Properties
Optimal? Yes, if the path cost is a non-decreasing function of depth of node (not optimal in general)
Time Complexity
Complete? Yes, when branching factor is finite
~ Branching factor (b): Maximum number of
successors of any node
~ Complete: if there is a solution, breadth-first
search will find it regardless of the kind of graph
Total Number of nodes generated by root of
search tree = b+b2+b3+…+(b(d+1)-b)
Time Complexity =
Space Complexity =
Implementation
using FIFO queue data structure
~ Call TREE-SEARCH with an empty fringe in a FIFO queue
Uniform Cost Search
:memo: 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
-
Properties
Complete? Yes,if every step cost is positive
Optimal? Yes,if every step cost is positive
Depth First Search
:memo: Always expands the deepest node in the current frontier of the search tree
The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors
-
Properties
-
Time complexity = ; m-max depth of any node
Space Complexity = ; needs to store only a single path from the root to a leaf node,along with the remaining unexpanded sibling nodes for each node on the path
Depth Limited Search
:memo: DFS with a limited depth (l - limit)
DLS with l=infinity is identical to DFS
Not easy to determine the limit until we have solved
the problem
Properties
Complete? No,if l<d, depth of shallowest goal node
Optimal? No, if l>d
Time complexity =
Space complexity =
-
Iterative Deepening
Depth-First Search
Limit 0: A
Limit 1: A,B,C
Limit 2: A,B,C,D,E,F,G
:memo: The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found.
Properties
Complete? Yes, when the branching
factor is finite
Optimal? Yes, when the path cost is a non-decreasing function of
the depth of the node
Time complexity =
Space complexity =
-
Bidirectional Search Algorithm
:memo: One forward from the initial state and the other backward from the goal hoping that the two searches meet in the middle
Implementation
Both the search checks each
node whether it is expanded to see whether it is in the fringe of other search tree :arrow_right: Solution has
been found!
-
-
Graph Search Algorithm
- GRAPH-SEARCH
is more efficient than TREE-SEARCH
- Current node matches a node in closed list :arrow_right: discard it
Properties
- Time, space requirement: proportional to size of state Time, space requirement: proportional to size of state
space
- Not optimal in general
-
Formulation
Belief State
A belief state is a set of states that represents the agent’s
current belief about the possible physical states it might be in
Actions
Actions applied to a belief state are just the unions of the results of applying the action to each physical state in the belief state
Path Cost
If the same action can have different costs in different states, then the cost of taking an action in a given belief state could be one of several values.
-
Goal Test
The agent wants a plan that is sure to work, which means that a belief state satisfies the goal only if all the physical states in it satisfy GOAL-TEST