Other Memory Limited Heuristic Search

Other Memory limited heuristic search: IDA* uses very little memory Other algorithms may use more memory for more efficient search.

RBFS: Recursive Breadth First Search

• RBFS uses only linear space.
• It mimics best first search.
• It keeps track of the f-value of the best alternative path available from any ancestor of the current node.
• If the current node exceeds this limit, the alternative path is explored.
• RBFS remembers the f-value of the best leaf in the forgotten sub-tree.

RBFS (node: N, value: F(N), bound: B)

• IF f(N)>B, RETURN f(N)
• IF N is a goal, EXIT algorithm
• IF N has no children, RETURN infinity
• FOR each child Ni of N,
• IF f(N)<F(N), F[i] := MAX(F(N),f(Ni))
• ELSE F[i] := f(Ni)
• sort Ni and F[i] in increasing order of F[i]
• IF only one child, F[2] := infinity
• WHILE (F[1] <= B and F[1] < infinity)
• F[1] := RBFS(N1, F[1], MIN(B, F[2]))
• insert Ni and F[1] in sorted order
• RETURN F[1]

MA* and SMA*: MA* and SMA* are restricted memory best first search algorithms that utilize all the memory available. The algorithm executes best first search while memory is available. When the memory is full the worst node is dropped but the value of the forgotten node is backed up at the parent.

Local Search: Local search methods work on complete state formulations. They keep only a small number of nodes in memory. Local search is useful for solving optimization problems:

• Often it is easy to find a solution
• But hard to find the best solution

Algorithm goal:
find optimal configuration (e.g., TSP),

• Hill climbing
• Gradient descent
• Simulated annealing
• For some problems the state description contains all of the information relevant for a solution. Path to the solution is unimportant.
• Examples:
• map coloring
• 8-queens
• cryptarithmetic
• Start with a state configuration that violates some of the constraints for being a solution, and make gradual modifications to eliminate the violations.
• One way to visualize iterative improvement algorithms is to imagine every possible state laid out on a landscape with the height of each state corresponding to its goodness. Optimal solutions will appear as the highest points. Iterative improvement works by moving around on the landscape seeking out the peaks by looking only at the local vicinity.

Iterative improvement
In many optimization problems, the path is irrelevant; the goal state itself is the solution.
An example of such problem is to find configurations satisfying constraints (e.g., n-queens).
Algorithm:
– Start with a solution
– Improve it towards a good solution