Рассмотрим следующий график:
Представлен следующей структурой массива:
$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 в любом направлении без повторения узлов? Например, пути, которые ведут от узла C
к узлу A
, это:
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(Итеративный углубляющийся глубина-первый поиск)на основе псевдокода Википедии и вот как выглядит мой код:
$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, я не могу заставить его вернуть все пути (demo forC
-> A
иC
-> D
).
Поскольку мне не нужно знать фактически пройденный путь, только сколько существует путей, которые требуют n
количество шагов, чтобы добраться от узла X до узла Y, я придумал эту функцию (использует 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)
иРасстояние('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
)
Индекс a
должен быть только 6 (3 + 3), так как единственные способы, которыми я могу получить от C
до A
, используя 3 шага:
C --> F --> B --> A
C --> F --> D --> A
Тем не менее, похоже, что он рассматриваетдва(только?) дополнительных пути, которые повторяют узлы:
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))
, кажется, исправляет эту конкретную ошибку, но это не является правильным исправлением... Справка?
снова, так что вам не нужно прокручивать