Local Search Algorithms

Hill‐climbing Search

• aka Greedy local search
• It terminates until it reaches a peak where no neighbors w/ better values
• Does not keep a search tree; keep only the current node data

Local Beam Search

• Like Hill‐climbing, but keep k best at each level, not just one
• Unlike k hill‐climbing w/ random restarts

Simulated Annealing

Hill‐climbing不允許downhill，因此屬於incomplete；uniformly隨機挑選successor屬於complete，但是速度很慢。因此使用此折衷的演算法

• If the move improves, take it. Otherwise, accept the bad move with probability

Let T[1], T[2], …, T[N]=0 be temperature schedule;
Current <‐ initial state;
For i = 1 to N do:
  T <‐ T[i];
  Next <‐ Random next state;
  ΔVal <‐ Value(Next) – Value(Current);
  If ΔVal >= 0,
    Current <‐ Next,
  Else Current <‐ Next w/ probability e^(ΔVal/T)