1

私は試してみました。検索して検索しましたが、私の問題を解決するアルゴリズムを実際に見つけることができませんでした。ツリー内のすべてのパス (単純なパスだけでなく) を列挙したいと思います (ただし、これは簡単な制約です)。

たとえば、ツリーの場合。

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

次のパスを生成できるようにしたい:

4
4-2-5
4-2-5-2-1-3-6
4-2-5-2-1-3-7
4-2-5-2-1-3-6-3-7
4-2-1-3-6
4-2-1-3-7
4-2-1-3-6-3-7
5
5-2-1-3-6
5-2-1-3-7
5-2-1-3-6-3-7
6
6-3-7
7

それだけだと思います。

次の解決策を試しました深さ優先検索を使用してすべての単純なパスを見つけることの複雑さ? . ただし、単純なパスしか検索されないため、4-2-5-2-1-3-6 などのパスは検索できませんでした。

あなたが私を導くことができる方法はありますか、おそらくアルゴリズムはありますか?

4

2 に答える 2

0

4-2-1-2-5 のようなパスはカウントされますか? もしそうなら、私は答えがあると思います：

各エッジに「1回」だけアクセスしたいようです。したがって、グラフの「デュアル」を使用して、パスを頂点のシーケンスではなくエッジのシーケンスとして見てください。このようにして、エッジが「頂点」になり、頂点が「エッジ」になります。

これにより、問題が単純なグラフのパスの生成に軽減されます。これは、既に方法を知っている問題です。

traverse(path, edg):
    mark edg as visited
    print path
    for each edge (e2) sharing a vertex with edg:
        traverse(e2, path+e2)

(with some sort of precaution to avoid duplicate paths being printed)
于 2011-05-01T15:32:08.340 に答える
0

ツリーがバイナリ ツリーである場合、これはかなり単純な再帰アルゴリズムです。Python の場合:

def lchild(u):
    return 2 * u

def rchild(u):
    return 2 * u + 1

def paths(u, depth):
    if depth <= 0:
        yield ((), (u,), ())
    else:
        for ldown, lpath, lup in paths(lchild(u), depth - 1):
            yield ((u,) + ldown, lpath, lup + (u,))
        for ldown, lpath, lup in paths(lchild(u), depth - 1):
            for rdown, rpath, rup in paths(rchild(u), depth - 1):
                yield ((u,) + ldown, lpath + lup + (u,) + rdown + rpath, rup + (u,))
        for rdown, rpath, rup in paths(rchild(u), depth - 1):
            yield ((u,) + rdown, rpath, rup + (u,))

if __name__ == '__main__':
    for down, path, up in paths(1, 2):
        print path
于 2011-05-01T19:34:13.267 に答える