9

次のグラフについて考えてみます。

ダミーグラフ

次の配列構造で表されます。

$graph = array
(
    'a' => array(),
    'b' => array('a'),
    'c' => array('a', 'b'),
    'd' => array('a'),
    'e' => array('d'),
    'f' => array('a', 'b', 'c', 'd'),
    'g' => array('d'),
    'h' => array('c'),
    'i' => array('c', 'g'),
    'j' => array(),
);

ノードを繰り返さずに、ノードXからノードYまでのいずれかの方向のすべてのパス（最短パスだけでなく）を見つけるための最も効率的なアルゴリズムは何ですか？たとえば、ノードからノードにつながるパスは次のとおりです。CA

C --> A
C --> B --> A
C --> F --> A
C --> F --> B --> A
C --> F --> D --> A
C --> I --> G --> D --> A

ノードの親ノードX（AおよびB、ノードの例ではC）を使用してすべてのパスを見つけるのは簡単ですが、子孫/ハイブリッド方向にノードをトラバースするのに非常に苦労しています。

誰かが私を助けることができますか？

更新：@JackManeyのアドバイスに従って、ウィキペディアの擬似コードに基づいてIDDFS（Iterative Deepening Depth-First Search）を移植しようとしましたが、これは多かれ少なかれ私のコードのように見えます。

$graph = directed2Undirected($graph);

function IDDFS($root, $goal) {
    $depth = 0;

    while ($depth <= 2) { // 2 is hard-coded for now
        $result = DLS($root, $goal, $depth);

        if ($result !== false) {
            return $result;
        }

        $depth++;
    }
}

function DLS($node, $goal, $depth) {
    global $graph;

    if (($depth >= 0) && ($node == $goal)) {
        return $node;
    }

    else if ($depth > 0) {
        foreach (expand($node, $graph) as $child) {
            return DLS($child, $goal, $depth - 1);
        }
    }

    else {
        return false;
    }
}

そして、これがそれによって使用されるヘルパー関数です：

function directed2Undirected($data) {
    foreach ($data as $key => $values) {
        foreach ($values as $value) {
            $data[$value][] = $key;
        }
    }

    return $data;
}

function expand($id, $data, $depth = 0) {
    while (--$depth >= 0) {
        $id = flatten(array_intersect_key($data, array_flip((array) $id)));
    }

    return array_unique(flatten(array_intersect_key($data, array_flip((array) $id))));
}

function flatten($data) {
    $result = array();

    if (is_array($data) === true) {
        foreach (new RecursiveIteratorIterator(new RecursiveArrayIterator($data)) as $value) {
            $result[] = $value;
        }
    }

    return $result;
}

上記を呼び出すと、奇妙な結果または不完全な結果が得られます。

var_dump(IDDFS('c', 'a')); // a -- only 1 path?
var_dump(IDDFS('c', 'd')); // NULL -- can't find this path?!

擬似コードから何かを見落としていると思いますが、それが何であるかはわかりません。

別の質問で推奨されたこのDFSクラスも試しましたが、ノードXからノードYへのパスは常に1つ見つかるようですが、すべてのパスを返すようにすることはできません（ C->AおよびC->Dのデモ）。

実際にたどるパスを知る必要はないので、ノードXからノードYに到達するためにステップ数を必要とするパスがいくつ存在するかnだけなので、この関数を思いつきました（directed2Undirected上記で使用）。

$graph = directed2Undirected($graph);

function Distance($node, $graph, $depth = 0) {
    $result = array();

    if (array_key_exists($node, $graph) === true) {
        $result = array_fill_keys(array_keys($graph), 0);

        foreach (expand($node, $graph, $depth - 1) as $child) {
            if (strcmp($node, $child) !== 0) {
                $result[$child] += $depth;
            }
        }

        $result[$node] = -1;
    }

    return $result;
}

function expand($id, $data, $depth = 0) {
    while (--$depth >= 0) {
        $id = flatten(array_intersect_key($data, array_flip((array) $id)));
    }

    // no array_unique() now!
    return flatten(array_intersect_key($data, array_flip((array) $id)));
}

の場合Distance('c', $graph, 0)、これはDistance('c', $graph, 1)と他のノードDistance('c', $graph, 2)間の距離の合計を正しく返します。C問題は、Distance('c', $graph, 3)（以上）でノードの繰り返しを開始し、 間違った結果を返すことです。

Array
(
    [a] => 12
    [b] => 9
    [c] => -1
    [d] => 9
    [e] => 3
    [f] => 12
    [g] => 3
    [h] => 3
    [i] => 6
    [j] => 0
)

3つのステップを使用aするための唯一の方法は次のとおりであるため、インデックスは6（3 + 3）のみである必要があります。CA

C --> F --> B --> A
C --> F --> D --> A

それでも、ノードを繰り返す2つの（のみ？）追加のパスを検討しているようです。

C --> A --> C --> A
C --> B --> C --> A
C --> F --> C --> A
C --> H --> C --> A
C --> I --> C --> A

もちろん、a間違っているのはインデックスだけではありません。問題はあるようexpand()ですが、それを修正する方法がわかりません。array_diff(expand('c', $graph, $i), expand('c', $graph, $i - 2))この特定のエラーを修正するようですが、それは適切な修正ではありません...ヘルプ？

再びダミーグラフ 繰り返しますので、スクロールする必要はありません

4

2 に答える 2

2

一般に、深さ優先検索または幅優先検索を実行できますが、どちらが優れているというわけではありません (どちらが優れているかの例を簡単に思いつくことができるため)。

編集：C質問を読み直して少し考えてみると、からへの すべてのパスが必要なのでA、で始まるDFSCがおそらく最も理にかなっています。途中で、エッジのシーケンスを保存し、最終的に に到達しない場合はシーケンスを破棄する必要がありますA。

于 2012-05-29T17:53:08.253 に答える