274
个编辑
更改
→Methods
==Methods==
==Methods==
方法<br>
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.
There is a large amount of literature on polynomial-time algorithms 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 paths and shortest-path trees, flows and circulations, spanning trees, matching, and matroid problems.
There is a large amount of literature on polynomial-time algorithms 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 paths and shortest-path trees, flows and circulations, spanning trees, matching, and matroid problems.
对于某些特殊的离散优化问题，有大量的文献是关于'''<font color="#FF8000">多项式时间 Polynomial Algorithm <\font>'''算法的，其中相当一部分是由'''<font color="#FF8000">线性规划 Linear Programming <\font>'''理论统一起来的。属于这个框架的组合优化问题的一些例子包括'''<font color="#FF8000">最短路径 Shortest paths <\font>'''和'''<font color="#FF8000">最短路径树 Shortest-path Tree <\font>'''、'''<font color="#FF8000">流和循环 Flows And Circulations <\font>'''、生成树、'''<font color="#FF8000">匹配和拟阵 Matching And Matroid Problems <\font>'''问题。
组合优化问题可以看作是在一组离散项目中寻找最佳元素，因此，原则上，任何一种搜索算法或元启发式算法都可以用来解决它们。也许最普遍适用的方法是分支定界法(一种可以在任何时间点停止作为启发式算法的精确算法)、分支定界法(使用线性最优化生成边界)、动态规划法(一种有限搜索窗口的递归解构法)和禁忌搜索法(一种贪婪型交换算法)。然而，遗传搜索算法不能保证首先找到最优解，也不能保证快速运行(在多项式时间内)。由于一些离散优化问题是 NP 完全的，例如旅行商问题，除非 p = NP，否则这是可以预期的。
组合优化问题可以看作是在一组离散项目中寻找最佳元素，因此，原则上，任何一种搜索算法或元启发式算法都可以用来解决它们。也许最普遍适用的方法是分支定界法(一种可以在任何时间点停止作为启发式算法的精确算法)、分支定界法(使用线性最优化生成边界)、动态规划法(一种有限搜索窗口的递归解构法)和禁忌搜索法(一种贪婪型交换算法)。然而，遗传搜索算法不能保证首先找到最优解，也不能保证快速运行(在多项式时间内)。由于一些离散优化问题是 NP 完全的，例如旅行商问题，除非 p = NP，否则这是可以预期的。
== Formal definition ==
== Formal definition ==