274
个编辑
更改
跳到导航
跳到搜索
第60行：
第60行： + 第65行：
第66行： − 关于某些特殊类型的离散优化的多项式时间算法有大量的文献，相当多的文献被线性规划理论所统一。属于这个框架的组合优化问题的一些例子包括最短路径和最短路径树、流和循环、生成树、匹配和拟阵问题。+ 第90行：
第91行： − −
→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 ==