State Space Search

Blind Search

BFS

DFS

Heuristic Search

State: V

Space: State -> Number

Finding state of smallest cost/ greatest value

state cost = 0 / doesn't have to be the best

Maximal State

Hill Climbing Algorithm

https://www.geeksforgeeks.org/introduction-hill-climbing-artificial-intelligence/

s = Starting State

repeat
    N in Neighbor of S with greatest V(N)
    if V(N) > V(s)
        S = N
    else
        return S

//return local non-strict maximum => S is at least as large as any neighbors

The problem is it will stuck in local maximum.

1. Start from good starting point
2. random restart (generate a random state). Run it n times and with random start state.

Example:

Traveling Salesman problem // NP Complete

A-B-C-D-H-G-E-F-A...

Good starting point:

swap with possible pairs (A, C) / (A, D)

swap with immediate neighbor

Hill Climbing with Sideways Motion

use when with large plateu

Goal state of cost 0

N.Queens

State: any placement of Q is on board (2^(N^2))

Neighbor: adding or delete queen

Cost: # of pairs of Q that attack

Sideway Motion search {
   S= Random state
   Q=0
   while(cost(s)>0 && Q<QMax) { //QMax is the max wandering
      NN = set of neighbor of S with minimal cost
      N= choose randomly a state in NN
      if cost(N) = 0 return N
      if(cost(N) < cost(S))
         Q = 0
         S=N
      } else if (Cost(N) = Cost(S))
         Q++
         S=N;
      else
         return FAIL

   }

}

it might need random restart.

Simulated Annealing

very effective, very slow.

http://katrinaeg.com/simulated-annealing.html

s = random state

Gradient Descent - Continuous Space

not every function is differentiable.

Real Params P1...Pk

Real Value Function f(P1....Pk)

Maxmise /minimise