更改

For NP-complete discrete optimization problems, current research literature includes the following topics:

For NP-complete discrete optimization problems, current research literature includes the following topics:

对于 np 完全的离散优化问题，目前的研究文献包括以下主题:

对于'''<font color="#FF8000"> NP完全 NP-Complete </font>'''的离散优化问题，目前的研究文献包括以下主题:

* polynomial-time exactly solvable special cases of the problem at hand (e.g. see [[fixed-parameter tractable]])

* polynomial-time exactly solvable special cases of the problem at hand (e.g. see [[fixed-parameter tractable]])

 

* algorithms that perform well on "random" instances (e.g. for [[Traveling salesman problem#TSP path length for random pointset in a square|TSP]])

* algorithms that perform well on "random" instances (e.g. for [[Traveling salesman problem#TSP path length for random pointset in a square|TSP]])

 

* [[approximation algorithm]]s that run in polynomial time and find a solution that is "close" to optimal

* [[approximation algorithm]]s that run in polynomial time and find a solution that is "close" to optimal

 

* solving real-world instances that arise in practice and do not necessarily exhibit the worst-case behavior inherent in NP-complete problems (e.g. TSP instances with tens of thousands of nodes<ref>{{harvnb|Cook|2016}}.</ref>).

* solving real-world instances that arise in practice and do not necessarily exhibit the worst-case behavior inherent in NP-complete problems (e.g. TSP instances with tens of thousands of nodes<ref>{{harvnb|Cook|2016}}.</ref>).

 

Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items; therefore, in principle, any sort of search algorithm or metaheuristic can be used to solve them. Perhaps the most universally applicable approaches are branch-and-bound (an exact algorithm which can be stopped at any point in time to serve as heuristic), branch-and-cut (uses linear optimisation to generate bounds), dynamic programming (a recursive solution construction with limited search window) and tabu search (a greedy-type swapping algorithm). However, generic search algorithms are not guaranteed to find an optimal solution first, nor are they guaranteed to run quickly (in polynomial time). Since some discrete optimization problems are NP-complete, such as the traveling salesman problem, this is expected unless P=NP.

Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items; therefore, in principle, any sort of search algorithm or metaheuristic can be used to solve them. Perhaps the most universally applicable approaches are branch-and-bound (an exact algorithm which can be stopped at any point in time to serve as heuristic), branch-and-cut (uses linear optimisation to generate bounds), dynamic programming (a recursive solution construction with limited search window) and tabu search (a greedy-type swapping algorithm). However, generic search algorithms are not guaranteed to find an optimal solution first, nor are they guaranteed to run quickly (in polynomial time). Since some discrete optimization problems are NP-complete, such as the traveling salesman problem, this is expected unless P=NP.

组合优化问题可以看作是在一组离散项目中寻找最佳元素，因此，原则上，任何一种搜索算法或元启发式算法都可以用来解决它们。也许最普遍适用的方法是分支定界法(一种可以在任何时间点停止作为启发式算法的精确算法)、分支定界法(使用线性最优化生成边界)、动态规划法(一种有限搜索窗口的递归解构法)和禁忌搜索法(一种贪婪型交换算法)。然而，遗传搜索算法不能保证首先找到最优解，也不能保证快速运行(在多项式时间内)。由于一些离散优化问题是 NP 完全的，例如旅行商问题，除非 p = NP，否则这是可以预期的。

组合优化问题可以看作是在一组离散项目中寻找最佳元素，因此，原则上，任何一种搜索算法或元启发式算法都可以用来解决它们。也许最普遍适用的方法是'''<font color="#FF8000">分支定界法 Branch-and-bound </font>'''(一种可以在任何时间点停止作为启发式算法的精确算法)、'''<font color="#FF8000">分支切面法 Branch-and-cut </font>'''(使用线性最优化生成边界)、'''<font color="#FF8000">动态规划法 Dynamic Programming </font>'''(一种有限搜索窗口的递归解构法)和'''<font color="#FF8000">禁忌搜索法 Tabu Search </font>'''(一种贪婪型交换算法)。然而，'''<font color="#FF8000">遗传搜索算法 Generic Search Algorithms </font>'''不能保证首先找到最优解，也不能保证快速运行(在多项式时间内)。由于一些离散优化问题是NP完全的，例如旅行商问题，除非P=NP，否则这是可以预期的。

== Formal definition ==

== Formal definition ==