1

这本质上是用尽可能少的道路连接 n 个目的地的问题。

输入是一组顶点 (a,b, ... , n)

两个顶点之间的边的权重很容易计算（例如两个顶点之间的笛卡尔距离）

我想要一种算法，它给定欧几里得空间中的一组顶点，返回一组边，这些边将构成一个连通图，并且边的总权重尽可能小。

在图形语言中，这是连通图的最小生成树。

用蛮力我会：

  1. 定义所有顶点之间的所有可能边 - 假设你有 n 个顶点，那么你在完整图中有 n(n-1)/2 个边
  2. 可能的边缘可以打开或关闭（2 个状态）
  3. 遍历所有可能的边缘开/关组合：2^(n(n-1)/2)！
  4. 忽略所有不会连接图形的
  5. 从剩余的组合中，找到边权重之和最小的组合

我知道这是一个 NP-Hard 问题。但是，实际上对于我的应用程序，我最多有 11 个顶点。我希望能够在典型的现代智能手机上解决这个问题，或者至少在小型服务器上解决这个问题。

作为第二种变体，我想获得相同的目标，但限制是每个顶点最多连接到另一个顶点。本质上，只要图是连接的，就可以从任何点开始，在任何其他点结束，从而获得一条迹线。没有必要回到你开始的地方。在图形语言中，这是开放的欧几里得旅行商问题。

一些伪代码算法会很有帮助。

4

4 回答 4

1

好的，对于第一个问题，您必须构建一个最小生成树。有几种算法可以做到这一点，Prim和Kruskal。但是，请查看第一个链接以获取完整图表的处理，这是您的情况。

对于第二个问题，它变得有点复杂。这个问题变成了一个开放的旅行推销员问题（oTSP）。阅读上一个链接可能集中在欧几里得和不对称。

问候

于 2013-09-27T09:09:24.840 回答
0

也许你可以尝试一个贪心算法：

1. Create a list sortedList that stores each pair of nodes i and j and is sorted by the 
   weight w(i,j).
2. Create a HashSet connectedNodes that is empty at the beginning
3. while (connectedNodes.size() < n)
     element := first element of sortedList
     if (connectedNodes.isEmpty())
       connectedNodes.put(element.nodeI);
       connectedNodes.put(element.nodeJ);
       delete element from sortedList
     else 
       for(element in sortedList) //start again with the first
         if(connectedNodes.get(element.nodeI) || connectedNodes.get(element.nodeJ))
           if(!(connectedNodes.get(element.nodeI) && connectedNodes.get(element.nodeJ)))
              //so it does not include already both nodes
              connectedNodes.put(element.nodeI);
              connectedNodes.put(element.nodeJ);
              delete element from sortedList
              break;
           else 
              continue;

所以我稍微解释一下第 3 步：

您添加尽可能长的节点，直到所有节点都相互连接。connectedNodes可以确定该图是连接的，因为您只需添加一个节点，如果他与列表中已经存在的另一个节点有连接。

所以这个算法是贪心的，它不能确保解决方案是最优的。但这是一个相当好的近似值，因为它总是取最短边（因为sortedList是按边的权重排序的）。

哟不要进去duplicates，connectedNodes因为它是一个HashSet，这也使运行时更快。

总而言之，运行时间应该是 O(n^2)，因为在 O(n^3) 的开头和低于它的排序，因为在最坏的情况下，你会在每个步骤中运行大小为 n^2 的整个列表你做了 n 次，因为你在每一步中添加了一个元素。

但更有可能的是，你发现一个元素比 O(n^2) 快得多，我认为在大多数情况下它是 O(n)。

于 2013-09-27T09:13:03.027 回答
0

对于第一个问题，有一个O(n^2 * 2^n)时间算法。基本上，您可以使用动态规划来减少搜索空间。假设所有顶点的集合是V，因此状态空间由 的所有子集组成V，目标函数f(S)是 中连接顶点的边的最小权重之和S。对于每个状态S，您可以枚举所有的边(u, v)，其中u是 inS和vis in V - S，并进行更新f(S + {v})。在检查所有可能的状态后，最佳答案是f(V)。

下面是说明这个想法的示例代码，但它是以向后的方法实现的。

const int n = 11;
int weight[n][n];
int f[1 << n];
for (int state = 0; state < (1 << n); ++state)
{
    int res = INF;
    for (int i = 0; i < n; ++i)
    {
        if ((state & (1 << i)) == 0) continue;
        for (int j = 0; j < n; ++j)
        {
            if (j == i || (state & (1 << j)) == 0) continue;
            if (res > f[state - (1 << j)] + weight[i][j])
            {
                res = f[state - (1 << j)] + weight[i][j];
            }
        }
    }
    f[state] = res;
}
printf("%d\n", f[(1 << n) - 1]);

对于第二个问题，抱歉我不太明白。也许你应该提供一些例子？

于 2013-09-27T10:01:40.223 回答
0

您可以使用 optimap tsp 求解器（来自 gebweb）或线性程序求解器来求解 travelsalesman 问题和汉密尔顿路径问题。但是第一个问题似乎要求最小生成树，也许问题标签是错误的？

于 2013-09-27T09:47:21.740 回答