1,068
个编辑
更改
跳到导航
跳到搜索
第13行：
第13行： − + 第42行：
第42行： − + 第81行：
第81行： − + − + 第96行：
第96行： − + 第160行：
第160行： − | author1-link = William J. Cook − | author3-link = William R. Pulleyblank − | author4-link = Alexander Schrijver 第180行：
第177行： − + 第236行：
第233行： − | author-link = Eugene Lawler 第246行：
第242行： − | author-link = Jon Lee (mathematician) 第259行：
第254行： − | author2-link = Kenneth Steiglitz 第308行：
第302行： − | author1-link = Gerard Sierksma 第337行：
第330行： − − {{Commonscat}}
无编辑摘要
'''组合优化'''主要是从一个有限的对象集合中寻找一个最佳对象。<ref>{{harvnb|Schrijver|2003|p=1}}.</ref>在许多这样的问题中，'''穷举搜索 exhaustive search '''是不易处理的。如果这些优化问题可行解集是离散的，或者可行解集可以化为离散的，那么可以在问题范围内进行运算，其目标是找到最优解。典型的问题是'''旅行商问题 Traveling Salesman Problem'''(“ TSP”)、最小[[生成树]]问题(“ MST”)和'''背包问题 Knapsack Problem'''。
'''组合优化'''主要是从一个有限的对象集合中寻找一个最佳对象。在许多这样的问题中，'''穷举搜索 exhaustive search '''是不易处理的。如果这些优化问题可行解集是离散的，或者可行解集可以化为离散的，那么可以在问题范围内进行运算，其目标是找到最优解。典型的问题是'''旅行商问题 Traveling Salesman Problem'''(“ TSP”)、最小[[生成树]]问题(“ MST”)和'''背包问题 Knapsack Problem'''。
* 在“随机”实例上表现良好的算法（例如，TSP）
* 在“随机”实例上表现良好的算法（例如，TSP）
* '''近似算法 Approximation Algorithm'''在多项式时间内运行并找到一个“接近”最优值的解
* '''近似算法 Approximation Algorithm'''在多项式时间内运行并找到一个“接近”最优值的解
* 解决现实世界中出现的实例，这些实例不一定表现出NP完全问题固有的最坏情况（例如，具有成千上万个节点的TSP实例<ref>{{harvnb|Cook|2016}}.</ref>)
* 解决现实世界中出现的实例，这些实例不一定表现出NP完全问题固有的最坏情况（例如，具有成千上万个节点的TSP实例)
在''' 近似算法approximation algorithms'''领域，算法被设计来寻找困难问题的近似最优解。因此，通常的决策版本对问题的定义不够充分，因为它只指定了可接受的解决办法。尽管我们可以引入合适的决策问题，使这个问题更自然地被描述为一个最优化问题。<ref name="Ausiello03">{{citation|last1=Ausiello|first1=Giorgio|title=Complexity and Approximation|year=2003|edition=Corrected|publisher=Springer|isbn=978-3-540-65431-5|display-authors=etal}}</ref>
在''' 近似算法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|isbn=978-3-540-44134-2}}</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>注意，下面提到的多项式是相应函数输入大小的函数，而不是某些隐式输入实例集大小的函数。
这意味着相应的决策问题在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|isbn=91-7170-082-X}}</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" />
| first1 = William J.
| first1 = William J.
| last1 = Cook
| last1 = Cook
| first2 = William H.
| first2 = William H.
| last2 = Cunningham
| last2 = Cunningham
| first3 = William R.
| first3 = William R.
| last3 = Pulleyblank
| last3 = Pulleyblank
| last4 = Schrijver
| last4 = Schrijver
| first4 = Alexander
| first4 = Alexander
| title = Combinatorial Optimization
| title = Combinatorial Optimization
| publisher = Wiley
| publisher = Wiley
| last = Cook
| last = Cook
| first = William
| first = William
| publisher = [[University of Waterloo]]
| publisher = University of Waterloo
| year = 2016
| year = 2016
}} ''(Information on the largest TSP instances solved to date.)''
}} ''(Information on the largest TSP instances solved to date.)''
| last = Lawler
| last = Lawler
| first = Eugene
| first = Eugene
| title = Combinatorial Optimization: Networks and Matroids
| title = Combinatorial Optimization: Networks and Matroids
| year = 2001
| year = 2001
| first = Jon
| first = Jon
| last = Lee
| last = Lee
| url = https://books.google.com/books?id=3pL1B7WVYnAC
| url = https://books.google.com/books?id=3pL1B7WVYnAC
| title = A First Course in Combinatorial Optimization
| title = A First Course in Combinatorial Optimization
| last2 = Steiglitz
| last2 = Steiglitz
| first2 = Kenneth
| first2 = Kenneth
| title = Combinatorial Optimization : Algorithms and Complexity
| title = Combinatorial Optimization : Algorithms and Complexity
| publisher = Dover
| publisher = Dover
| last2 = Ghosh
| last2 = Ghosh
| first2 = Diptesh
| first2 = Diptesh
| title = Networks in Action; Text and Computer Exercises in Network Optimization
| title = Networks in Action; Text and Computer Exercises in Network Optimization
| publisher = Springer
| publisher = Springer
==外部链接==
==外部链接==
*[https://www.springer.com/mathematics/journal/10878 Journal of Combinatorial Optimization]
*[https://www.springer.com/mathematics/journal/10878 Journal of Combinatorial Optimization]