Подтвердить что ты не робот

Алгоритм перемещения графа

У меня есть интересная проблема теории графов. Мне дано дерево T с n узлами и множеством ребер. T, конечно, неориентирован. У каждого края есть вес, который указывает, сколько раз (по крайней мере) его нужно посещать. Мы прогуливаемся от node до node с использованием ребер, и задача состоит в том, чтобы найти минимальное количество необходимых шагов для удовлетворения вышеперечисленных условий. Я могу начать с любого node.

Например, это дерево (вес края в круглых скобках):

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

Я не знаю, как подойти к этому алгоритму. Можно ли найти этот оптимальный тур или мы можем найти это минимальное число не напрямую?

4b9b3361

ОТВЕТЫ

Ответ 1

Добавьте дополнительные графы к вашему графику, соответствующие весу каждого края. (т.е. если a- > b имеет вес 3, то ваш график должен включать в себя 3 непрямых соединения ребер между a и b).

Затем то, что вы пытаетесь найти, на этом графе называется эйлеровой дорожкой.

Эйлерова тропа может быть закрыта (если начало == конец) или открыто (если start!= end).

Закрытые тропы существуют, если все узлы имеют четную степень.

Открытые трейлы существуют, если все узлы, кроме 2, имеют четную степень.

Пути можно найти с помощью алгоритма Fleurys (более быстрые линейные алгоритмы существуют, если это слишком медленно).

Если ваш график не удовлетворяет требованиям для эйлеровой дорожки, просто добавьте наименьшее количество дополнительных ребер до тех пор, пока оно не будет.

Один из способов сделать это - выполнить первый поиск глубины над деревом и отслеживать минимальное количество ребер, которое вы можете добавить к каждому поддереву, чтобы оно имело 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) )