Search algorithm: Difference between revisions

Revision as of 21:31, 20 August 2022

Revision as of 15:13, 4 November 2022

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]]".

Another 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]], and the [[A* search algorithm|A* algorithm]] and its variants.

===For sub-structures of a given structure===

Line 51:

An important and extensively studied subclass are the [[List of algorithms#Graph algorithms|graph algorithm]]s, in particular [[graph traversal]] algorithms, for finding specific sub-structures in a given graph — such as [[Glossary of graph theory#Subgraphs|subgraphs]], [[path (graph theory)|paths]], circuits, and so on. Examples include [[Dijkstra's algorithm]], [[Kruskal's algorithm]], the [[nearest neighbour algorithm]], and [[Prim's algorithm]].

Another important subclass of this category are the [[string searching algorithm]]s, that search for patterns within strings. Two famous examples are the [[Boyer–Moore string search algorithm|Boyer–Moore]] and [[Knuth–Morris–Pratt algorithm]]s, and several algorithms based on the [[suffix tree]] data structure.

===Search for the maximum of a function===

Line 61:

== Search engine optimization ==

{{Main|Search engine optimization}}

Search algorithms used in a search engine such as [[Google]], order the relevant search results based on a myriad of important factors.<ref name=":0">{{Cite journal|last1=Baye|first1=Michael|last2=De los Santos|first2=Barbur|last3=Wildenbeest|first3=Matthijs|date=2016|title=Search Engine Optimization: What Drives Organic Traffic to Retail Sites?|journal=Journal of Economics & Management Strategy|volume=25|pages=6–31|doi=10.1111/jems.12141|s2cid=156960693}}</ref> [[Search engine optimization]] (SEO) is the process in which any given search result will work in conjunction with the search algorithm to organically gain more traction, attention, and clicks, to their site. This can go as far as attempting to adjust the search engines algorithm to favor a specific search result more heavily, but the strategy revolving around SEO has become incredibly important and relevant in the business world.<ref name=":0" />

==See also==