7

作为一个个人复活节项目，我正在尝试在工作中实施一些基于模型的测试。我有一个用 python 实现的图，我需要遍历所有边/执行图的所有转换，至少一次。遍历一条边两次或更多次并不重要，但我需要在同一个节点中开始和结束，并返回一系列边/过渡。

更简单的算法 > 最短序列。

我环顾四周，发现了很多算法，但我找不到适合我的一个/一个组合。如果有人能指出我正确的方向或给我一些关于如何做到这一点的提示，那就太好了。

我的图形实现如下所示：

graph = {
    A : {'IDLE': 't8', 'B': 't2', 'C': 't4'},
    B : {'A': 't3', 'C': 't4', 'IDLE': 't6'},
    C : {'A': 't5', 'IDLE': 't7', 'B': 't2'},
    IDLE : {'A': 't1'}
}

图形

4

4 回答 4

5

方法一

您可以将图 G 更改为新图 G'，其中 G 中的每条边都成为 G' 中的节点。如果“A -> t1 -> B -> t2 -> C”在 G 中对于某些 A、B 和 C 是可能的，则在 G' 中创建从 t1 到 t2 的边。

然后你需要在 G'中找到一个路径覆盖。

方法二

  • 您的位置 P 最初是某个节点 P0（例如空闲）。
  • 对于每条边 T（从 A 到 B），找到从 P 到 A 的任意路线，然后使用 T 到 B。将 P 更新为 B。
  • 最后找到从 P 回到 P0 的任何路线。
于 2012-04-06T11:58:37.420 回答
2

这个问题与旅行商问题不同。相反，它被称为中国邮递员问题。最大的不同是 TSP 想要访问 CPP 想要访问所有边（街道）的所有节点（城市）。

可以在这里找到一个完美的教程：https ://www.datacamp.com/community/tutorials/networkx-python-graph-tutorial

于 2017-11-03T15:05:05.123 回答
1

对于图中的每个 P1、P2 点，找到所有 R 条道路，其中 R 如下所示：

R = (P1, Pf1, ..., Pfn, P2)

对于从 P1 到 P2 的每条 R1、R2 道路，如果 Intersection(R1, R2) 有超过 0 个点（当然 P1 和 P2 除外），则确定哪个更短。如果 R1 的长度小于 R2 的长度，则忘记 R2，否则忘记 R1。

在一次迭代中，您会发现从 P1 到 P2 的最短的完全独立的道路。如果你想穿越一条路，你有点 (P1, ..., Pk) 如果我们选择 Pi，其中 1<= i <= k，我们知道第一个点是 Pi，最后一个点是也被Pi。

假设顺序无关紧要。每当您遍历一个点时，将其标记为已遍历。如果某个点被标记为已遍历，则您不会想再次前往给定点，但如果有必要，您不会介意再次遍历该点。因此，规划的道路将是：Pf1，...，Pfk，Pf1。

对于每个 Pfj，Pfm：

我们此刻在 Pfj。如果Pfm被遍历了那么我们不想再去Pfm，所以我们去下一次迭代

如果不遍历 Pfm，我们有从 Pfj 到 Pfm 的 R1，...，Rq 路。选择未经过点数最多且已经过道路数最少的道路。您需要通过一个聪明的想法来衡量道路中未经过点和经过点的重要性（希望您的权重可以最小化从 Pf1 到 Pf1 的道路总长度）。

请注意，不应将 Pf1 标记为已遍历，因为您希望在算法结束时到达那里。

于 2012-04-06T14:02:09.857 回答
0

我不确定您是想要算法还是想知道如何完成工作。如果是后者，您可以使用networkx。

下载并安装 networkx 后，您可以尝试以下操作

>>> import networkx as nx
>>> DG=nx.DiGraph()
>>> def CycleFrom(G,node):
    return sorted((c for c in nx.simple_cycles(DG) if node in c), key=len)[0]

>>> for (stnode, edges) in graph.items():
    for (ennode,edge) in edges.items():
        DG.add_edge(stnode,ennode,name=edge)


>>> for node in DG.nodes():
    print "Cycles from {0} is {1}".format(node,CycleFrom(DG,node))


Cycles from A is ['A', 'IDLE', 'A']
Cycles from IDLE is ['A', 'IDLE', 'A']
Cycles from B is ['A', 'B', 'A']
Cycles from C is ['A', 'C', 'A']
>>>
于 2012-04-06T12:35:47.913 回答