Outline
Generate-and-test
Hill climbing
Best-first search
Problem reduction
Constraint satisfaction
Informed Search
Informed search methods use problem specific
knowledge, are more efficient.
3
Heuristics
“Rule of Thumb”.
“Heuristics are the criteria, methods and principles for
deciding which among several alternative courses of
action promises to be most effective in order to achieve
some goal.” pearl.
Can use heuristics to identify the most promising search
path.
4
Example of Heuristic Function
A heuristic function at node n is an estimate of the
optimum cost current node to goal. Denoted by h(n).
H(n) = estimated cost of the cheapest path from node n to goal
node.
Example:
Want path form Jalandhar to chandigarh.
Heuristic to chandigarh may be staright line distance
between jalandhar to chandigarh.
H(jalandhar) = euclideandistance(jalandhar, chandigarh).
5
Generate-and-Test
Algorithm
1. Generate a possible solution.
2. Test to see if this is actually a solution.
3. Quit if a solution has been found.
Otherwise, return to step 1.
Generate-and-Test
Acceptable for simple problems.
Inefficient for problems with large space.
Generate-and-Test
Exhaustive generate-and-test.
Heuristic generate-and-test: not consider paths
that seem unlikely to lead to a solution.
Plan generate-test:
- Create a list of candidates.
- Apply generate-and-test to that list.
Generate-and-Test
Example: coloured blocks
“Arrange four 6-sided cubes in a row, with each
side of each cube painted one of four colours,
such that on all four sides of the row one block
face of each colour is showing.”
Generate-and-Test
Example: coloured blocks
Heuristic: if there are more red faces than other
colours then, when placing a block with several
red faces, use few of them as possible as outside
faces.
Best-First Search
Depth-first search: not all competing branches
having to be expanded.
Breadth-first search: not getting trapped on dead-
end paths.
Combining the two is to follow a single path at
a time, but switch paths whenever some
competing path look more promising than
the current one.
Best-First Search (OR Graphs)
A A
B C D
3 5 1
Best-First Search (OR Graphs)
A A A
B C D B C D
3 5 1 3 5
E F
4 6
Best-First Search (OR Graphs)
A A A
B C D B C D
3 5 1 3 5
E F
4 6
A
B C D
5
G H E F
6 5 4 6
Best-First Search (OR Graphs)
A A A
B C D B C D
3 5 1 3 5
E F
4 6
A A
B C D B C D
5 5
G H E F G H E F
6 5 4 6 6 5 6
I J
2 1
Best-First Search
OPEN: nodes that have been generated, but have
not examined.
This is organized as a priority queue.
CLOSED: nodes that have already been examined.
Whenever a new node is generated, check whether
it has been generated before.
Best-First Search
Algorithm
1. OPEN = {initial state}.
2. Loop until a goal is found or there are no nodes left
in OPEN:
- Pick the best node in OPEN
- Generate its successors
- For each successor:
new evaluate it, add it to OPEN, record its
parent.
generated before change parent, update
successors
Best-First Search
Algorithm A* (Hart et al., 1968):
f(n) = g(n) + h(n)
h(n) = cost of the cheapest path from node n to a
goal state.
g(n) = cost of the cheapest path from the initial
state to node n.
Best-First Search
Algorithm A*:
f’(n) = g’(n) + h’(n)
h’(n) (heuristic factor) = estimate of h(n).
g’(n) (depth factor) = approximation of g(n)
found by A* so far.
