Posts Tagged ‘Hardware’

Simplified Memory Bounded A* Search

September 4th, 2010 No comments

The Simplified Memory-Bounded Algorithm (SMA*) is a variant of A* search which is memory-bounded.

  • Complete & optimal if enough memory is available to store shallowest solution path.
  • To enqueue new expand, dequeue the unpromising node with highest f-cost.
  • Retains ancestor node information about the quality of the best path in the forgotten sub tree.

Regenerate forgotten node if all other paths look worse.

Iterative Deepening A* Search

September 4th, 2010 No comments

Modification of A* search use f-cost limit as depth bound

  • Increase threshold as minimum of f(.) of previous cycle
  • Each iteration expands all nodes inside the contour for current f-cost
  • complete and optimal
  • Same order of node expansion
  • Storage Efficient – practical

IDA* do not remember history

Therefore cannot avoid repeated states

Breadth First Search Vs Depth First Search

September 4th, 2010 1 comment
Breadth First Search Depth First Search
Optimal solutions are always found

Multiple solutions found early

May arrive at solutions without examining much of search space
Will not go down blind alley for solution Needs little memory (only node in current path needs to be stored)
If solution path is long, the whole tree must be searched up to that depth May settle for non-optimal solution
All of the tree generated must be stored in memory May explore single unfruitful path for a long time (forever if loop exists!)