我有一个无向和未加权图的某个节点子集。我正在尝试确定所有这些节点之间是否存在路径，如果存在，最短路径是什么，其中包含不在节点子集中的最少节点。
我一直在想一种方法来修改最小生成树算法来实现这一点，但到目前为止我还没有想出一个可行的解决方案。
有没有一种好方法可以做到这一点，或者这是对已知算法的描述？
问问题
2850 次
6 回答
2
我正在尝试确定所有这些节点之间是否存在路径
（据我了解，您正在寻找访问所有标记节点的单一路径）
好吧，我的朋友，这可能是一个问题 - 您正在描述旅行商问题和哈密顿路径问题的变体（如果您正在寻找一条简单的路径，哈密顿路径的简化是直截了当的：标记所有节点）。
但恐怕这些问题是NP-Hard。
NP-Hard 问题是一个我们不知道任何多项式时间解决方案来解决它的问题，并且一般假设是 - 不存在1。
因此，您最好的选择可能是某种指数解决方案。有O(n^2 * 2^n)使用动态编程或蛮力解决方案的 TSP 解决方案，它们是O(n!)
(1) 真的不是一个正式的定义，但这是足够的信息来理解问题，NP-Hard 问题真的有很多。
于 2012-10-12T09:11:06.270 回答
2
这是一种方法，可以帮助您实现一些目标：
对于每个 i 和 j，使用Floyd-Warshall或 Dijkstra 求节点 i 和节点 j 之间的距离 d(i, j)，使得节点 i 和节点 j 在节点的子集中。
（如果 d(i,j) = infinity 那么现在停止，没有解决方案）
制作一个包含子集中每个节点的新图。对于每个 d(i, j)，在新图中的节点 i、节点 j 之间添加一条边，权重 = d(i, j)
现在在这个新图上使用旅行商算法来找到访问所有节点的最短路径。
这条最短路径为您提供了路径的长度，但该路径可能会多次访问某些节点。这意味着我们对所需子集之外的节点数量有一个上限。
于 2012-10-12T01:59:35.577 回答
0
Dijkstra 算法或使用广度优先搜索。
于 2012-10-12T01:21:09.557 回答
0
我创建了一个 Graph/Node/Connection 类，它不仅可以显示最短路径，还可以告诉您是否所有节点都已连接：
var allNodesAreConnected = StartNode.AllNodes.All(n => n.IsConnectedToStartNode);
或者，如果您想知道哪些节点未连接，请稍微更改一下：
var anotConnectedNodes = StartNode.AllNodes.Where(n => !n.IsConnectedToStartNode);
这篇文章中的更多示例和完整代码： 创建您自己的导航系统（使用 Graph、Node 和 Connection 类）
于 2014-03-05T12:36:30.307 回答
0
您应该使用Dijkstra 的最短路径算法。首先，您必须为图中的所有边分配权重（或距离），连接不在子集中的两个节点的每条边必须被赋予权重 1。连接子集中一个或两个节点的每条边必须被赋予无限重量。其次，您应该在结果图上运行 Dijkstra 算法。该算法将检查图的每条边。
此外，您可以使用A* (A-star) 算法。
更新：起初我不明白这个问题。正如@amit 所说，这是一个 NP 难题，是 HCP 和 TSP 的组合。也许某种随机搜索算法可以在多项式时间内以高概率解决这个问题。
于 2012-10-12T07:54:02.847 回答