数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究证明旅行商问题是NP难的
旅行商问题（TSP）是一种解决方案，其中一名销售人员必须从一个地方出发，依次访问所有其他城市，然后返回其出发地。TSP 的目标是找到最短路径。多项式时间难度称为 NP 难，它定义了一类问题的特性。子集和问题是 NP 难问题的简单示例。
NP-难 - 无法在多项式时间内解决的问题类别称为 NP-难。
让我们以五个城市为例，了解销售人员如何以最短距离访问每个城市。
在图中的这两个可能性中，我们更倾向于哪一个？
在这两张图中，图 II 表示最短/最小距离路径。在图 I 中，当销售人员从 Chennai（点 1）前往 Hyderabad（点 5）时，需要花费大量时间才能返回其出发地，并且总行程距离很长，即 (1 -> 2 -> 3 -> 4 -> 5 -> 1)，但在图 II 的情况下，销售人员直接到达点 3（孟买），这节省了时间，并且覆盖了总的最小距离，即 (1 -> 3 -> 5 -> 1)。
我们能否找到 32 个城市问题的可能性？
可能性由(n-1)!/2 解决方案给出。
在 4 个城市问题的情况下，
我们有 (4-1)!/2 = 3!/2
因此，总共有 3 种覆盖距离的可能性。
让我们看看图片，了解 4 个城市的可能性。
在 3 个城市问题的情况下，只有一种覆盖距离的可能性。
现在，让我们考虑 41 个城市的问题，从中我们可以理解 NP-难问题。
在 41 个城市的情况下，销售人员访问每个城市将有 40!/2 种解决方案。
如果销售人员到达每个城市并找到最佳路线，则需要
40! / (2*106) 秒
或 40! / (2*106*24*60*60) 天
或 40! / 365*(2*106*24*60*60) 年 = 6.8 * 1013 倍，这超过了地球的寿命。因此，不可能找到所有可能的路线并获得最优解，而这类问题称为 NP-难。
结论
我们探讨了 NP 难的旅行商问题的概念。我们看到了许多图，这些图简单地给出了最小距离的含义并找到了最佳路线，但是当我们了解 NP 难问题时，我们观察到这类问题无法在多项式时间内解决。所以，这就是 NP 难。
4K+ 阅读量
