patternMinor
Survey of informed search algorithms?
Viewed 0 times
surveyinformedsearchalgorithms
Problem
I'm looking for a list of informed search algorithms, also known as heuristic search algorithms.
I'm aware of:
-
best-first search
Are there more best-first algorithm or other informed searches that are not best-first?
I'm aware of:
-
best-first search
- Greedy best-first search
- A* search
Are there more best-first algorithm or other informed searches that are not best-first?
Solution
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,
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,
Context
StackExchange Computer Science Q#1300, answer score: 7
Revisions (0)
No revisions yet.