`连接多个点的最短路径

2024-03-29 14:23:21 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在阅读“摸索算法”,了解Dijkstran和贪婪算法,
但是,当笔者将其与NP完全问题进行比较时

But it’s hard to tell if a problem you’re working on is NP-complete. Usually there’s a very small difference between a problem that’s easy to solve and an NP-complete problem. For example, in the previous chapters, I talked a lot about shortest paths. You know how to calculate the shortest way to get from point A to point B.
enter image description hereBut if you want to find the shortest path that connects several points, that’s the traveling-salesperson problem, which is NP-complete. The short answer: there’s no easy way to tell if the problem you’re working on is NP-complete. Here are some giveaways:

句子:
但是如果你想找到连接几个点的最短路径

什么是“几点”?
一个基本的Dijkstan算法问题,我想不出有什么不同。你知道吗


Tags: thetore算法youifthatis
1条回答
网友
1楼 · 发布于 2024-03-29 14:23:21

他指的是通过一个图的所有节点的子集的路径,我想。(考虑“几点”的最坏情况)

注意,对于任何固定数量的点,例如n个节点的图上的k=3或k=3000,问题的复杂性与两点相同。虽然有些人可能认为数永远不会大于7,或者可能是7、几十、70亿,但这既不是事实,也不是精确的科学。你知道吗

不太可能,他指的是旅行推销员问题(连通图上的所有节点/点)的通常公式,尽管有可能。NP完全。你知道吗

相关问题 更多 >