Archive

Posts Tagged ‘Programming’

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.

Problem Space

September 4th, 2010 No comments
Tree-data-structure

Image via Wikipedia

Problem space is a set of states and a set of operators. The operators map from one state to another state. There will be one or more states that can be called initial states, one or more states which we need to reach what are known as goal states and there will be states in between initial states and goal states known as intermediate states. So what is the solution? The solution to the given problem is nothing but a sequence of operators that map an initial state to a goal state. This sequence forms a solution path. What is the best solution? Obviously, the shortest path from the initial state to the goal state is the best one. Shortest path has only a few operations compared to all other possible solution paths. Solution path forms a tree structure where each node is a state. So searching is nothing but exploring the tree from the root node.