1

我正在将图形算法应用于可能的非标准应用程序。我有链接在一起的图，并试图找到通过它们的前 K 个最短节点不相交路径。希望我能解释一下：举个例子，假设我有两个相当简单的图表，带有开始和结束。在我的例子中，这些图表经历了阶段（从左到右）并且都具有相同数量的阶段。我可以使用 Dijkstra 或其他东西在每个图中找到最短路径，但它们链接在一起，使得第一个图中的某些节点链接到第二个图中的匹配节点。选择一个需要选择另一个。我的第一个想法是将两个图合并为一个，所有可能的组合都得到一个节点。因此，如果在图一的某个阶段，节点是 A、B、C，图二有 D、E、F，如果 C 和 F 是链接的，选项有 AD、AE、BD、BE、CF。这可以很好地找到单一的最佳路径。当我应用 Suurballe 算法来查找 K 个最佳节点不相交路径时，问题就出现了，因为两个节点不相交路径可以选择 AD 和 AE。这些是组合图中的节点不相交，但在原始问题中不是（它们共享 A）。这类问题是否有任何现有技术，或者任何人都可以想到一个简单的解决方案？

图片示例：在以下约束下通过这两个图找到 K 个最小成本路径（两条路径的总和），如果您在一个图中选择彩色节点，则必须在另一个图中选择相同的颜色节点。即使未显示，边缘也会被加权。

在此处输入图像描述

响应以下答案的另一个示例（示例2）： 在此处输入图像描述

4

1 回答 1

0

我不确定这个领域的“现有技术”，但我想我可以想到一个“直截了当的解决方案”。

  1. 分别在图 1（第一个图）中找到最佳路径，如“图片示例”所示。计算这条路径的成本函数，比如 CF1。
  2. 在图 1 的最佳路径中找到彩色节点的数量。
  3. 对于图 1 中的所有彩色节点，从图 2 中删除所有备用连接，即确保图 2 中的路径必须经过图 1 中使用的彩色节点。
  4. 在图 2 中找到最优路径并计算其成本函数，例如 CF2。
  5. 计算 CF1 + CF2
  6. 重复步骤 1 到 5，但这次从图 2 开始，然后将图 1 的彩色节点与图 2 的初始最优路径匹配。

CF1+CF2 的最小值将为您提供一组可行路径。

基本上，您计划其中一个图的路径并让另一个图符合其链接节点集并检查组合成本函数。然后重复另一个图表。找到最有效的组合。

一般来说，对于 n 个图，您必须执行 n^2 次最短路径计算，这显然非常糟糕。但它应该工作，作为一个天真的想法。

++++++++++++++++++++++

这是我对之前加权图算法的修改版本：

假设：我们正在使用“n”个图，它们都被加权，并且它们都包含相等且固定数量的“阶段”。

所有的起始节点都被描述为 S1、S2、S3……。锡。所有的终端节点都被描述为 e1, e2, e3….. en。

  1. 启动一个空的优先级队列（PQ）[最好使用二进制/斐波那契最小堆]，它将包含路径（节点集合），并且它们的相应优先级将由它们的路径权重的累积和表示]

  2. 插入所有起始节点 - S1、S2、S3……。Sn变成PQ，每个单独节点的优先级设置为零。

  3. 弹出权重最小的路径（比如它属于图形编号“k”）并展开它的子节点。让有'p'个子节点。[如果没有更多阶段可以扩展，请从优先级队列中删除该路径。这样，如果队列的总大小变为零，那么 S 和 e 之间就没有可行路径]

  4. 对于所有 i 不等于 k ​​的 i = 1 到 n，重复：

    4a。检查剩余 (n-1) 个图中的哪些 p 路径是可行的。

    4b。将所有可行的路径插入到 PQ（在计算它们的优先级之后）。

    4c。如果其中一条可行路径以 ek 结束：则将该路径标记为“PathOptimal”并转到 5。否则：转到 3。

  5. 对于 i = 1 到 n 对于所有 i 不等于 k ​​：在每个图中针对 'PathOptimal' 找到相应的路径并将它们报告为输出。

在这里，必须正确实现路径权重的概念。路径权重将等于：该路径中包含的边的权重之和 + 剩余 (n-1) 图中所有兄弟路径中包含的边的权重之和。

可行性概念将成为您的业务规则，即如果子节点是彩色节点，则所有其他 (n-1) 图中先前路径的相应子节点必须具有相同的颜色。如果它不是彩色节点，那么它的兄弟节点必须是非彩色的。

[如果你发现算法中有任何明显的缺陷，请告诉我，因为我只是编造的。另外，由于这是从 Dijkstra's 大量借来的，如果你能想出一个加快速度的方法，请告诉我。]

PS：-但是，我必须提到，鉴于您的问题范围，我宁愿使用遗传算法来解决这个问题，而不是采用确定性方法。

于 2013-09-05T07:34:44.627 回答