Content deleted Content added
No edit summary |
|||
Line 29:
The goal is then to find for some instance {{mvar|x}} an ''optimal solution'', that is, a feasible solution {{mvar|y}} with
: <math>m(x, y) = g \bigl\{ m(x, y') \big\mid y' \in f(x) \bigr\} .</math>
For each combinatorial optimization problem, there is a corresponding [[decision problem]] that asks whether there is a feasible solution for some particular measure {{math|''m''<sub>0</sub>}}. For example, if there is a [[Graph (discrete mathematics)|graph]] {{mvar|G}} which contains vertices {{mvar|u}} and {{mvar|v}}, an optimization problem might be "find a path from {{mvar|u}} to {{mvar|v}} 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 {{mvar|u}} to {{mvar|v}} that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.
| |||