search Flashcards
what is search
Search is not about prediction but about choice and decision-
making, such as planning and assigning
Search is a computational problem where the goal is to
find a solution, often a sequence of actions or a state, that
transforms an initial state into a goal state, by exploring a
space of possible solutions.
what is a search problem
Search is the process of navigating from the start state to a goal
state by transitioning through intermediate states
what are the stages of a search problem
A search problem consists of
◆ State space: all possible states.
◆ Start state: where the agent begins the search.
◆ Goal state: the desired state that the agent is looking for.
◆ Goal test: whether the goal state is achieved or not.
◆ A successor function (also called transition function, often associated
with a cost): given a certain state, what actions are available and for
those actions what are the next stage the agent will land into
what is a state space
all possible states.
what is a start state
where the agent begins the search.
what is the goal state
the desired state that the agent is looking for.
what is the goal test
whether the goal state is achieved or not.
what is a solution
A solution is a sequence of actions which transforms the start
state to a goal state
what is a successor function
A successor function (also called transition function, often associated
with a cost): given a certain state, what actions are available and for
those actions what are the next stage the agent will land into
what is a state space graph
a mathematical
representation of a search problem
what do nodes represent in a state space graph
nodes represent states
what do arcs represnt in a state space graph
arcs represent transitions
what is search tree
the process of solving the search
problem can be abstracted as a search tree
The start state is the root node.
Children correspond to successors
what do nodes represent in a search tree
Nodes show states, but correspond to plans (i.e.,
paths) that achieve those states
explain tree search problem function
function Tree-Search (problem, strategy) returns a solution, or failure
initialise the search tree via setting the start state of problem as root node and put
it in Frontier
loop do
if there are no nodes in Frontier for expansion then return failure
else choose a node in Frontier for expansion according to strategy and
remove it from Frontier
if the chosen node is a goal state then return the corresponding solution
else expand the node based on problem and add the resulting nodes to Frontier
end
what is a frontier in a search tree problem
to store the nodes waiting for expansion
what is an expansion in a search tree problem
to find and display the children of the node
what is an expansion strategy in a search tree problem
to decide which node in Frontier to
expand (like depth first search), also called to explore
