10

这就是问题：

我有 n 个点 (p1, p2, p3, .. pn)，每个点都可以以确定的成本 x 连接到任何其他点。

每个点都属于一组点类型中的一个（例如“A”“B”“C”“D”......）。

该方法的输入是我要遵循的路径，例如“ABCADB”。

输出是连接我在输入中给出的类型的点的最短路径，例如“p1-p4-p32-p83-p43-p12”，其中 p1 是 A 型，p4 是 B 型，p32 是 C-型，p83 为 A 型，p43 为 D 型，p12 为 B 型。

“简单”的解决方案包括计算所有可能的路径，但计算成本非常高！

有人能找到更好的算法吗？

正如我在标题中所说，我不知道它是否存在！

更新：

阻止我使用 Dijkstra 和其他类似算法的关键是我必须根据类型链接这些点。

作为输入，我有一个类型数组，我必须按该顺序链接。

这是 Kent Fredric 的图片（非常感谢），它描述了初始情况（红色允许链接）！

替代文字

一个真实的例子：

一个人早上想去教堂，下午去餐馆，最后去博物馆。

地图上有 6 座教堂、30 间餐厅和 4 座博物馆。

他希望教堂-休息-博物馆的距离尽可能小。

4

8 回答 8

7

您可以使用 Floyd–Warshall 算法。这是维基百科给出的伪代码：

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to 
   (infinity if there is none).
   Also assume that n is the number of vertices and edgeCost(i,i)=0
*/

int path[][];

/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
   from i to j using intermediate vertices (1..k-1).  Each path[i][j] is initialized to
   edgeCost(i,j) or infinity if there is no edge between i and j.
*/

procedure FloydWarshall ()
    for k: = 1 to n
        for each (i,j) in {1,..,n}2
            path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

我不得不为关于同样问题的算法课程编写一个程序。这个算法就像一个魅力！祝你好运。

于 2009-07-17T12:51:34.987 回答
4

有许多算法会比计算所有可能的路径做得更好。 广度优先搜索是我想到的算法系列的基本起点，最佳优先搜索是合适的，因为您定义了顶点成本，如果您可以获得有关问题空间的更多信息，您可以使用A*或Dijkstra 算法。（在每种情况下，从一组允许的起始节点中查找路径。）

重新编辑：您的路径约束（您需要满足的节点类型数组）不会阻止您使用这些算法；恰恰相反，它可以帮助他们更好地工作。您只需要以允许合并路径约束的方式实现它们，将搜索中每个步骤的可用顶点限制为给定约束有效的顶点。

于 2009-07-17T12:40:24.063 回答
4

正如 Jan 所提到的，您只需要一个普通的无聊最短路径算法（如 Dijkstra 或Floyd算法）；但是，您需要转换输入图，以便输出路径尊重您的路径约束。

给定路径约束：A - B - A

创建一个新图并使用新标签（如 a_01）G将所有顶点A插入其中。G然后插入所有顶点B并将顶点与顶点G连接（边应指向新插入的节点），从原始图中复制成本。然后，您重复此步骤（和任何其他路径组件），将新插入的顶点连接到. 因此，您创建了一个图，其中只有存在的路径满足路径约束。然后，您可以使用正常的最短路径算法。ABAB

关键的见解是，当您重新访问一个类时，您实际上是在访问一组不同的节点，并且您只需要连接相邻节点类的边。

于 2009-07-17T12:58:32.807 回答
4

替代文字

这就是我目前解释您的问题的方式。

红色箭头是我手动跟踪符合给定排序约束的路径。

没有提供成本，但假设所有链接都会产生成本，并且链接成本是不同的。

如果这准确地描述了您要解决的方案，请这样说，以便其他人可以更好地回答问题。

于 2009-07-17T13:15:18.640 回答
2

在修改您的问题时，您似乎要求每个字母一个节点 - 在这种情况下，它是一个简单的动态编程解决方案：计算每对节点之间满足序列开头的所有长度为 1 的最短路径。然后对于所有节点对有 k 个所有这样的路径，为 k+1 构造是微不足道的。

于 2009-07-17T12:54:07.250 回答
2

这是具有动态编程解决方案的伪代码：

n - length of desired path
m - number of vertices
types[n] // desired type of ith node
vertice_types[m]
d[n][m] // our DP tab initially filled with infinities

d[0][0..m] = 0
for length from 1 to n 
  for b from 0 to m
    if types[length] == vertice_types[b]
      for a from 0 to m
        if types[length-1] == vertice_types[a]
          d[length][b] = min(d[length][b], d[length-1][a] + cost(a,b))

您的最低成本路径是 min(d[n][0..m])

您可以将 d 表的大小减少到 2 行，但它会混淆解决方案

于 2009-07-17T14:01:19.410 回答
1

据我了解您的问题，您需要有向图中的最短路径。http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm应该给你一个想法。

问候，扬

于 2009-07-17T12:40:25.610 回答
1
  1. 计算每个等价块内的所有最短路径对。
  2. 现在构建一个没有类间边的图，但其类之间的边与该类中的最短路径匹配，从而导致另一个类的特定节点。

希望这很清楚。

该解决方案不是特别有效，但显然是多项式的。

于 2009-07-17T12:44:59.213 回答