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

.

That is, cosistency implies admissibility.

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.