图旅行算法

Question

我有一个有趣的图论问题。我得到了一个有n个节点和一组边的树T。当然，T是无定向的。每条边都有权重，指示它(至少)必须被访问多少次。我们使用边从一个节点漫步到另一个节点，任务是找到满足上述条件的最少所需步骤。我可以从任何节点开始。

例如，此树(圆括号中的边权重)：

1-2 (1)

2-3 (1)

3-4 (2)

4-5 (1)

4-6 (1)

我们需要8个步骤来走这棵树。例如: 1->2->3->4->3->4->5->4->6

我不知道如何使用这个算法。有没有可能找到这个最优线路，或者我们能不能直接找到这个最小数量？

Answer 1

将额外的边添加到与每条边的权重对应的图中。(即，如果a->b的权重为3，那么您的图应该包括a和b之间的3个无向边连接)。

那么你要找的东西就是这张图上的欧拉轨迹。

Eulerian轨迹可以是闭合的(如果是start==end)，也可以是开放的(如果start!=end)。

如果所有节点的度数为偶数，则存在闭合轨迹。

如果除2之外的所有节点的度数都是偶数，则存在开放轨迹。

可以使用Fleury算法找到路径(如果速度太慢，也可以使用更快的线性算法)。

如果您的图不满足欧拉轨迹的要求，那么只需添加最小数量的额外边，直到它满足要求为止。

这样做的一种方法是在树上执行深度优先搜索，并跟踪可以添加到每个子树的最小边数，以便它具有0、1或2个奇数次顶点。这应该需要时间与树中节点的数量成线性关系。

示例代码

这段Python代码计算一个图的最短步数。(要构建该图，您应该将其视为有根的图，并为远离根的每条边添加边)

from collections import defaultdict
D=defaultdict(list)
D[1].append((2,1))
D[2].append((3,1))
D[3].append((4,2))
D[4].append((5,1))
D[4].append((6,1))
BIGNUM=100000

class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if not self.memo.has_key(args):
            self.memo[args] = self.fn(*args)
        return self.memo[args]

@Memoize
def min_odd(node,num_odd,odd,k):
    """Return minimum cost for num_odd (<=2) odd vertices in subtree centred at node, and using only children >=k

    odd is 1 if we have an odd number of edges into this node from already considered edges."""
    edges=D[node]
    if k==len(edges):
        # No more children to consider, and no choices to make
        if odd:
            return 0 if num_odd==1 else BIGNUM
        return 0 if num_odd==0 else BIGNUM

    # We decide whether to add another edge, and how many of the odd vertices to have coming from the subtree
    dest,w0 = edges[k]
    best = BIGNUM
    for extra in [0,1]:
        w = w0+extra
        for sub_odd in range(num_odd+1):
            best = min(best, w + min_odd(dest,sub_odd,w&1,0) + min_odd(node,num_odd-sub_odd,(odd+w)&1,k+1) )

    return best

root = 1
print min( min_odd(root,2,0,0),min_odd(root,0,0,0) )