0

次のような二分木があるとします。ここに画像の説明を入力

A のすべての同等性を見つけるアルゴリズムを探しています。このツリーの要素を含む配列が与えられます。ルールは、ノードのすべての子が配列に存在する場合、そのノードを配列に持つことと同等です。たとえば、配列に B と C がある場合、それは A を持つことと同じです。したがって、上記の配列では、F+G=C であり、C+B = A であるため、[B,F,G] も同様に [DEFG] も A と同等です。

checkSubstitute(node) のようなものを再帰的に呼び出すことができます。

if node in array
return true
else:
    for child in nodeChildren
        if ((child not in array) && (child == terminalNode))
            return false
        else
        return checkSubstitute(child)

このロジックは理にかなっていますか？また、上記のようなアルゴリズムを使用して、同等の配列をすべて格納するにはどうすればよいですか?

前もって感謝します！！

4

2 に答える 2

3

for ループの最初の反復中に常に値を返すため、指定したメソッドは正しく機能しません。配列 [D] があるとします。次に、checkSubstitute(B) は True を返しますが、False を返す必要があります。

for ループを使用する代わりに、両方の子に対して 2 つの明示的な呼び出しを行う方が簡単です。これは、すべてのノードにゼロまたは 2 つの子があることを前提としています。ノードが 1 つの子を持つことができる場合は、追加の null チェックが必要です。

#returns true if Node n exists in NodeList seq, or if its equivalent exists in seq.
function exists(n, seq):
    if n in seq:
        return True
    if not n.hasChildren:
        return False
    return exists(n.leftChild, seq) and exists(n.rightChild, seq)

同等の配列をすべて取得するには、少しの組み合わせ論が必要です。

#gets all possible equivalents for the given node. This includes itself.
#An equivalent is a list of nodes, so this method returns a list of lists of nodes.
function getPossibleEquivalents(node):
    ret = new List()
    baseCase = new List()
    baseCase.append(node)
    ret.append(baseCase)
    if not node.hasChildren:
        return ret  
    for each leftEquivalent in getPossibleEquivalents(node.leftChild):
        for each rightEquivalent in getPossibleEquivalents(node.rightChild):
            ret.append(leftEquivalent + rightEquivalent)
    return ret

編集: N for ループをネストすることにより、正確に 0 または N 個の子を持つツリーの getPossibleEquivalents を拡張できます。

for each child0Equivalent in getPossibleEquivalents(node.child[0]):
    for each child1Equivalent in getPossibleEquivalents(node.child[1]):
        for each child2Equivalent in getPossibleEquivalents(node.child[2]):
            for each child3Equivalent in getPossibleEquivalents(node.child[3]):
                for each child4Equivalent in getPossibleEquivalents(node.child[4]):
                    ret.append(child0Equivalent + child1Equivalent + child2Equivalent + child3Equivalent + child4Equivalent + child5Equivalent)

任意の数の子を持つツリーを処理できる単一の関数を作成する場合は、各子に相当する可能性のあるそれぞれのデカルト積を取得する必要があります。一部の言語では、既にデカルト積が実装されています。たとえば、Python では次のようになります。

from itertools import product

def getPossibleEquivalents(node):
    ret = [node]
    if len(node.children) == 0: return ret
    for equivalentTuple in product(map(getPossibleEquivalents, node.children)):
        possibleEquivalent = reduce(lambda x,y: x+y, equivalentTuple)
        ret.append(possibleEquivalent)
    return ret
于 2012-06-11T20:30:21.377 に答える
0

このロジックは、すべての同等の表現を生成するために正常に機能しますが、必要に応じて確認して修正することができます。

[B,C] からすべての可能な表現が必要だとします。この配列の各ノードについて、その子を置き換えるか、そのままにしておくことができます。したがって、再帰の一般的な考え方は次のとおりです。

find_equivalent(representation, node){
        // representation is a list which is a valid equivalent representation.
        child = list_of_children_of_node;
        Temp = representation[:]
        for each c in child: Temp.insert(child)


        find_equivalent(representation, next(node,representation))
        N = next(node,Temp)
        Temp.delete(node)
        Li.append(Temp)
        find_equivalent(Temp, N)
        // Here next function takes a list and a node and returns the next element from the list after node.

上記の Li は表現のグローバル配列であり、表現が追加されるたびに関数 find_equivalent を呼び出す必要があります。

于 2012-06-11T20:32:31.233 に答える