图组件间路径规划算法

Question

图组件间路径规划算法

4

首先，这是一个作业问题。我有一个布尔矩阵，其中1表示节点，相邻的节点被认为是连接的。例如：

1 0 0 0 1
1 1 1 0 0
1 0 0 1 1
0 0 0 0 0
0 0 0 0 0

根据我所得到的定义，该矩阵包含3个组。左上角的一个组由5个节点组成，右上角的一个组由1个节点组成，下面的一个组由2个节点组成。
我需要编写一个函数来确定必须添加到矩阵中的最少节点数量，以便连接所有分离的组。当一条路径可以从一个组中的任何节点到达另一个组时，两个组就被连接了。

所以，我的问题是希望有人能在算法方面给我指点方向。我考虑如何使用路径查找算法找到两个组之间的最短路径，但不确定如何为矩阵中的每个组执行此操作。如果我使用深度优先遍历来确定单独的组，那么我是否可以为每个组内的任意节点到另一个节点使用路径查找算法？

- user3027689

看起来是一个棘手的问题！一种方法是首先识别这些岛屿，计算这些岛屿之间的成对最短距离，并得到0到1转换数量的上限。然后递归地尝试减少这个数字并查看是否可能。正如我所说，这种方法非常低效，我认为应该有更好的方法。 - Abhishek Bansal

一个不相交集合也适用于查找独立的组。广度优先搜索适用于确定最短路径，因为你可以缓慢地“辐射出去”。我同意@AbhishekBansal，这是一个棘手的问题。 - Tom

2个回答

-1

将每个连通分量(组)看作一个节点。然后可以运行MST (最小生成树)算法来找到连接所有组的最小成本。

复杂度：建立边缘的复杂度=O(M*M)+O(ElgV)（其中M是给定网格上1的数量，需要M*M次操作来查找每对1之间的曼哈顿距离，以查找每对组的曼哈顿距离），而O(ElgV)是查找MST的复杂度。

- Fallen

你正在计算最小生成树的图中，节点和边是什么？即使它们没有被使用，最小生成树是否也会连接中间节点？ - templatetypedef

@templatetypedef: 第一步：将每个连通分量（组）视为一个节点。第二步：在给定的网格上，1的数量为M，需要进行M * M次操作，以找出每对1之间的曼哈顿距离，以便找到每对组之间的曼哈顿距离。在考虑问题中间节点时，我了解到最小生成树在这里行不通:) 我会更新答案。谢谢！ - Fallen

经过查看你们提到的一些内容，我认为这是最好的方法。由于我只需要输出连接所有组件所需的节点数，因此可以计算每个组件最近节点之间的曼哈顿距离，然后从一个组件通过每个其他组件获取最短距离。感谢大家的建议。 - user3027689

1

也许我错过了什么，但是MST信息如何告诉您哪些正方形需要点亮呢？可能有许多相同长度的不同路线连接所有集群，但有些可能比其他路线更好，因为它们之间可以共享1s。此外，为什么最佳结构必须是MST？也许最佳选项会引入一些中间连接点。想想T形状的三个集群。将它们连接成T形状可能比连接两个独立的对更好。 - templatetypedef

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sorin · Accepted Answer

这个通用问题被称为斯坦纳树问题，它是NP完全问题。

有一种算法不是指数级的，但会给出一个次优解。

你可以这样做：计算任意两个组件之间的最短路径，使用初始组件和计算得到的权重进行最小生成树，然后遍历解决方案并消除循环。

由于连接岛屿有很多选项，我建议添加一步来优化连接。

但是对于最优答案的算法：NP完全问题（尝试每种组合）。