Search algorithm: Difference between revisions

Revision as of 06:08, 6 October 2023

Latest revision as of 04:10, 18 August 2025

(13 intermediate revisions by 11 users not shown)

Line 18:

Specific applications of search algorithms include:

*Problems in [[combinatorial optimization]], such ashas:

** The [[vehicle routing problem]], a form of [[shortest path problem]]

** The [[knapsack problem]]: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Line 28:

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

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

* Search engine optimization (SEO) and content optimization for web crawlers

* 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 40 ⟶ 41:

Algorithms for searching virtual spaces are used in the [[constraint satisfaction problem]], where the goal is to find a set of value assignments to certain variables that will satisfy specific mathematical [[equation]]s and [[inequation]]s / equalities. They are also used when the goal is to find a variable assignment that will [[discrete optimization|maximize or minimize]] a certain function of those variables. Algorithms for these problems include the basic [[brute-force search]] (also called "naïve" or "uninformed" search), and a variety of [[heuristic function|heuristic]]s that try to exploit partial knowledge about the structure of this space, such as linear relaxation, constraint generation, and [[Local consistency|constraint propagation]].

An important subclass are the [[Local search (optimization)|local search]] methods, that view the elements of the search space as the [[vertex (graph theory)|vertices]] of a graph, with edges defined by a set of heuristics applicable to the case; and scan the space by moving from item to item along the edges, for example according to the [[gradient descent|steepest descent]] or [[best-first search|best-first]] criterion, or in a [[Stochastic optimization|stochastic search]]. This category includes a great variety of general [[metaheuristic]] methods, such as [[simulated annealing]], [[tabu search]], [[A-teams]] <ref>{{Cite journal |last=Talukdar |first=Sarosh |last2=Baerentzen |first2=Lars |last3=Gove |first3=Andrew |last4=De Souza |first4=Pedro |date=1998-12-01 |title=Asynchronous Teams: Cooperation Schemes for Autonomous Agents |url=https://doi.org/10.1023/A:1009669824615 |journal=Journal of Heuristics |language=en |volume=4 |issue=4 |pages=295–321 |doi=10.1023/A:1009669824615 |issn=1572-9397|url-access=subscription }}</ref>, and [[genetic programming]], that combine arbitrary heuristics in specific ways. The opposite of local search would be global search methods. This method is applicable when the search space is not limited and all aspects of the given network are available to the entity running the search algorithm.<ref>{{Cite journal|last1=Hunter|first1=A.H.|last2=Pippenger|first2=Nicholas|date=4 July 2013|title=Local versus global search in channel graphs|journal=Networks: An International Journey|arxiv=1004.2526}}</ref>

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

Line 47 ⟶ 48:

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

The name "combinatorial search" is generally used for algorithms that look for a specific sub-structure of a given [[Discrete mathematics|discrete structure]], such as a graph, a [[string (computer science)|string]], a finite [[group (mathematics)|group]], and so on. The term [[combinatorial optimization]] is typically used when the goal is to find a sub-structure with a maximum (or minimum) value of some parameter. (Since the sub-structure is usually represented in the computer by a set of integer variables with constraints, these problems can be viewed as special cases of constraint satisfaction or discrete optimization; but they are usually formulated and solved in a more abstract setting where the internal representation is not explicitly mentioned.)

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