11

興味深いグラフ理論の問題があります。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

このアルゴリズムにアプローチする方法がわかりません。この最適なツアーを見つけることは可能ですか、それともこの最小数を直接ではなく見つけることができますか?

4

1 に答える 1

6

各エッジの重みに対応する余分なエッジをグラフに追加します。(つまり、a->b の重みが 3 の場合、グラフには a と b の間に 3 つの無向辺接続が含まれている必要があります)。

次に、見つけようとしているものは、このグラフのオイラー トレイルと呼ばれます。

オイラー トレイルは、閉じる (start==end の場合) か、開く (start!=end の場合) ことができます。

すべてのノードの次数が偶数の場合、閉じたトレイルが存在します。

2 を除くすべてのノードの次数が偶数の場合、オープン トレイルが存在します。

フルーリーのアルゴリズムを使用してパスを見つけることができます (これが遅すぎる場合は、より高速な線形アルゴリズムも存在します)。

グラフがオイラー トレイルの要件を満たさない場合は、満たされるまで最小数の余分なエッジを追加します。

これを行う 1 つの方法は、ツリーに対して深さ優先検索を実行し、奇数次数の頂点が 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) )
于 2012-11-25T18:57:48.613 に答える