CS计算机代考程序代写 algorithm Cost‐Sensitive Search

Cost‐Sensitive Search
 Breadth First Search finds the shortest path in terms of number of actions, i.e., lowest cost when all actions have the same cost.
1A1 1
C1G
 In most case, the cost of each action S is different, so we can introduce a
similar search algorithm which
considers the cost first, called
1
B 1
uniform cost search (or Dijkstra algorithm).

Uniform Cost Search
Idea: Expand a cheapest node (lowest cumulative cost) in the frontier
A5C 2
3
S0 A1C2D4
12
B S 1.5
G 4D2
Order of the nodes to be expanded in the frontier:
S

Uniform Cost Search
Idea: Expand a cheapest node (lowest cumulative cost) in the frontier
A5C 2
3
S0 A1C2D4
12
B S 1.5
G 4D2
Order of the nodes to be expanded in the frontier: S A
B3 C6

Uniform Cost Search
Idea: Expand a cheapest node (lowest cumulative cost) in the frontier
A5C 2
3
S0 A1C2D4
12
B S 1.5
G 4D2
Order of the nodes to be expanded in the frontier: S A C
B3C6G5

Uniform Cost Search
Idea: Expand a cheapest node (lowest cumulative cost) in the frontier
A5C 2
3
S0 A1C2D4
12
B S 1.5
G 4D2
Order of the nodes to be expanded in the frontier: S A C B
B3C6G5

Uniform Cost Search
Idea: Expand a cheapest node (lowest cumulative cost) in the frontier
A5C 2
3
S0 A1C2D4
12
B S 1.5
G 4D2
Order of the nodes to be expanded in the frontier: S A C B D
B 3 C 6 G 5 C 5.5 G 6

Uniform Cost Search
Idea: Expand a cheapest node (lowest cumulative cost) in the frontier
A5C 2
3
S0 A1C2D4
12
B S 1.5
G 4D2
Order of the nodes to be expanded in the frontier: S A C B D G
B 3 C 6 G 5 C 5.5 G 6

Uniform Cost Search properties
 Time complexity
 Suppose the solution costs 􏰯∗ and arcs cost at least 􏰰, then the depth
of the solution is 􏰱∗ at maximum. 􏰳∗ 􏰲
 Takestime􏰡􏰂􏰢􏰴 􏰵􏰉􏰄.  Space complexity
􏰴
 Nodes in the next layer of the solution 􏰡􏰂􏰢􏰳∗􏰵􏰉􏰄.
 Is complete?
 Yes, if 􏰱∗ is finite, which means 􏰯∗ is finite and 􏰰 is positive
 Is optimal?  Yes
􏰲

Problems of Uniform Cost Search
 No information about goal location, so it explores every “direction”.
 Such algorithms are called Uninformed Search Algorithms, including DFS, BFS, Iterative Deepening, Uniform Cost Search.
2A5C 12
3
S0 A1C2D4
B S 1.5
G 4D2
B3 C6

Search Heuristics
 A heuristic is a function that estimates how close a state is to a goal.
 It is problem dependant, designed for a particular search problem.  Example: Euclidean distance for path finding.

Greedy Search
Idea: Expand the node that seems closest to the goal (i.e. best heuristic estimate) in the frontier
A5C3 S 2
12
B S 1.5
Node Heuristic
SABCDG 4 5 7 2 0.5 0
G 4D2
ACD
Order of the nodes to be expanded in the frontier:
S

Greedy Search
Node Heuristic
SABCDG 4 5 7 2 0.5 0
Idea: Expand the node that seems closest to the goal (i.e. best heuristic estimate) in the frontier
A5C3 S 2
12
B S 1.5
G 4D2
ACD
Order of the nodes to be expanded in the frontier:
SD
G

Greedy Search
Node Heuristic
SABCDG 4 5 7 2 0.5 0
Idea: Expand the node that seems closest to the goal (i.e. best heuristic estimate) in the frontier
A5C3 S 2
12
B S 1.5
G 4D2
ACD
Order of the nodes to be expanded in the frontier:
SDG
G