Эффективный код для поиска маршрута между узлами дерева данных - PullRequest
Новая
       48

Эффективный код для поиска маршрута между узлами дерева данных

3 голосов
/ 22 января 2020

У меня есть файл в следующем формате: 

Y1DP480P T FDVII005 ID=000
Y1DPMS7M T Y1DP480P ID=000
Y1DPMS7M T Y1DP4860 ID=000
Y1DPMS7M T Y1ENDCYP ID=000
Y1DPMS6M T Y1DPMS7M ID=000
Y1DPMS5M T VPY1CM28 ID=000
Y1DPMS5M T Y1DPMS6M ID=000
Y1DPAS21 T Y1DPMS5M ID=000
Y1DPMS4M T FDRBC004 ID=000
Y1DPMS4M T FDYBL004 ID=000

et c. et c.

используются только данные в столбцах 1-8 и 12-19, и их можно рассматривать как: 

node1 -> node2
node1 -> node3
node3 -> node5
node2 -> node4
node4 -> node5
node5 -> node7

Мне нужен эффективный способ отобразить путь от данного начального узла до данного конечного узла.

Например, если я хочу путь от узла1 до узла7, функция вернет узел1-> узел3, узел3-> узел5, узел5-> узел7.

Текущий подход:

Я считал файл в массив, используя первые 19 символов в качестве ключа и значения, например 

$data[Y1DP480P T FDVII005] = 'Y1DP480P T FDVII005'

(я использую значение в качестве ключ, потому что входной файл может содержать дубликаты, поскольку это отфильтровывает их - я не думаю, что PHP имеет структуру данных 'set').

У меня есть рекурсивная подпрограмма, которая находит следующие 'n' зависимости из данного узла следующим образом:

(при входе $ path [] - пустой массив, данные узла находятся в $ data, узел, с которого начинается поиск, - $ job, а глубина зависимостей - $ глубина) 

function createPathFrom($data, $job, $depth) {
    global $path, $maxDepth, $timeStart;
    $job = trim($job);
    // echo "Looking for $job\n";
    if ( $depth > $maxDepth ) {return;} // Search depth exceeded
    // if ( (microtime(true) - $timeStart) > 70 ) {return;} //Might not be needed as we have the same further down
    // $depth += 1;
    // Get the initial list of predecessors for this job.
    // echo __FUNCTION__."New iteration at depth $depth for $job\n";
    $dependents = array_filter($data, function($dataLine) use($job){
        // preg_match('/'.JOB_SPLIT_MASK.'/', $dataLine, $result);
        // $dependent = trim($result[1]);
        $dependent = explode(" ", $dataLine)[0];
        return ( $dependent == $job );
        // return ( preg_match('/'.$job.'/', $dependent) );
    });

    if (count($dependents) == 0) {
        return;
    } else {
        // print_r($predecessors);
        $elapsedTime = microtime(true) - $timeStart;
        // print $elapsedTime." : Searching ".count($dependents)." at depth ".$depth.NL;

        $path = array_merge($path, $dependents);
        foreach($dependents as $dependency) {
            // preg_match('/'.JOB_SPLIT_MASK.'/', $dependency, $result);
            // $dependent = trim($result[3]);
            $dependent = explode(" ", $dependency)[2];
            if ( (microtime(true) - $timeStart) > 85 ) {return;} // Let's get out if running out of time... (90s in HTTPD/conf)
            createPathFrom($data, $dependent, $depth+1);
        }
    }
}

У меня есть почти идентичная функция, которая установила предшественников для моей цели нет де называется createPathTo

Ограничения по времени (70-е и 85-е и да - одно определенно избыточно) и ограничение по глубине - чтобы избежать тайм-аута моего cgi-скрипта.

Если я вызываю обе подпрограммы с достаточной «глубиной», я могу видеть, соединяются ли они, но есть много тупиков.

Я думаю, что делаю в ширину поиск, тогда как я думаю, что я должен выполнить поиск в глубину и отбросить поиски, которые не достигают моего целевого узла.

Вопрос:

Давая начало узел и конечный узел, существует ли эффективный алгоритм поиска, который будет возвращать минимальный минимум узлов для установления соединения или какое-либо значение, указывающее, что путь не найден?

Этот вопрос следует из Рекурсивная функция в PHP чтобы найти путь между произвольными узлами . У меня есть узлы, ведущие (и теперь от) к моему целевому узлу, но теперь я хочу обрезать его до пути между двумя узлами.

Редактировать: Я уверен, что ответ уже здесь, на SO, но я довольно плохо знаком с PHP и подобными алгоритмами, поэтому не смог найти ни одного.

1 Ответ

2 голосов
/ 22 января 2020

Вам будет лучше с такой структурой: 

$data =[
    "Y1DP480P" => ["FDVII005" => true],
    "Y1DPMS7M" => ["Y1DP480P" => true, "Y1DP4860" => true, "Y1ENDCYP" => true],
    // ...etc
];

Итак, для каждого ключа у вас есть «набор» дочерних ключей, доступ к которому можно получить за один шаг от первого ключа. Хотя наборы не существуют, вы, как правило, имитируете c, что: используйте ассоциативный массив со значениями true (или что вы предпочитаете вместо этого). Это также будет игнорировать дубликаты записей, которые могут быть у вас на входе.

Тогда стандартная BFS будет весьма эффективной: 

$input = "aaaaaaaa T bbbbbbbb ID=000
aaaaaaaa T cccccccc ID=000
cccccccc T eeeeeeee ID=000
bbbbbbbb T dddddddd ID=000
dddddddd T eeeeeeee ID=000
eeeeeeee T gggggggg ID=000";

// Convert input to the data structure:
$data = [];
foreach (explode("\n", $input) as $line) {
    list($a, $b) = explode(" T ", substr($line, 0, 19));
    $data[$a][$b] = true;
    if (!isset($data[$b])) $data[$b] = [];
}

function shortestPath($data, $source, $target) { // Perform a BFS
    $comeFrom[$source] = null;
    $frontier = [$source];
    while (count($frontier)) {
        $nextFrontier = [];
        foreach ($frontier as $key) {
            if ($key == $target) {
                $path = [];
                while ($key) { // unwind the comeFrom info into a path
                    $path[] = $key;
                    $key = $comeFrom[$key];
                }
                return array_reverse($path); // the path needs to go from source to target
            }
            foreach ($data[$key] as $neighbor => $_) {
                if (isset($comeFrom[$neighbor])) continue;
                $comeFrom[$neighbor] = $key;
                $nextFrontier[] = $neighbor;
            }
        }
        $frontier = $nextFrontier;
    }
}

$path = shortestPath($data, "aaaaaaaa", "gggggggg");

print_r($path); // ["aaaaaaaa", "cccccccc", "eeeeeeee", "gggggg"]
...