1

我有图 1 中的图（第一张图像），并希望连接红色节点以具有循环，但循环不必像图2和图3那样是哈密顿量（最后两张图片）。这个问题的搜索空间比 TSP 大得多，因为我们可以访问一个节点两次。像 TSP 一样，不可能在一个大图中评估所有组合，我应该尝试启发式，但问题是，与 TSP 不同，循环或旅行的长度在这里不是固定的。因为，访问所有蓝色节点不是强制性的，这导致长度可变，包括一些蓝色节点。如何每次都生成一个可能的“有效”组合进行评估？我的意思是，一个循环可以是{A，e，B，l，k，j，D，j，k，C，g，f，e}或{A，e，B，l，k，j，D， j, i, h, g, C, g, f, e}，但不是 {A, e, B, l, k, C, g, f, e} 或 {A, B, k, C, i, D}。

更新： 最终目标是根据长度和风险评估哪个周期是最优/接近最优的（见下文）。所以我不仅要尽量减少长度，还要尽量减少风险。除非您知道其所有节点的顺序，否则这将导致无法评估循环风险。希望这能澄清为什么我不能在生成过程的中间评估新周期。我们可以：

  • 一个一个地生成和评估可能的循环；
  • 或生成所有可能的循环，然后进行评估。

风险定义： 假设循环是将主节点（红色节点之一）连接到所有其他红色节点的环。如果环的任何部分（边缘）发生故障，则不应从主节点断开任何红色节点（这是理想的）。然而，有些边我们必须通过两次（由于没有连接所有红色节点的哈密顿循环），如果这些边出现故障，一些红色节点可能会完全断开连接。因此，循环风险是风险边缘长度的总和（我们在环/巡回中有两次）乘以在切割每个风险边缘的情况下我们丢失的红色节点数。

图1

图 2 图 3

我正在处理的 3D 图的真实示例包括 5 个红色节点和 95 个蓝色节点，如下所示： 在此处输入图像描述

这里是包含上图邻接矩阵的 Excel 表的链接（前五个节点为红色，其余为蓝色）。

4

1 回答 1

1

经过更多思考，我决定重写我的解决方案可能会更好，因为您可以使用红色节点两次，这使得我最初绘制红色节点之间路径的想法效率低下。但是，它并没有完全浪费，因为红色节点之间的蓝色节点很重要。

您实际上可以使用 BFS 的修改版本来解决这个问题，更不用说回溯算法。对于每个唯一的分支，都存储了以下信息，其中大部分只是为了更快地拒绝而以更多空间为代价，实际上只需要前两项：

  • 完整的当前路径。（仅包含起始红色节点的列表）
  • 剩余的红色节点。（最初所有红色节点）
  • 最后一个红色节点。（最初是起始红色节点）
  • 自上一个红色节点以来的蓝色节点集。（最初为空）
  • 计数为 1 的节点集。（最初为空）
  • 计数为 2 的节点集。（最初为空）

该算法从单个节点开始，然后使用 BFS 或 DFS 扩展相邻节点，重复此过程，直到结果是有效的游览或要扩展的节点被拒绝。所以基本的伪代码（当前路径和剩余的红点）如下所示。其中 rn 是红色节点的集合，t 是有效路径的列表，p/p2 是节点的路径，r/r2 是红色节点的集合，v 是要扩展的节点，a 是可能的节点扩展到。

function PATHS2HOME(G,rn)
    create a queue Q
    create a list t
    p = empty list
    v ← rn.pop()
    r ← rn
    add v to p
    Q.enqueue((p,r))
    while Q is not empty
        p, r ← Q.dequeue()
        if r is empty and the first and last elements of p are the same:
            add p to t
        else
            v ← last element of p
            for all vertices a in G.adjacentVertices(v) do 
                if canExpand(p,a)
                    p2 ← copy(p)
                    r2 ← copy(r)
                    add a to the end of p2
                    if isRedNode(a) and a in r2
                        remove a from r2
                    Q.enqueue( (p2,r2) )
    return t

以下条件可防止节点扩展。可能不是一个完整的列表。

  • 红色节点：
    • 如果它在计数为 2 的节点集中。这是因为红色节点会被使用两次以上。
    • 如果等于最后一个红色节点。当一个红色节点与其他三个蓝色节点相邻时，这可以防止“奇怪的”旅行。因此，红色节点 A 与蓝色节点 b、c 和 d 相邻。然后您将结束一个巡演，其中部分巡演看起来像 bAcAd。
  • 蓝色节点：
    • 如果它在计数为 2 的节点集中。这是因为红色节点会被使用两次以上。
    • 如果它在自上一个红色节点以来的蓝色节点集中。这是因为它会导致红色节点之间的蓝色节点循环。

可能的优化：

  • 您可以绘制出红色节点之间的路径，使用它来构建后缀树，它显示了给定以下路径可以到达的红色节点 Like。这样做的好处是，如果扩展路径导致已经访问过两次的红色节点，您可以避免扩展节点。因此，这只是一个有用的检查，一旦至少 1 个红色节点被访问过两次。
  • 使用算法的并行版本。单个线程可能正在访问队列，并且队列中的元素之间没有交互。虽然我怀疑可能有更好的方法。有可能将运行时间从数百秒缩短到几秒。尽管这取决于并行化水平和效率。您也可以将其应用于先前的算法。实际上我改用这个算法的原因几乎被否定了
  • 您可以使用堆栈而不是队列。这里的主要好处是通过使用深度优先的方法，队列的大小应该保持相当小。
于 2013-04-17T17:16:36.313 回答