我有一個格式如下的文件：Y1DP480P T FDVII005 ID=000Y1DPMS7M T Y1DP480P ID=000Y1DPMS7M T Y1DP4860 ID=000Y1DPMS7M T Y1ENDCYP ID=000Y1DPMS6M T Y1DPMS7M ID=000Y1DPMS5M T VPY1CM28 ID=000Y1DPMS5M T Y1DPMS6M ID=000Y1DPAS21 T Y1DPMS5M ID=000Y1DPMS4M T FDRBC004 ID=000Y1DPMS4M T FDYBL004 ID=000等等等等僅使用第 1-8 列和第 12-19 列中的數據，可以認為是：node1 -> node2node1 -> node3node3 -> node5node2 -> node4node4 -> node5node5 -> node7我需要一種有效的方法來映射從給定起始節點到給定結束節點的路徑。例如，如果我想要從 node1 到 node7 的路徑，該函數將返回 node1->node3、node3->node5、node5->node7。目前的做法：我將文件讀入一個數組，將前 19 個字符作為鍵和值，例如$data[Y1DP480P T FDVII005] = 'Y1DP480P T FDVII005' （我使用該值作為鍵，因為輸入文件可能包含重復項，因為這會將它們過濾掉——我認為 PHP 沒有“設置”數據結構）。我有一個遞歸子例程，可以從給定節點中找到下一個“n”個依賴項，如下所示：（入口時，$path[] 是一個空數組，節點數據在 $data 中，開始搜索的節點是 $job，依賴的深度是 $depth）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) ); });我有一個幾乎相同的功能，它為我的端節點建立了前輩，稱為createPathTo時間限制（70 秒和 85 秒，是的 - 一個絕對是多余的）和深度限制是為了避免我的 cgi 腳本超時。如果我以足夠的“深度”調用這兩個例程，我可以查看它們是否連接，但有很多死胡同。我認為我正在進行廣度優先搜索，而我認為我應該進行深度優先搜索并丟棄未到達目標節點的搜索。問題：給定一個開始節點和一個結束節點，是否有高效的搜索算法將返回最少的節點以建立連接或指示未找到路徑的某個值？這個問題從PHP 中的 Recursive function 開始，以查找任意節點之間的路徑。我有通向（現在來自）我的目標節點的節點，但現在我想將其修剪為僅 2 個節點之間的路徑。編輯：我確定答案已經在這里了，但是我對 PHP 和這些算法很陌生，所以一直找不到。
1 回答
海綿寶寶撒
TA貢獻1809條經驗 獲得超8個贊
使用這樣的結構會更好：
$data =[
"Y1DP480P" => ["FDVII005" => true],
"Y1DPMS7M" => ["Y1DP480P" => true, "Y1DP4860" => true, "Y1ENDCYP" => true],
// ...etc
];
因此，每個鍵都有一組子鍵，可以從第一個鍵開始一步到達。盡管集合不存在，但您通常會這樣模仿：使用帶有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"]
- 1 回答
- 0 關注
- 131 瀏覽
添加回答
舉報
0/150
提交
取消