Optimization problem: Difference between revisions

Revision as of 01:38, 26 January 2008

Revision as of 04:28, 31 January 2008

Line 1:

{{mergeto|Optimization (mathematics)|date=January 2008}}

In [[mathematics]] and [[computer science]], an '''optimization problem''' is the problem of finding the ''best'' solution from all feasible solutions. More formally, an optimization problem <math>A</math> is a quadruple <math>(I, f, m, g)</math>, where

Line 11:

m(x, y) = g \{ m(x, y') \mid y' \in f(x) \} .

</math></center>

For each optimization problem, there is a corresponding [[decision problem]] that asks whether there is a feasible solution for some particular measure <math>m_0</math>. For example, if there is a graph <math>G</math> which contains vertices <math>u</math> and <math>v</math>, an optimization problem might be "find a path from <math>u</math> to <math>v</math> that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from <math>u</math> to <math>v</math> that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.