0

以下に示すようなツリーがあります。

  • 赤は特定のプロパティがあることを意味し、塗りつぶされていないものはそれがないことを意味します。Redチェック を最小限にしたい。
    1. Redすべての先祖もそうである場合Red(再度チェックする必要はありません)。
    2. Not Redすべての子孫がNot Red.
  • 木の深さは ですd。
  • 木の幅は ですn。

  • 子ノードの値は親よりも大きいことに注意してください。

    • 例: 以下のツリーでは、
      • ノード '0' には子 [1, 2, 3] があります。
      • ノード '1' には子 [2, 3] があります。
      • ノード '2' には子 [3] があり、
      • ノード '4' には子 [] があります (子なし)。

    • したがって、子は次のように構築できます。

      if vertex.depth > 0:
    vertex.children = [Vertex(parent=vertex, val=child_val, depth=vertex.depth-1, n=n) for child_val in xrange(self.val+1, n)]
else:
    vertex.children = []

ツリーの例を次に示します。

木

Redノード数を数えようとしています。木の奥行きも幅も大きくなります。したがって、一種の深さ優先検索を実行し、さらに上記のプロパティ 1 と 2 を使用したいと考えています。

そのツリーをトラバースするアルゴリズムを設計するにはどうすればよいですか?

PS: 私はこれに [python] というタグを付けましたが、アルゴリズムの概要は何でも構いません。

更新と背景

  1. プロパティ チェックを最小限に抑えたい。
  2. プロパティ チェックは、ツリーのパスから構築された 2 部グラフの接続性をチェックしています。 例：
    • サンプル ツリーの左下のノードのパスは[0, 1] です。
    • 二部グラフに集合RとCサイズrとがあるとしcます。(ツリーの幅は であることに注意してくださいn=r*c)。
    • パスから、完全なグラフから開始し、パス内のすべての値のエッジ (x, y) を次のように削除して、グラフのエッジに到達しますx, y = divmod(value, c)。

プロパティ チェックの 2 つのルールは、グラフの接続性に由来します。- エッジ [a, b, c] を削除してグラフを切断する場合、追加のエッジ d [a, b, c, d] を削除してグラフを切断する必要があります (ルール 2)。

更新 2

だから私が本当にやりたいことは、[0..n] から d 要素を選択するすべての組み合わせをチェックすることです。ツリー構造はいくらか役に立ちますが、最適なツリー トラバーサル アルゴリズムを取得したとしても、チェックする組み合わせが多すぎます。（今気づいた。）

説明させてください。[4, 5] をチェックする必要があると仮定します (上記で説明したように、4 と 5 は 2 部グラフから削除されますが、ここでは関係ありません)。これが「赤」と表示された場合、私のツリーでは [4] のみをチェックできなくなります。それはいいです。ただし、チェックから [5] もマークする必要があります。

チェックの数をさらに最小限に抑えるために、ツリーの構造を (おそらくグラフに) 変更するにはどうすればよいですか?

4

3 に答える 3

2

完全な 2 部グラフ K_{r,c} でトゥッテ多項式 ((1,2) で評価され、スパニング サブグラフの総数が得られる) を評価するために、削除縮小アルゴリズムの変形を使用します。

文では、アイデアは、エッジを任意に並べ替え、スパニング ツリーを列挙し、スパニング ツリーごとに、最小スパニング ツリーを持つサイズ r + c + k のスパニング サブグラフの数を数えることです。スパニング ツリーの列挙は再帰的に実行されます。グラフ G がちょうど 1 つの頂点を持っている場合、関連するスパニング サブグラフの数は、その頂点での自己ループの数であり、k を選択します。それ以外の場合は、G の自己ループではない最小エッジを見つけて、2 つの再帰呼び出しを行います。最初はグラフ G/e で、e は縮約されています。2 番目は e が削除されたグラフ Ge にありますが、Ge が接続されている場合のみです。

于 2013-07-13T15:30:38.430 に答える
1

Python は疑似コードに十分近いです。

class counter(object):
    def __init__(self, ival = 0):
        self.count = ival

    def count_up(self):
        self.count += 1
        return self.count

def old_walk_fun(ilist, func=None):
    def old_walk_fun_helper(ilist, func=None, count=0):
        tlist = []
        if(isinstance(ilist, list) and ilist):
            for q in ilist:
                tlist += old_walk_fun_helper(q, func, count+1)
        else:
            tlist = func(ilist)
        return [tlist] if(count != 0) else tlist
    if(func != None and hasattr(func, '__call__')):
        return old_walk_fun_helper(ilist, func)
    else:
        return []

def walk_fun(ilist, func=None):
    def walk_fun_helper(ilist, func=None, count=0):
        tlist = []
        if(isinstance(ilist, list) and ilist):
            if(ilist[0] == "Red"): # Only evaluate sub-branches if current level is Red
                for q in ilist:
                    tlist += walk_fun_helper(q, func, count+1)
        else:
            tlist = func(ilist)
        return [tlist] if(count != 0) else tlist
    if(func != None and hasattr(func, '__call__')):
        return walk_fun_helper(ilist, func)
    else:
        return []

# Crude tree structure, first element is always its colour; following elements are its children
tree_list = \
["Red",
    ["Red", 
        ["Red", 
            []
        ], 
        ["White", 
            []
        ],
        ["White", 
            []
        ]
    ],
    ["White",
        ["White", 
            []
        ],
        ["White", 
            []
        ]
    ],
    ["Red", 
        []
    ]
]

red_counter = counter()
eval_counter = counter()
old_walk_fun(tree_list, lambda x: (red_counter.count_up(), eval_counter.count_up()) if(x == "Red") else eval_counter.count_up())
print "Unconditionally walking"
print "Reds found: %d" % red_counter.count
print "Evaluations made: %d" % eval_counter.count
print ""

red_counter = counter()
eval_counter = counter()
walk_fun(tree_list, lambda x: (red_counter.count_up(), eval_counter.count_up()) if(x == "Red") else eval_counter.count_up())
print "Selectively walking"
print "Reds found: %d" % red_counter.count
print "Evaluations made: %d" % eval_counter.count
print ""
于 2013-07-13T06:29:34.490 に答える
0

コネクティビティのテストを高速化するために、どれだけ懸命に取り組んでいますか?

グラフの接続性をテストするには、ランダムな順序でエッジを選択し、それらを接続するエッジが表示されたら、union-find を使用して頂点をマージします。グラフが接続されている場合、私は早期に終了することができ、接続性の一種の証明書、つまり、以前は接続されていなかった頂点の 2 つのセットを接続したエッジを持っています。

ツリーをたどる/二部グラフのパスをたどると、グラフからエッジが削除されます。削除したエッジが接続証明書に含まれていない場合でも、グラフはまだ接続されている必要があります。これは簡単なチェックのように思えます。接続性の証明書にある場合は、完全な接続性テストを繰り返すのではなく、そのエッジが追加される直前のユニオン/検索の状態にバックアップしてから、新しいエッジを追加してみてください。

パスを正確にどのように定義するかに応じて、そのパスの拡張には、これまでパスの内部にある頂点など、頂点のサブセットを使用するエッジが含まれないと言える場合があります。これらの触れられない頂点に由来するエッジがグラフを接続するのに十分である場合、パスを延長しても接続を解除することはできません。次に、少なくとも、個別のパスの数を数えるだけです。元のグラフが規則的である場合、明示的に列挙せずにそれらをカウントできる動的プログラミング再帰を見つけたいと思います。

于 2013-07-13T13:38:10.650 に答える