Ответ 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) )