更改

 

==应用==

==Applications  应用==

Applications for combinatorial optimization include, but are not limited to:

Applications for combinatorial optimization include, but are not limited to:

制定最佳工作分配

制定最佳工作分配

==Methods  方法==

==方法==

There is a large amount of literature on [[polynomial-time algorithm]]s for certain special classes of discrete optimization, a considerable amount of it unified by the theory of [[linear programming]]. Some examples of combinatorial optimization problems that fall into this framework are [[shortest path]]s and [[shortest-path tree]]s, [[flow network|flows and circulations]], [[spanning tree]]s, [[Matching (graph theory)|matching]], and [[matroid]] problems.

There is a large amount of literature on [[polynomial-time algorithm]]s for certain special classes of discrete optimization, a considerable amount of it unified by the theory of [[linear programming]]. Some examples of combinatorial optimization problems that fall into this framework are [[shortest path]]s and [[shortest-path tree]]s, [[flow network|flows and circulations]], [[spanning tree]]s, [[Matching (graph theory)|matching]], and [[matroid]] problems.

组合优化问题可以看作是在一些离散项目中搜索最佳元素，因此，原则上，任何一种搜索算法或元启发式算法都可以用来解决它们。也许最普遍适用的方法是'''分支定界法 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，否则这是可以预期的。

== Formal definition  形式化定义 ==

==形式化定义==

在''' 近似算法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|isbn=978-3-540-65431-5|display-authors=etal}}</ref>

== NP optimization problem  NP优化问题==

==NP优化问题==

==Specific problems  特定问题==

==特定问题==

[[Image:TSP Deutschland 3.png|thumb|200px|An optimal traveling salesperson tour through [[Germany]]’s 15 largest cities. It is the shortest among 43,589,145,600<ref>Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other: 14!/2 = 43,589,145,600.</ref> possible tours visiting each city exactly once.]]

[[Image:TSP Deutschland 3.png|thumb|200px|An optimal traveling salesperson tour through [[Germany]]’s 15 largest cities. It is the shortest among 43,589,145,600<ref>Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other: 14!/2 = 43,589,145,600.</ref> possible tours visiting each city exactly once.]]

'''武器目标分配问题 Weapon Target Assignment Problem '''

'''武器目标分配问题 Weapon Target Assignment Problem '''

==See also==

==参见==

*[[Constraint composite graph]]

*[[Constraint composite graph]]

约束复合图

约束复合图

==Notes==

==注解==

{{reflist}}

{{reflist}}

==References==

==参考文献==

*{{Cite web

*{{Cite web