-1

我正在尝试创建一种算法，该算法创建一条以最短/最有效的方式将点图连接在一起的路径，确保所有点都已连接，并且每个点最多有两个连接。

经过一些研究，这似乎是一条（无向）哈密顿路径。我当前的算法只是创建网络中所有可能连接的列表，然后按顺序选择最短的连接，检查它与一个点的连接不超过两次。但是，它无法检查阻止它将整个图形连接在一起的闭环。

我的方法是完全错误的，还是有一种简单的方法来检查闭环并忽略创建它们的连接？

4

1 回答 1

1

寻找哈密顿路径是一个NP 完全问题。您可能找不到比尝试每个节点排列更好的解决方案了。

如果以某种方式找到它，您将立即变得富有和出名:)

于 2015-01-18T22:17:52.007 回答