ch4. informed search and explorartion

Heuristic search algorithms
----------------------------------------------------------
best first-search, uses evaluation function f(n) and heuristic function h(n) - estimated cost from n to the goal

Greedy best-first search f(n) = h(n), can go to infinite loop

A* search = f(n) = g(n) + h(n), optimal if h(n) is admissible ie h(n) <= h*(n)
consistent if h(n) <= c(n,a,n') + h(n')
h(G) = 0
e.g. shortest path from Arad to Bucharest, 8-puzzle sliding tile

A* (like breadth first) is complete and optimal, large space (keeps all nodes in memory) and time complexity, it needs to expand ALL fn <= C* (inside the contour) before expanding the next contour

trees don't loop (because childs are not connected with each other) (for A*, h(n) only needs to be admissible) but graphs can loop so graphs need to be more restrictive (for A*, it h(n) needs to be consistent), if h(n) is consistent then it's admissible but not the other way around ...


Local search and optimization / Iterative improvement algorithms - eg. n-queens
------------------------------------------------------------------------
local search algorithms (use when paths are irrelevant) operate a single current state (rather than multiple paths) and tries to improve it, generally move only to neighbours of that state, unsystematic, paths followed are not retained -> use less memory; also find solutions in large or infinite state spaces eg. nxn-queens problem, think of the state space landscape (hills), it doesn't matter how you got there, just that you got there.

hill-climbing search is like a greedy local search, it grabs a good neighbour state without thinking ahead about where to go next., fast but it gets stuck at local maxima sometimes, needs some restarting. gradient descent is like hill-climbing but it finds the minima. gradient descent is like a ping-pong ball falling down to a hole where the surface is bumpy.

simulated annealing is where you shake the surface a lot in the beginning (high temp) and then gradually reduce the intensity of shaking (lower temp.) over long period of time, so more bad moves are allowed at the beginning and as temperature T decreases, bad moves are less favoured. If T decreases slowly enough, the algorithm will find a global optimum approaching 1.

local beam search keeps track of k states rather than just one, starts off with k randomly generated states, at each step, all the successors of all k states are generated, if any one is a goal, the algorithm halts. Otherwise, it picks the k best successors from the complete list and repeats so useful information is passed among the k parallel search (not the case with a random-walk)

genetic algorithms is like a stochastic beam search in which successor states are generated by combining two parent states, rather than by modifying a single state, so it's like natural selection using sexual reproduction, operations include, 1) initial population 2) fitness function 3) selection 4) crossovers 5) mutations.