274
个编辑
更改
跳到导航
跳到搜索
第99行：
第99行： − + − + − + − + + − + 第117行：
第118行： − 然后，我们的目标是找到一个最优解，也就是一个可行的解+ 第145行：
第146行： − + 第153行：
第154行： − 在近似算法领域，算法被设计用来寻找困难问题的近似最优解。因此，通常的决策版本对问题的定义不够充分，因为它只具体说明了可接受的解决办法。尽管我们可以引入合适的决策问题，但这个问题更自然地被描述为一个最佳化问题问题。+
→Formal definition
Formally, a combinatorial optimization problem <math>A</math> is a quadruple <math>(I, f, m, g)</math>, where
Formally, a combinatorial optimization problem <math>A</math> is a quadruple <math>(I, f, m, g)</math>, where
从形式上来说，一个组合优化问题<math>A</math>是一个关于四变量的<math>(I，f，m，g)</math>问题
从形式上来说，一个组合优化问题<math>A</math>是一个关于四变量的<math>(I，f，m，g)</math>问题 ：
* <math>I</math> is a [[Set (mathematics)|set]] of instances;
* <math>I</math> is a [[Set (mathematics)|set]] of instances;
<math>I</math>是实例的数学中的集合；
* given an instance <math>x \in I</math>, <math>f(x)</math> is the finite set of feasible solutions;
* given an instance <math>x \in I</math>, <math>f(x)</math> is the finite set of feasible solutions;
给定<math>I</math>中的一个实例，<math>f(x)</math>是可行解的有限集合；
* given an instance <math>x</math> and a feasible solution <math>y</math> of <math>x</math>, <math>m(x, y)</math> denotes the [[Measure (mathematics)|measure]] of <math>y</math>, which is usually a [[Positive (mathematics)|positive]] [[Real number|real]].
* given an instance <math>x</math> and a feasible solution <math>y</math> of <math>x</math>, <math>m(x, y)</math> denotes the [[Measure (mathematics)|measure]] of <math>y</math>, which is usually a [[Positive (mathematics)|positive]] [[Real number|real]].
给定一个实例<math>x</math>和一个可行解<math>y</math>，<math>m(x,y)</math>表示<math>y</math>的映射函数。
--该句存疑
* <math>g</math> is the goal function, and is either <math>\min</math> or <math>\max</math>.
* <math>g</math> is the goal function, and is either <math>\min</math> or <math>\max</math>.
<math>g</math>是目标函数，可以是求最小值也可以是最大值。
The goal is then to find for some instance <math>x</math> an optimal solution, that is, a feasible solution <math>y</math> with
The goal is then to find for some instance <math>x</math> an optimal solution, that is, a feasible solution <math>y</math> with
然后，我们的目标是找到一个最优解<math>x</math>，也就是一个可行的解<math>y</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_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'.
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_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'.
对于每一个组合优化问题，都有一个相应的决策问题，它询问是否存在某一特定测度的可行解。例如，如果一个图形 < math > g </math > 包含顶点 < math > u </math > 和 < math > v </math > ，那么一个最佳化问题可能是“ find a path from < math > u </math > to < math > v </math > that uses the fewest edges”。这个问题的答案可能是，比方说，4。一个相应的决策问题是“是否存在一条从 < math > u </math > 到 < math > v </math > 使用10个或更少边的路径? ”这个问题可以用简单的“是”或“否”来回答。
对于每一个组合优化问题，都有一个相应的决策问题，它询问是否存在某一特定测度的可行解。例如，如果一个图形 <math>G</math> 包含顶点 <math>u</math > 和 <math>v</math> ，那么一个最佳化问题是“找到一条从<math>u</math>到<math>v</math>且使用最少边的路径”。这个问题的答案可能是，比方说，4。一个相应的决策问题是“是否存在一条从 <math>u</math> 到 <math>v</math> 使用10个或更少边的路径? ”这个问题可以用简单的“是”或“否”来回答。
In the field of approximation algorithms, algorithms are designed to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is more naturally characterized as an optimization problem.
In the field of approximation algorithms, algorithms are designed to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is more naturally characterized as an optimization problem.
在近似算法领域，算法被设计用来寻找困难问题的近似最优解。因此，通常的决策版本对问题的定义不够充分，因为它只具体说明了可接受的解决办法。尽管我们可以引入合适的决策问题，但这个问题更自然地被描述为一个最优化问题。
== NP optimization problem ==
== NP optimization problem ==