3

我有一个有向哈密顿循环：

[..., a, b, ... , c, d, ..., e, f, ...]

其中b = next(a),d = next(c)和f = next(e).

假设我删除边 (a, b)、(c, d) 和 (e, f)。

问题：如何生成图的所有可能重组，使其保持哈密顿循环（请记住，我可能必须颠倒其中一个部分的顺序以固定方向）？

我知道的

我知道通过删除 n 边可以达到的新哈密顿循环数是double-factorial(n-1). 我也知道，如果我要删除两个连续的边，我会得到重复的解决方案（我很好......相对于唯一循环它们应该是最小的，并且它保持生成的代码干净）。

我尝试过的（粗略的伪代码）

考虑这一点的一种方法是，任何产生的哈密顿循环都必须保留在跳到新的部分之前必须沿着断开连接图的部分移动的属性。

因此，例如，考虑上面的循环（其中n = 3），有以下 3 个部分：

[b, ..., c]
[d, ..., e]
[f, ..., a]

因此，假设我的新解决方案如下所示：

[..., a, d, ...]

我知道 e 是我的终端顶点列表中必须出现的下一个顶点。

因此，使用这个想法，Python 将是这样的：

from itertools import permutations

def hamiltonian_cycles(l, s=None, r=None):
    if s is None:
        s = [l[0]]
    if r is None:
        r = l[1:]
    if not r:
        yield s
    else:
        for permutation in permutations(r):
            s1 = s[:] + [permutation[0]]
            for cycle in hamiltonian_cycles(l, s1, permutation[1:]):
                yield cycle
            s2 = s[:] + [(permutation[0][1], permutation[0][0])]
            for cycle in hamiltonian_cycles(l, s2, permutation[1:]):
                yield cycle

>>> l = [('f', 'a'), ('b', 'c'), ('d', 'e')]
>>> for cycle in hamiltonian_cycles(l):
...    print(cycle)
[('f', 'a'), ('b', 'c'), ('d', 'e')]
[('f', 'a'), ('b', 'c'), ('e', 'd')]
[('f', 'a'), ('c', 'b'), ('d', 'e')]
[('f', 'a'), ('c', 'b'), ('e', 'd')]
[('f', 'a'), ('d', 'e'), ('b', 'c')]
[('f', 'a'), ('d', 'e'), ('c', 'b')]
[('f', 'a'), ('e', 'd'), ('b', 'c')]
[('f', 'a'), ('e', 'd'), ('c', 'b')]

不过，这看起来很丑陋并且停止工作n=3，因此是这个问题。

为什么我不想使用 BFS/DFS

我需要一个生成器，它在删除的边数上是线性的，而不是在总边数 + 顶点数上。

4

2 回答 2

2

多亏了这里有用的答案，这是执行此操作的代码。

from itertools import chain, permutations, product

def new_edge_sets(deleted_edges):

    def edges_to_pieces(l):
        new_list = []
        n = len(l)
        for i in xrange(-1,n-1):
            new_list.append((l[i%n][1], l[(i+1)%n][0]))
        return new_list

    def permute(it):
        return product(*(permutations(i) for i in it))

    def permute2(it):
        return chain.from_iterable(permute(p) for p in permutations(it))

    def pieces_to_edges(p):
        new_list = []
        n = len(p)
        for i in xrange(n):
            new_list.append((p[i%n][1], p[(i+1)%n][0]))
        return new_list

    def permute3(s):
        return (pieces_to_edges(s[:1] + list(p)) for p in permute2(s[1:]))

    return permute3(edges_to_pieces(deleted_edges))

例子：

>>> deleted_edges = [('a', 'b'), ('c', 'd'), ('e', 'f'), ('g', 'h')]
>>> l = list(new_edge_sets(deleted_edges))
>>> len(l)
48
>>> for new_edges in l:
...     print(new_edges)
[('a', 'b'), ('c', 'd'), ('e', 'f'), ('g', 'h')]
[('a', 'b'), ('c', 'd'), ('e', 'g'), ('f', 'h')]
[('a', 'b'), ('c', 'e'), ('d', 'f'), ('g', 'h')]
[('a', 'b'), ('c', 'e'), ('d', 'g'), ('f', 'h')]
[('a', 'c'), ('b', 'd'), ('e', 'f'), ('g', 'h')]
[('a', 'c'), ('b', 'd'), ('e', 'g'), ('f', 'h')]
[('a', 'c'), ('b', 'e'), ('d', 'f'), ('g', 'h')]
[('a', 'c'), ('b', 'e'), ('d', 'g'), ('f', 'h')]
[('a', 'b'), ('c', 'f'), ('g', 'd'), ('e', 'h')]
[('a', 'b'), ('c', 'f'), ('g', 'e'), ('d', 'h')]
[('a', 'b'), ('c', 'g'), ('f', 'd'), ('e', 'h')]
[('a', 'b'), ('c', 'g'), ('f', 'e'), ('d', 'h')]
[('a', 'c'), ('b', 'f'), ('g', 'd'), ('e', 'h')]
[('a', 'c'), ('b', 'f'), ('g', 'e'), ('d', 'h')]
[('a', 'c'), ('b', 'g'), ('f', 'd'), ('e', 'h')]
[('a', 'c'), ('b', 'g'), ('f', 'e'), ('d', 'h')]
[('a', 'd'), ('e', 'b'), ('c', 'f'), ('g', 'h')]
[('a', 'd'), ('e', 'b'), ('c', 'g'), ('f', 'h')]
[('a', 'd'), ('e', 'c'), ('b', 'f'), ('g', 'h')]
[('a', 'd'), ('e', 'c'), ('b', 'g'), ('f', 'h')]
[('a', 'e'), ('d', 'b'), ('c', 'f'), ('g', 'h')]
[('a', 'e'), ('d', 'b'), ('c', 'g'), ('f', 'h')]
[('a', 'e'), ('d', 'c'), ('b', 'f'), ('g', 'h')]
[('a', 'e'), ('d', 'c'), ('b', 'g'), ('f', 'h')]
[('a', 'd'), ('e', 'f'), ('g', 'b'), ('c', 'h')]
[('a', 'd'), ('e', 'f'), ('g', 'c'), ('b', 'h')]
[('a', 'd'), ('e', 'g'), ('f', 'b'), ('c', 'h')]
[('a', 'd'), ('e', 'g'), ('f', 'c'), ('b', 'h')]
[('a', 'e'), ('d', 'f'), ('g', 'b'), ('c', 'h')]
[('a', 'e'), ('d', 'f'), ('g', 'c'), ('b', 'h')]
[('a', 'e'), ('d', 'g'), ('f', 'b'), ('c', 'h')]
[('a', 'e'), ('d', 'g'), ('f', 'c'), ('b', 'h')]
[('a', 'f'), ('g', 'b'), ('c', 'd'), ('e', 'h')]
[('a', 'f'), ('g', 'b'), ('c', 'e'), ('d', 'h')]
[('a', 'f'), ('g', 'c'), ('b', 'd'), ('e', 'h')]
[('a', 'f'), ('g', 'c'), ('b', 'e'), ('d', 'h')]
[('a', 'g'), ('f', 'b'), ('c', 'd'), ('e', 'h')]
[('a', 'g'), ('f', 'b'), ('c', 'e'), ('d', 'h')]
[('a', 'g'), ('f', 'c'), ('b', 'd'), ('e', 'h')]
[('a', 'g'), ('f', 'c'), ('b', 'e'), ('d', 'h')]
[('a', 'f'), ('g', 'd'), ('e', 'b'), ('c', 'h')]
[('a', 'f'), ('g', 'd'), ('e', 'c'), ('b', 'h')]
[('a', 'f'), ('g', 'e'), ('d', 'b'), ('c', 'h')]
[('a', 'f'), ('g', 'e'), ('d', 'c'), ('b', 'h')]
[('a', 'g'), ('f', 'd'), ('e', 'b'), ('c', 'h')]
[('a', 'g'), ('f', 'd'), ('e', 'c'), ('b', 'h')]
[('a', 'g'), ('f', 'e'), ('d', 'b'), ('c', 'h')]
[('a', 'g'), ('f', 'e'), ('d', 'c'), ('b', 'h')]
于 2013-08-16T14:21:50.080 回答
1

To generate all the possible hamiltonian cycles. give it a try

MatrixOperations module made for self convinence with matrix operations like printing and stuff.u can try with normal print statement 
from matrix import MatrixOperations
A=[[0,1,0,1,1,0,0],[1,0,1,0,0,0,0],[0,1,0,1,0,0,1],[1,0,1,0,1,0,1],[1,0,0,1,0,1,0],[0,0,0,0,1,0,1],[0,0,1,1,0,1,0]]
print("THE ADJACENCY MATRIX\n");MatrixOperations.PrintMatrix(A)
n=len(A)
X=[]
vis=[0 for i in range(n)]
def hamiltonian(vis,A,i):
    vis[i]=1
    if(len(X)==n-1 and A[i][0]==1):
        print (X)   
    for j in range(0,n):
        if (vis[j]==0 and A[i][j]==1):
            X.append(j)

            #print(X) this print shows the whole tracing process
            hamiltonian(vis,A,j)
            
    if(len(X)>0):
        del X[-1]
        vis[i]=0
print("\nPossible Hamiltonian cycles")
hamiltonian(vis,A,0)
于 2017-06-12T10:00:46.767 回答