Simplified Memory Bounded A* Search
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
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
A* Search
A* uses a best-first search and finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).
It uses a distance-plus-cost heuristic function (usually denoted f(x)) to determine the order in which the search visits nodes in the tree. The distance-plus-cost heuristic is a sum of two functions:
- The path-cost function, which is the cost from the starting node to the current node (usually denoted g(x))
- In addition, an admissible “heuristic estimate” of the distance to the goal (usually denoted h(x)).
Best-First Search (Greedy Search)
Best-first search is a search algorithm, which explores a graph by expanding the most promising node chosen according to a specified rule.
Judea Pearl described best-first search as estimating the promise of node n by a “heuristic evaluation function f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain.”
Some authors have used “best-first search” to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution, so that paths, which are judged closer to a solution, are extended first. This specific type of search is called greedy best-first search.
Efficient selection of the current best candidate for extension is typically implemented using a priority queue
Comparison of Search Techniques
Criterion |
BFS |
UCS |
DFS |
DLS |
IDS |
BS |
Time |
b_{}^{d} |
b_{}^{d} |
B^{m} |
B^{l} |
b_{}^{d} |
b_{}^{d/2} |
Space |
b_{}^{d} |
b_{}^{d} |
bm |
bl |
bd |
b_{}^{d/2} |
Optimal? |
Yes |
Yes |
No |
No |
Yes |
Yes |
Complete? |
Yes |
Yes |
No |
Yes, If l>=d |
Yes |
Yes |
Bidirectional search
Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state and one backward from the goal, stopping when the two meet in the middle. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree with branching factor b, and the distance from start to goal is d, each of the two searches has complexity O(b^{d/2}) (in Big O notation), and the sum of these two search times is much less than the O(b^{d}) complexity that would result from a single search from the beginning to the goal.
Iterative Deepening Search
Iterative deepening depth-first search (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. On each iteration, IDDFS visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited, assuming no pruning, is effectively breadth-first.
Depth-Limited Search
Like the normal depth-first search, depth-limited search is an uninformed search. It works exactly like depth-first search, but avoids its drawbacks regarding completeness by imposing a maximum limit on the depth of the search. Even if the search could still expand a vertex beyond that depth, it will not do so and thereby it will not follow infinitely deep paths or get stuck in cycles. Therefore depth-limited search will find a solution if it is within the depth limit, which guarantees at least completeness on all graphs.
Breadth First Search Vs Depth First Search
Breadth First Search | Depth First Search |
Advantages | |
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) |
Disadvantages | |
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!) |
Depth First Search
Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it has not finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.