Survey of informed search algorithms?

Question

I'm looking for a list of informed search algorithms, also known as heuristic search algorithms.

I'm aware of:

1. best-first search

   • Greedy best-first search
   • A* search

Are there more best-first algorithm or other informed searches that are not best-first?

Answer 1

That list would be endless ... I will just try to provide a number of representative examples according to different criteria:

Best-first search (BFS): they are complete, i.e., they are guaranteed to find a solution provided that one exists and they are admissible, i.e., they are guaranteed to find the optimal solution provided, again, that one exists. However, they take memory exponentially in the depth of the search tree. Other than Greedy best-first search and A$^*$, pure heuristic search ($f(n)=h(n)$) is often quoted as another BFS algorithm

Depth-first search (DFS): they are not complete, and thus they are not admissible. However, running a sequence of depth-first searches with a threshold that increases monotonically is guaranteed both to be complete and admissible while it takes memory just linear in the depth of the search tree. The most prominent member in this class would be IDA$^*$. However, this is not the only way to guarantee both completeness and admissibility and Depth-First Bround-and-Bound (DFBnB) takes also memory which is linear in the depth of the search tree.

Bidirectional Search (BS): It has been observed that BS saves an exponential amount of time and memory in the case of blind (non-heuristic) search. Many efforts have been invested to reproduce the same result when using heuristic search but it is still an open question how to implement bidirectional search efficiently when using heuristics. James Kwa showed that BS* does not always expand less nodes than a single A$^*$ and Ariel Felner et al. have recently suggested Single-Frontier Bidirectional Search as a way to turn bidirectional search into a unidirectional search.

Perimeter Search (PS): while most people was considering that bidirectional search consists of two searches progressing simultaneously (either in front-to-front or front-to-end fashion), Giovanni Manzini and also Nelson and Dillemburg simultaneously and independently suggested to develop a perimeter around the target node $t$ and then to issue a unidirectional search from the start state $s$. The resulting algorithm is better known as Bidirectional Iterative-Deepening A* BIDA$^*$

Real-Time Search (RTS): in most cases the search is conducted off-line, i.e., the solution is seeked and as once it is found, it is executed. Korf (again) showed that this is not necessarily a limitation and was the first in introducing Real-Time Search for looking for the solution while the agent is moving. The same algorithm was improved and it is known as Learning Real-Time Search. This work started a branch of research which is continued even nowadays and you can find a myriad of algorithms to solve problems in Real-Time search. Very importantly also, this category of algorithms was devised taking minimax as a motif where decisions are taken without ever visiting a goal node. This is, these algorithms are also expected to solve problems which are unsolvable with the previous algorithms.

Moving-Target Search: somehow related to the previous case, but not exactly equal is the case of seeking a moving target while the agent is moving. Originally (as far as I know) Ishida and Korf (get in use to hear from Korf ;) ) suggested an algorithm called exactly like this Moving-Target Search. Ishida continued the work later and some work has been presented in recent years.

Sub-optimal search: most of the algorithms described above (all but RTS) are used to find optimal solutions. However, some algorithms are "extended" to find sub-optimal solutions with guarantees on the error margin. For example, Ira Pohl introduced weighted-A* WA$^*$ which is known to find solutions with a bounded error. There are also a lot of research in this category and one of my favourite algorithms (among others) is $A_{\epsilon}$

But bear in mind that these are just only a number of prominent examles. The list of algorithms is huge and even the list of categories is quite large (though not impossible to get, of course).

Cheers,

Answer 2

breadth-first search (BFS): is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

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(bd/2)$ (in Big O notation), and the sum of these two search times is much less than the $O(bd)$ complexity that would result from a single search from the beginning to the goal.

As in A* search, bi-directional search can be guided by a heuristic estimate of the remaining distance to the goal (in the forward tree) or from the start (in the backward tree).