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