Please enable JavaScript.
Coggle requires JavaScript to display documents.
5_Uninformed/Blind Search - Coggle Diagram
5_Uninformed/Blind Search
Types of Agents
Reflex
How the world
IS
?
Types
w/State (Model-based)
Simple
Goal-based
How the world
WOULD BE
?
subfields
Search
Planning
Types
Problem Solving
formulate
search
execute
Utility-based
Search Problems
consists of
state space
successor function
start state & goal test
performance measure
reaching goal
how expensive?
components
Initial State
Actions
Transition Model
RESULT(s,a)
Goal State
Path Cost
States
Algorithm
node
parent node
action
path cost
state
depth
Revised Approach
Start with a frontier that contains the initial state.
Repeat
If the frontier is empty, then no solution.
Remove a node from the frontier.
If node contains goal state, return the solution.
Add the node to the explored set.
Expand node, add resulting nodes to the frontier if they aren't already in the frontier or the explored set.
Start with an empty explored set.
Breadth First Search
function
BREADTH-FIRST-SEARCH (problem)
returns
a solution or failure
return
GENERAL-SEARCH (problem, ENQUEUE-AT-END)
Analysis
Complete?
Yes (if b is finite)
Time?
Number of nodes in a b-ary tree of depth d:
1+b+b^2+b^3+…+b^d = O(b^d)
(d is the depth of the optimal solution)
Depth First Search
function
DEPTH-FIRST-SEARCH (problem)
returns
a solution or failure
return
GENERAL-SEARCH (problem, ENQUEUE-AT-FRONT)
Depth Limited Search
Iterative Deepening Search
Uniform-cost Search
Analysis
completeness
time & space complexity
b-ary tree
d: depth of the least-cost solution
m: maximum depth of the state space (may be ∞)
optimality