Python,循环最短路径

Question

我正在尝试制作奇怪的最短路径查找方法.但我不知道我怎么做.

我需要一个算法.我做了一些研究,发现了一些寻找最短路径的算法,如Dijkstra算法,Floyd-Warshall算法,Johnson算法.但我认为他们没有达到我的期望.

我想要的是:应该从红点开始,应该遍历所有蓝点并以红点结束.

有算法吗？

(真的很抱歉我的英语.我希望你能理解我.)

Answer 1

你的问题是汉密尔顿循环问题的一个变种,它是NP完全的,因此没有已知的有效解决方案(并且大多数人认为解决方案不存在,但尚未证实)

哈密​​顿循环问题说:给定一个图G=(V,E),找出是否有一个简单的循环(每个顶点最多遍历一次),它遍历所有顶点,并且是一个经典的NP完全问题.

考虑到汉密尔顿循环问题,减少非常简单,颜色为红色的随机点,其余的点为蓝色.当且仅当问题的解决方案是新图上"修改"问题的简单路径时,才能解决哈密顿循环问题.

由于问题是NP-Complete,这意味着没有已知的最佳有效解决方案.您可以尝试使用一些可能适用于小图形的强力技术,或者使用适用于近似/启发式解决方案的蛮力技术.