Formal Methods II

Perturb
'Die' Shaking up the die.
We're shaking up our eye balls on the search space.

LOCAL SEARCH
LOOP:
At some point (x, y, ...)
Perturb Pick a nearby point
Compare it with current point - eval (p1) < eval (p2)
if better, move there.

We're moving through the space of possible paths.
A

B C

D

The search space is
ABD
ACD

Local Optimum: Of the possible solutions we can see, the one that is the best. There might be one in the future, in the other parts of the search space that we can't see, but for the moment this one is the best. Neighbourhood. You can get stuck at a local optimum, because you cannot consider everything, so you end up missing the other, better solutions.

The book considers partial algs to be greedy algs. You assemble the solutions piece by piece.
Sorting algs take pieces of a problem and solve them. You can completely solve this and this, then merge them. Combining solns. - Divide and conquer.

Recursion. You have to keep on breaking down, then when you get to the end (base case) and take them all back up.

G & C (P)
Break P into P1, P2
S1 = D&C (P1)
S2 = D&C(P2)
S = Combine S1, S2 //you've still got stuff to do as you come back up.
Return S

Local search - only a subset of each step is to be examined.

It's an issue of unfeasibility (time/memory). Do local search when an exhaustive search will take too long.
But often you could prefer to do the local optimum even when the exhaustive approach is feasible. There's just no point.

The search space is the combination of all clothes.
Dressing yourself is a local search - you're not going to look at all your shirts. When you get to a shirt that is good enough, that will probably do.
It's a partial solution.

< S, P, T > Ignore T and you're ignoring a dimension makes it partial. Ignoring some points makes it local.

not wear pants - probably not a valid solution.


Chess.
It's going to probably be a local search. You have an exhaustive search for the first next move, then
The inner most eval function is going to look at the entire state of the board and be able to say what's a good state and what's a bad state.
You have an exhaustive search on the outside, which then calls another eval function that calls a local search.

In pac man, the graph isn't weighted.

d) It becomes more complicated with different terrain. The graph becomes weighted, and we have to use a local search.

Delegation IS D&C. Parallel computing

Doing a jigsaw puzzle. Find the edge pieces.