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

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).

Answer 2

Uniform Cost Search

Uniform cost search (or Branch and Bound) is a variation on best-first search that uses the evaluation function g(node), which for a given node evaluates to the cost of the path leading to that node. In other words, this is an A* algorithm but where h(node) is set to zero. At each stage, the path that has the lowest cost so far is extended. In this way, the path that is generated is likely to be the path with the lowest overall cost, but this is not guaranteed. To find the best path, the algorithm needs to continue running after a solution is found, and if a preferable solution is found, it should be accepted in place of the earlier solution. Uniform cost search is complete and is optimal, providing the cost of a path increases monotonically. In other words, if for every node m that has a successor n, it is true that g(m) < g(n), then uniform cost is optimal. If it is possible for the cost of a node to be less than the cost of its parent, then uniform cost search may not find the best path. Uniform cost search was invented by Dijkstra in 1959 and is also known as Dijkstra’s algorithm.

Best-first search

employs a heuristic in a similar manner to hill climbing. The difference is that with best-first search, the entire queue is sorted after new paths have been added to it, rather than adding a set of sorted paths. In practical terms, this means that best-first search follows the best path available from the current (partially developed) tree, rather than always following a depth-first style approach.

Function best ()
{
    queue = []; // initialize an empty queue
    state = root_node; // initialize the start state
    while (true)
    {
        if is_goal (state)
            then return SUCCESS
        else
        {
            add_to_front_of_queue (successors (state));
            sort (queue);
        }

        if queue == []
            then report FAILURE;
        state = queue [0]; // state = first item in queue
        remove_first_item_from (queue);
    }
}

Beam search

is a form of breadth-first search that employs a heuristic, as seen with hill climbing and best-first search. Beam search works using a threshold so that only the best few paths are followed downward at each level. This method is very efficient in memory usage and would be particularly useful for exploring a search space that had a very high branching factor (such as in game trees for games, such as Go or Chess). It has the disadvantage of not exhaustively searching the entire tree and so may fail to ever find a goal node. In this implementation, the function call select_best_paths (queue, n) removes all but the best n paths from the queue.

Function beam ()
{
    queue = []; // initialize an empty queue
    state = root_node; // initialize the start state
    while (true)
    {
        if is_goal (state)
            then return SUCCESS
        else
        {
            add_to_back_of_queue (successors (state));
            select_best_paths (queue, n);
        }

        if queue == []
            then report FAILURE;
        state = queue [0]; // state = first item in queue
        remove_first_item_from (queue);
    }
}

In this pseudocode, n is used to represent the width threshold, which is set at the beginning of the procedure.

Constraint Satisfaction Search

Search can be used to solve problems that are limited by constraints, such as the eight-queens problem. Such problems are often known as Constraint Satisfaction Problems, or CSPs. In this problem, eight queens must be placed on a chess board in such a way that no two queens are on the same diagonal, row, or column. If we use traditional chess board notation, we mark the columns with letters from a to g and the rows with numbers from 1 to 8. So, a square can be referred to by a letter and a number, such as a4 or g7. This kind of problem is known as a constraint satisfaction problem (CSP) because a solution must be found that satisfies the constraints. In the case of the eight-queens problem, a search tree can be built that represents the possible positions of queens on the board. One way to represent this is to have a tree that is 8-ply deep, with a branching factor of 64 for the first level, 63 for the next level, and so on, down to 57 for the eighth level. A goal node in this tree is one that satisfies the constraints that no two queens can be on the same diagonal, row, or column. An extremely simplistic approach to solving this problem would be to analyze every possible configuration until one was found that matched the constraints. A more suitable approach to solving the eight-queens problem would be to use depth-first search on a search tree that represents the problem in the following manner: The first branch from the root node would represent the first choice of a square for a queen. The next branch from these nodes would represent choices of where to place the second queen. The first level would have a branching factor of 64 because there are 64 possible squares on which to place the first queen. The next level would have a somewhat lower branching factor because once a queen has been placed, the constraints can be used to determine possible squares upon which the next queen can be placed. The branching factor will decrease as the algorithm searches down the tree. At some point, the tree will terminate because the path being followed will lead to a position where no more queens can be placed on legal squares on the board, and there are still some queens remaining.

Answer 3

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,