在图中查找周期（不一定是哈密顿量或访问所有节点）-Java 学习之路

我有图像一个在图1（第一图像）和要连接的红色节点具有周期，但周期不必是哈密顿像图2和图3（最后两个图像） . 这个问题比TSP有更大的搜索空间，因为我们可以访问节点两次 . 像TSP一样，不可能在大图中评估所有组合，我应该尝试启发式，但问题是，与TSP不同，周期或游览的长度在这里不固定 . 因为访问所有蓝色节点不是强制性的，并且这导致具有可变长度，包括一些蓝色节点 . 如何在每次评估时生成可能的"valid"组合？我的意思是，一个周期可以是{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} .

Update: 最终目标是根据长度和风险评估哪个周期最佳/接近最佳（见下文） . 因此，我不仅要缩短长度，还要尽量降低风险 . 这导致无法评估循环风险，除非您知道其所有节点序列 . 希望这澄清了为什么我无法在其生成过程中评估新循环 . 我们可以：

逐个生成并评估可能的周期;
或生成所有可能的周期，然后进行评估 .

Definition of the risk: 假设循环是一个环，它将主节点（一个红色节点）连接到所有其他红色节点 . 如果环的任何部分（边缘）发生故障，则不应从主节点断开红色节点（这是期望的） . 然而，我们必须传递两次边缘（由于没有连接所有红色节点的哈密尔顿循环），并且在这些边缘失效的情况下，一些红色节点可能完全断开 . 因此，周期风险是风险边缘长度的总和（我们在环/巡回赛中有两次）乘以我们在削减每个风险边缘时丢失的红色节点数 .

我正在研究的包含5个红色节点和95个蓝色节点的3D图形的真实示例如下：
enter image description here

并且here链接到包含上图的邻接矩阵的Excel工作表（前五个节点为红色，其余为蓝色） .

1 回答

1
经过多次反思，我认为重写我的解决方案可能更好，因为你可以使用红色节点两次，这使得我最初的想法是将红色节点之间的路径映射效率低下 . 但是，它并没有完全浪费，因为红色节点之间的蓝色节点很重要 .

你实际上可以使用BFS的修改版本解决这个问题，因为更多的是backtracking algorithm . 对于每个唯一分支，存储以下信息，其中大部分仅允许以更多空间为代价更快地拒绝，实际上仅需要前两个项目：
- 完整的当前路径 . （仅包含起始红色节点的列表）
- 剩余的红色节点 . （最初都是红色节点）
- 最后一个红色节点 . （最初是红色节点）
- 自上一个红色节点以来的蓝色节点集 . （最初是空的）
- 计数为1的节点集 . （最初为空）
- 计数为2的节点集 . （最初为空）
该算法以单个节点开始，然后使用BFS或DFS扩展相邻节点，这将重复直到结果是有效的巡回或者要扩展的节点被拒绝 . 所以基本的psudoish代码（当前路径和剩余的红点）看起来如下所示 . 其中RN是集红色节点，t为有效之旅的名单，P / P2是节点的路径，R / r2为一组红色节点，v是要扩展的节点，一个是可能的节点扩展到 .
```
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的节点集中 . 这是因为红色节点的使用次数将超过两次 .
- 如果它等于最后一个红色节点 . 当红色节点与其他三个蓝色节点相邻时，这可以防止"odd"巡视 . 因此，说红色节点A与蓝色节点b，c和d相邻 . 然后你将结束巡回演出，其中部分巡演看起来像b-A-c-A-d .
- 蓝色节点：
- 如果它位于计数为2的节点集中 . 这是因为红色节点的使用次数将超过两次 .
- 如果它位于自上一个红色节点以来的蓝色节点集中 . 这是因为它会导致红色节点之间出现蓝色节点循环 .
可能的优化：
- 您可以绘制红色节点之间的路径，使用它来构建后缀树的某些内容，显示可以通过以下路径获得的红色节点 . 这样做的好处是，如果扩展的路径导致已经访问过两次的红色节点，则可以避免扩展节点 . 因此，一旦至少有1个红色节点，这只是一个有用的检查访问了两次 .
- 使用算法的并行版本 . 单个线程可以访问队列，队列中的元素之间没有交互 . 虽然我怀疑可能有更好的方法 . 有可能将运行时间减少到几秒而不是几百秒 . 虽然这取决于并行化水平和效率 . 您也可以将其应用于先前的算法 . 实际上，我切换到使用这种算法的原因几乎被否定了
- 您可以使用堆栈而不是队列 . 这里的主要好处是使用深度优先方法，队列的大小应该保持相当小 .
回复于 2024-05-15T10:29:14+08:00

在图中查找周期（不一定是哈密顿量或访问所有节点）

1 回答

相关问题