CS计算机代考程序代写 Content

Content
 Definition
 Formalising a search problem
 Search state graph
 Search tree
 Generic tree search

What is Search
 Agents may need to be able to plan ahead, i.e. to reason so as to find a sequence of actions needed to solve a task.
 In AI, search techniques are universal problem‐solving methods. Agents use these search methods to solve a specific problem and provide solutions.
Search is the process of navigating from a start state to a goal state by transitioning through intermediate states.

Search Problems
 A search problem consists of
 State space: all possible states.
 Start state: where agent begins the
search.
 Goal test: whether the goal state is
achieved or not.
 A successor function (also called transition function): what each action does and the effects on states, associated with cost.
Cities  Start state: Arad
 A solution is a sequence of actions which transforms the start state to a goal state.
 Successor function: Road to adjacent city with cost =
 State space:
 Goal test: Is state == Bucharest
 Solution:
any path from Arad to Bucharest
distance

State Space Graph
 State space graph: A mathematical representation of a search problem
 Nodes represent states
 Arcs represent successors (action results)  Goaltestisagoalnodeorasetofgoal
A
CG
nodes
S
B
 In real world problems, we usually cannot build state space graph in memory as it is too big

Search Tree
A
CG
 A search tree
S
B
 The start state is the root node
 Children correspond to successors
 Nodes show state, but correspond to
S
B
plans that achieve those states
A BCC
CGG G

Search Tree
A
CG
 A search tree
S
B
 The start state is the root node
 Children correspond to successors
 Nodes show state, but correspond to
S
B
plans that achieve those states
A BCC
CGG G

Search Tree
A
CG
 A search tree
S
B
 The start state is the root node
 Children correspond to successors
 Nodes show state, but correspond to
plans that achieve those states
 For most problems, we can never
build the whole tree
 IfaddinganarcfromBtoA,thenit
ends up an infinite tree

Example: Romania

Search with a search tree
Sibiu
Timisoara Zerind
Arad
Arad Fagaras Oradea R.V. Arad Lugoj Arad Oradea

Search with a search tree
Sibiu
Timisoara Zerind
Arad
Arad Fagaras Oradea R.V. Arad Lugoj Arad Oradea

Search with a search tree
Sibiu
Timisoara Zerind
 Search
Arad
Arad Fagaras Oradea R.V. Arad Lugoj Arad Oradea
 Expand out potential plans (tree nodes)  Maintain a frontier (also called fringe) of
partial plans under consideration
 Try to expand as few nodes as possible

Generic tree search
function Tree-Search (problem, strategy) return a solution, or failure initialise the search tree via setting Frontier to be the start state of problem loop do
end
if there are no nodes in Frontier for expansion then return failure
choose a node in Frontier for expansion according to strategy and remove it from Frontier
if the node contains a goal state then return the corresponding solution
else expand the node based on problem and add the resulting nodes to Frontier
 Important ideas:
 Frontier
 Expansion
 Exploration strategy
 Main question: which node in Frontier to explore?

Example: Tree Search and Priority Queue
Search tree
SS
Priority queue
B BC
S‐B
A
S‐A‐B S‐A‐C
S
B
A
CG
State space graph
S‐A

Example: Tree Search and Priority Queue
Search tree
SS
Priority queue
B BCC
S‐B
A
S‐A‐B S‐A‐C
G
S‐A‐C‐G S‐B‐C
S
B
A
CG
State space graph
S‐A