Search algorithm: Difference between revisions

Revision as of 23:56, 10 January 2019

Revision as of 09:07, 6 March 2019

Line 17:

* In [[game theory]] and especially [[combinatorial game theory]], choosing the best move to make next (such as with the [[minmax]] algorithm)

* Finding a combination or password from the whole set of possibilities

* [[FactorizationFactorisation|Factoring]] an integer (an important problem in [[cryptography]])

* Optimizing an industrial process, such as a [[chemical reaction]], by changing the parameters of the process (like temperature, pressure, and pH)

* Retrieving a record from a [[database]]

Line 44:

This class also includes various [[Tree traversal|tree search algorithm]]s, that view the elements as vertices of a [[tree (graph theory)|tree]], and traverse that tree in some special order. Examples of the latter include the exhaustive methods such as [[depth-first search]] and [[breadth-first search]], as well as various heuristic-based [[Pruning (decision trees)|search tree pruning]] methods such as [[backtracking]] and [[branch and bound]]. Unlike general metaheuristics, which at best work only in a probabilistic sense, many of these tree-search methods are guaranteed to find the exact or optimal solution, if given enough time. This is called "[[Completeness (logic)|completeness]]".

AnotherAnothe important sub-class consists of algorithms for exploring the [[game tree]] of multiple-player games, such as [[chess]] or [[backgammon]], whose nodes consist of all possible game situations that could result from the current situation. The goal in these problems is to find the move that provides the best chance of a win, taking into account all possible moves of the opponent(s). Similar problems occur when humans or machines have to make successive decisions whose outcomes are not entirely under one's control, such as in [[robot]] guidance or in [[marketing]], [[finance|financial]], or [[military]] strategy planning. This kind of problem — [[combinatorial search]] — has been extensively studied in the context of [[artificial intelligence]]. Examples of algorithms for this class are the [[Minimax|minimax algorithm]], [[alpha–beta pruning]], * Informational search <ref>{{cite paper

|url= http://www.eng.tau.ac.il/~bengal/GTA.pdf

|title=A Group-Testing Algorithm with Online Informational Learning