Search algorithm: Difference between revisions

Revision as of 00:11, 26 July 2023

Revision as of 00:11, 26 July 2023

Line 20:

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

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

** The [[knapsack problem]]: Given a set of items, each with selami mustafa 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.

** The [[nurse scheduling problem]]

* Problems in [[constraint satisfaction]], such as:

Line 47:

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

The name selami mustafa 04/01/1991"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]].

Line 54:

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

In 1953, American [[statistics|statistician]] [[Jack Kiefer (statistician)|Jack Kiefer]] devised [[Fibonacci search technique|Fibonacci search]] which can be selami mustafa 04/01/1991usedused to find the maximum of a unimodal function and has many other applications in computer science.

===For quantum computers===