1,068
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − + − + + 第8行：
第9行： − 第16行：
第16行： − + − − − 第31行：
第28行： + 第46行：
第44行： + − − + − * <math>g</math>是目标函数，可以是最小值也可以是最大值。 第64行：
第61行： − 第80行：
第76行： + − 在''' 近似算法approximation algorithms'''领域，算法被设计来寻找困难问题的近似最优解。因此，通常的决策版本对问题的定义不够充分，因为它只指定了可接受的解决办法。尽管我们可以引入合适的决策问题，使这个问题更自然地被描述为一个最优化问题。<ref name="Ausiello03">{{citation|last1=Ausiello|first1=Giorgio|title=Complexity and Approximation|year=2003|edition=Corrected|publisher=Springer|display-authors=etal}}</ref> − − − − + − − 第110行：
第101行： − − − − − − 第121行：
第106行： − 第137行：
第121行： + + − *约束复合图 − −
无编辑摘要
{{#seo:
{{#seo:
|keywords=分岔理论，退化点
|keywords=组合优化，运筹学，机器学习，旅行商问题，最小生成树问题，背包问题
|description=在数学上，突变论是动力学系统研究里分岔理论的一个分支；而在几何学中，它也是奇点理论里的一个特殊情形。
|description=组合优化是数学优化方法的一个子领域，与运筹学、算法理论和计算复杂性理论 有关。它在人工智能、机器学习、拍卖理论、软件工程、应用数学和理论计算机科学等领域有着重要的应用。
组合优化主要是从一个有限的对象集合中寻找一个最佳对象。典型的问题是旅行商问题、最小生成树问题和背包问题。
}}
}}
[[File:Minimum spanning tree.svg.png|thumb|300px|right|一个加权平面图的'''最小[[生成树]] Minimum Spanning Tree'''。找到最小[[生成树]]是一个涉及'''组合优化 Combinatorial Optimization'''的常见问题。
[[File:Minimum spanning tree.svg.png|thumb|300px|right|一个加权平面图的'''最小[[生成树]] Minimum Spanning Tree'''。找到最小[[生成树]]是一个涉及'''组合优化 Combinatorial Optimization'''的常见问题。
]]
]]
组合优化是'''数学优化方法 Mathematical Optimization'''的一个子领域，与'''运筹学 Operations Research'''、'''算法理论 Algorithm Theory'''和'''计算复杂性理论 Computational Complexity'''有关。它在'''[[人工智能]] Artificial Intelligence'''、'''[[机器学习]] Machine Learning'''、'''拍卖理论 Auction Theory'''、'''软件工程 Software Engineering'''、'''应用数学 Applied Mathematics'''和'''理论计算机科学 Theoretical Computer Science'''等领域有着重要的应用。
组合优化是'''数学优化方法 Mathematical Optimization'''的一个子领域，与'''运筹学 Operations Research'''、'''算法理论 Algorithm Theory'''和'''计算复杂性理论 Computational Complexity'''有关。它在'''[[人工智能]] Artificial Intelligence'''、'''[[机器学习]] Machine Learning'''、'''拍卖理论 Auction Theory'''、'''软件工程 Software Engineering'''、'''应用数学 Applied Mathematics'''和'''理论计算机科学 Theoretical Computer Science'''等领域有着重要的应用。
一些研究文献<ref>{{cite book | title=Discrete Optimization | url=http://www.elsevier.com/locate/disopt | publisher=Elsevier | accessdate=2009-06-08}}</ref>认为'''离散优化 Discrete Optimization '''是由'''整数规划 Integer Programming '''和组合优化组成的（反过来由解决图结构的优化问题组成），尽管所有这些主题的研究文献都紧密地交织在一起。它通常涉及如何有效地分配用于寻找数学问题解决方案的资源的决策。
一些研究文献<ref>{{cite book | title=Discrete Optimization | url=http://www.elsevier.com/locate/disopt | publisher=Elsevier | accessdate=2009-06-08}}</ref>认为'''离散优化 Discrete Optimization '''是由'''整数规划 Integer Programming'''和组合优化组成的（反过来由解决图结构的优化问题组成），尽管所有这些主题的研究文献都紧密地交织在一起。它通常涉及如何有效地分配用于寻找数学问题解决方案的资源的决策。
==应用==
==应用==
组合优化的应用包括但不限于:
组合优化的应用包括但不限于:
* 物流<ref>{{cite journal |doi=10.1007/s10288-007-0047-3|title=Combinatorial optimization and Green Logistics|journal=4Or|volume=5|issue=2|pages=99–116|year=2007|last1=Sbihi|first1=Abdelkader|last2=Eglese|first2=Richard W.|url=https://hal.archives-ouvertes.fr/hal-00644076/file/COGL_4or.pdf}}</ref>
* 物流<ref>{{cite journal |doi=10.1007/s10288-007-0047-3|title=Combinatorial optimization and Green Logistics|journal=4Or|volume=5|issue=2|pages=99–116|year=2007|last1=Sbihi|first1=Abdelkader|last2=Eglese|first2=Richard W.|url=https://hal.archives-ouvertes.fr/hal-00644076/file/COGL_4or.pdf}}</ref>
* 供应链优化<ref>{{cite journal |doi=10.1016/j.omega.2015.01.006|title=Sustainable supply chain network design: An optimization-oriented review|journal=Omega|volume=54|pages=11–32|year=2015|last1=Eskandarpour|first1=Majid|last2=Dejax|first2=Pierre|last3=Miemczyk|first3=Joe|last4=Péton|first4=Olivier|url=https://hal.archives-ouvertes.fr/hal-01154605/file/eskandarpour-et-al%20review%20R2.pdf}}</ref>
* 供应链优化<ref>{{cite journal |doi=10.1016/j.omega.2015.01.006|title=Sustainable supply chain network design: An optimization-oriented review|journal=Omega|volume=54|pages=11–32|year=2015|last1=Eskandarpour|first1=Majid|last2=Dejax|first2=Pierre|last3=Miemczyk|first3=Joe|last4=Péton|first4=Olivier|url=https://hal.archives-ouvertes.fr/hal-01154605/file/eskandarpour-et-al%20review%20R2.pdf}}</ref>
* 发展最好辐条和目的地的航空公司网络
* 发展最好辐条和目的地的航空公司网络
* 确定运送包裹的最佳方式
* 确定运送包裹的最佳方式
* 制定最佳工作分配
* 制定最佳工作分配
==方法==
==方法==
组合优化问题可以看作是在一些离散项目中搜索最佳元素，因此，原则上，任何一种搜索算法或元启发式算法都可以用来解决它们。也许最普遍适用的方法是'''分支定界法 Branch-and-bound '''(一种可以在任何时间点停止来用作启发式的精确算法)、'''分支切割法 Branch-and-cut '''(使用线性最优化生成边界)、'''动态规划法 Dynamic Programming '''(一种有限搜索窗口的递归解构法)和'''禁忌搜索法 Tabu Search '''(一种贪婪交换算法)。然而，'''遗传搜索算法 Generic Search Algorithms '''不能保证首先找到最优解，也不能保证快速运行(在多项式时间内)。由于一些离散优化问题是NP完全的，例如旅行商问题，除非P=NP，否则这是可以预期的。
组合优化问题可以看作是在一些离散项目中搜索最佳元素，因此，原则上，任何一种搜索算法或元启发式算法都可以用来解决它们。也许最普遍适用的方法是'''分支定界法 Branch-and-bound '''(一种可以在任何时间点停止来用作启发式的精确算法)、'''分支切割法 Branch-and-cut '''(使用线性最优化生成边界)、'''动态规划法 Dynamic Programming '''(一种有限搜索窗口的递归解构法)和'''禁忌搜索法 Tabu Search '''(一种贪婪交换算法)。然而，'''遗传搜索算法 Generic Search Algorithms '''不能保证首先找到最优解，也不能保证快速运行(在多项式时间内)。由于一些离散优化问题是NP完全的，例如旅行商问题，除非P=NP，否则这是可以预期的。
==形式化定义==
==形式化定义==
从形式上来说，一个组合优化问题<math>A</math>是涉及四个变量<math>(I，f，m，g)</math>的问题 ：
从形式上来说，一个组合优化问题<math>A</math>是涉及四个变量<math>(I，f，m，g)</math>的问题 ：
* <math>I</math>是实例中的数学集合；
* <math>I</math>是实例中的数学集合；
* 给定<math>I</math>中的一个实例，<math>f(x)</math>是可行解的有限集合；
* 给定<math>I</math>中的一个实例，<math>f(x)</math>是可行解的有限集合；
* 给定一个实例<math>x</math>和其对应的可行解<math>y</math>，<math>m(x,y)</math>表示<math>y</math>的测度，其中，y通常是正实数。
* 给定一个实例<math>x</math>和其对应的可行解<math>y</math>，<math>m(x,y)</math>表示<math>y</math>的测度，其中，y通常是正实数。
* <math>g</math>是目标函数，可以是最小值也可以是最大值。
然后，我们的目标是找到实例<math>x</math>的一个最优解，也就是可行解<math>y</math>。
然后，我们的目标是找到实例<math>x</math>的一个最优解，也就是可行解<math>y</math>。
<math>
<math>
m(x, y) = g \{ m(x, y') \mid y' \in f(x) \} .
m(x, y) = g \{ m(x, y') \mid y' \in f(x) \} .
在''' 近似算法approximation algorithms'''领域，算法被设计来寻找困难问题的近似最优解。因此，通常的决策版本对问题的定义不够充分，因为它只指定了可接受的解决办法。尽管我们可以引入合适的决策问题，使这个问题更自然地被描述为一个最优化问题。<ref name="Ausiello03">{{citation|last1=Ausiello|first1=Giorgio|title=Complexity and Approximation|year=2003|edition=Corrected|publisher=Springer|display-authors=etal}}</ref>
==NP优化问题==
==NP优化问题==
NP优化问题（NPO）是一个具有以下附加条件的组合优化问题。<ref name="Hromkovic02">{{citation|last1=Hromkovic|first1=Juraj|title=Algorithmics for Hard Problems|year=2002|series=Texts in Theoretical Computer Science|edition=2nd|publisher=Springer}}</ref>注意，下面提到的多项式是相应函数输入大小的函数，而不是某些隐式输入实例集大小的函数。
NP优化问题（NPO）是一个具有以下附加条件的组合优化问题。<ref name="Hromkovic02">{{citation|last1=Hromkovic|first1=Juraj|title=Algorithmics for Hard Problems|year=2002|series=Texts in Theoretical Computer Science|edition=2nd|publisher=Springer}}</ref>注意，下面提到的多项式是相应函数输入大小的函数，而不是某些隐式输入实例集大小的函数。
* 每个可行解<math>y\in f(x)</math>的大小都是由给定实例<math>x</math>的大小多项式约束的，
* 每个可行解<math>y\in f(x)</math>的大小都是由给定实例<math>x</math>的大小多项式约束的，
* 语言<math>\{\,x\,\mid\, x \in I \,\}</math> and <math>\{\,(x,y)\, \mid\, y \in f(x) \,\}</math>在多项式时间内可以可判定语言/识别，并且，
* 语言<math>\{\,x\,\mid\, x \in I \,\}</math> and <math>\{\,(x,y)\, \mid\, y \in f(x) \,\}</math>在多项式时间内可以可判定语言/识别，并且，
* <math>m</math>是可计算的多项式时间。
* <math>m</math>是可计算的多项式时间。
这意味着相应的决策问题在NP中。在计算机科学中，有趣的优化问题通常具有上述性质，因此是NPO问题。如果存在一种在多项式时间内找到最优解的算法，则该问题又称为'''P-优化（PO）问题 P-optimization problem '''。通常，在处理NPO类问题时，人们对决策版本为NP完全的优化问题感兴趣。请注意，硬度关系总是与某些降低有关。由于近似算法和计算优化问题之间的联系，在某些方面保持近似性的缩减比一般的'''图灵和卡普规约 Turing and Karp Reductions '''更为可取。这种规约的一个例子就是'''L-规约 L-reduction '''。因此，具有NP完全决策版本的优化问题不一定称为NPO完全问题。<ref name="Kann92">{{citation|last1=Kann|first1=Viggo|title=On the Approximability of NP-complete Optimization Problems|year=1992|publisher=Royal Institute of Technology, Sweden}}</ref>
这意味着相应的决策问题在NP中。在计算机科学中，有趣的优化问题通常具有上述性质，因此是NPO问题。如果存在一种在多项式时间内找到最优解的算法，则该问题又称为'''P-优化（PO）问题 P-optimization problem '''。通常，在处理NPO类问题时，人们对决策版本为NP完全的优化问题感兴趣。请注意，硬度关系总是与某些降低有关。由于近似算法和计算优化问题之间的联系，在某些方面保持近似性的缩减比一般的'''图灵和卡普规约 Turing and Karp Reductions '''更为可取。这种规约的一个例子就是'''L-规约 L-reduction '''。因此，具有NP完全决策版本的优化问题不一定称为NPO完全问题。<ref name="Kann92">{{citation|last1=Kann|first1=Viggo|title=On the Approximability of NP-complete Optimization Problems|year=1992|publisher=Royal Institute of Technology, Sweden}}</ref>
NPO问题根据其近似性可分为以下子类: <ref name="Hromkovic02" />
NPO问题根据其近似性可分为以下子类: <ref name="Hromkovic02" />
* ''NPO(I)''：等价于'''完全多项式时间近似方案 Fully Polynomial-time approximation scheme | PTAS '''。包含背包问题。
* ''NPO(I)''：等价于'''完全多项式时间近似方案 Fully Polynomial-time approximation scheme | PTAS '''。包含背包问题。
如果对于每个实例<math>x</math>和<math>f(x)</math>中的每个解<math>y</math>，其测度<math>m(x,y) , M(x,y)</math>被一个大小为<math>x</math>的多项式函数所限制，则该NPO问题称为多项式有界（PB）。NPOPB 类是一类多项式有界的 NPO 问题。
如果对于每个实例<math>x</math>和<math>f(x)</math>中的每个解<math>y</math>，其测度<math>m(x,y) , M(x,y)</math>被一个大小为<math>x</math>的多项式函数所限制，则该NPO问题称为多项式有界（PB）。NPOPB 类是一类多项式有界的 NPO 问题。
[[Image:300px-TSP_Deutschland_3.png|thumb|200px|德国15个最大城市的最佳旅行推销员之旅。最优的旅行商途经德国15个最大的城市。在43,589,145,600个可能的游览每个城市的旅行团中，这是最短的一个。]]
[[Image:300px-TSP_Deutschland_3.png|thumb|200px|德国15个最大城市的最佳旅行推销员之旅。最优的旅行商途经德国15个最大的城市。在43,589,145,600个可能的游览每个城市的旅行团中，这是最短的一个。]]
* '''指派问题 Assignment Problem'''
* '''指派问题 Assignment Problem'''
* '''封闭性问题 Closure Problem'''
* '''封闭性问题 Closure Problem'''
* '''车辆线路优化问题 Vehicle Routing Problem'''
* '''车辆线路优化问题 Vehicle Routing Problem'''
* '''武器目标分配问题 Weapon Target Assignment Problem'''
* '''武器目标分配问题 Weapon Target Assignment Problem'''
==参见==
==参见==
*约束复合图
==注解==
==注解==
{{reflist}}
{{reflist}}