# CMPS140, Winter 2012, Section 01: Lecture 9

Chapter 4:
Hill climbing: optimize one state and one greedy step at a time
Beam search: greedily optimize using k nodes and the best k of k-squared successors at a time.
Simulated annealing:
Consider nodes with various probabilities where the probabilities depend on f-value
and "temperature". Start out with hot temperature and then cool.
Genetic Algorithm:

selection, mutation and crossover
==========================================================
defun mycons (x l)
(append (list x) l))

(defun myreverse (l)
(if l
(append (myreverse (rest l)) (list (first l)))))
Here  are the theorems and proofs from class today. I encourage
you to try covering up the proofs and see if you can recreate them.

---------------------------------------------------------------------------
Defs. h is admissible if h(n) <= h*(n).
Defs. h satisfies consistency if for two adjacent nodes i, j c(i,j) >= |h(i) - h
(j)|.
--------------------------------------------------------------------

Theorems proven  in class:

Lemma 1: Before A*-admissable terminates every optimal path to every unexpanded
node n
has a node n' on OPEN.

pf: Suppose not. Let n be an expanded node, P an optimal path to n without any n
odes
on OPEN. Let n' be the last node on P that was on OPEN. But since it was expande
d
(since it is no longer on OPEN) its children must be on OPEN. Contradiction.

Corollary:  Before each iteration  A*-admissable has a node n on OPEN  with
f-value <= f*(i).

pf: Consider a path to the goal node. Let n be a node on this path that
is on OPEN (guaranteed by the Lemma). f(n) = g^(n) + h(n) = g*(n) (*since on opt
imal path *)
+ h(n). But h(n) <=h*(n) so f(n) <= g*(n) + h*(n) = f*(n) = f*(i) since on an op
timal path.

1. A*-admissable always terminates for finite graphs or graphs with solutions.
proof:
This follows from the fact that all graphs have a bounded  branching factor, tha
t
cycles make g^ worse each time around and that there are a finite number of
paths to any node at any depth.

2. A*-admissable always returns an optimal path if a solution exists.
proof:
Suppose  not. Since 1 shows A* terminates. Let G' be the  goal
that was terminated in with a non-optimal path, and G be an optimal goal. (Note
that G' might equal G !)
Then G' was just expanded with f(G') > f(G) but this contradicts corollary above
since
there must have been a better node on OPEN when G' was expanded.

3. If consistency is satisfied g(n)=g*(n) for expanded nodes n.
proof:
Suppose not. Let n' be the last node expanded in the optimal path to n.
Let n" be n's child that is still on OPEN. (as in proof of Lemma 1).
But by MR and transitivity |h(n") - h(n)| <= g*(n - g*(n))
So that f(n") <= f*(n) < f(n) at time of expansion. So that
n" should have been expanded instead.

4. If MR is satisfied, the sequence of f-values of nodes expanded by A* are
non-decreasing.
proof:
Suppose not. Then let x1 and x2 be nodes expanded in sequence but such
that f(x2) < f(x1). Clearly if x2 was on OPEN at time of x1's expansion
it would have been expanded instead. Therefore x2 is newly arrived!!
and hence is a child of x1. But then f(x2) >= f(x1) since g^(x2) = g^(x1) +
1
and MR says h(x2) >= h(x1) + 1.

Bonus:
We also showed that consistency and h=0 at goal => h(n) <= h*(n) for all nodes n
.
Proof:
Each move along any path from goal increases g^ by 1 and h by at most 1.

99% of what we have proved about A* is based on this simple
understanding:
If h<=h* then h does not decrease faster than g increases
along an optimal path to the goal. Thus f(n)<=f*(n) along
such a path.

If consistency then h does not decrease faster than g increases
along an optimal path from i to ANYTHING. Thus f(n)<=f*(n)
along all such paths.

One node from such paths is always on OPEN or the
path has been traversed.