我有一個(gè)格式如下的文件：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 列中的數(shù)據(jù)，可以認(rèn)為是：node1 -> node2node1 -> node3node3 -> node5node2 -> node4node4 -> node5node5 -> node7我需要一種有效的方法來映射從給定起始節(jié)點(diǎn)到給定結(jié)束節(jié)點(diǎn)的路徑。例如，如果我想要從 node1 到 node7 的路徑，該函數(shù)將返回 node1->node3、node3->node5、node5->node7。目前的做法：我將文件讀入一個(gè)數(shù)組，將前 19 個(gè)字符作為鍵和值，例如$data[Y1DP480P T FDVII005] = 'Y1DP480P T FDVII005' （我使用該值作為鍵，因?yàn)檩斎胛募赡馨貜?fù)項(xiàng)，因?yàn)檫@會(huì)將它們過濾掉——我認(rèn)為 PHP 沒有“設(shè)置”數(shù)據(jù)結(jié)構(gòu)）。我有一個(gè)遞歸子例程，可以從給定節(jié)點(diǎn)中找到下一個(gè)“n”個(gè)依賴項(xiàng)，如下所示：（入口時(shí)，$path[] 是一個(gè)空數(shù)組，節(jié)點(diǎn)數(shù)據(jù)在 $data 中，開始搜索的節(jié)點(diǎn)是 $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) ); });我有一個(gè)幾乎相同的功能，它為我的端節(jié)點(diǎn)建立了前輩，稱為createPathTo時(shí)間限制（70 秒和 85 秒，是的 - 一個(gè)絕對(duì)是多余的）和深度限制是為了避免我的 cgi 腳本超時(shí)。如果我以足夠的“深度”調(diào)用這兩個(gè)例程，我可以查看它們是否連接，但有很多死胡同。我認(rèn)為我正在進(jìn)行廣度優(yōu)先搜索，而我認(rèn)為我應(yīng)該進(jìn)行深度優(yōu)先搜索并丟棄未到達(dá)目標(biāo)節(jié)點(diǎn)的搜索。問題：給定一個(gè)開始節(jié)點(diǎn)和一個(gè)結(jié)束節(jié)點(diǎn)，是否有高效的搜索算法將返回最少的節(jié)點(diǎn)以建立連接或指示未找到路徑的某個(gè)值？這個(gè)問題從PHP 中的 Recursive function 開始，以查找任意節(jié)點(diǎn)之間的路徑。我有通向（現(xiàn)在來自）我的目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)，但現(xiàn)在我想將其修剪為僅 2 個(gè)節(jié)點(diǎn)之間的路徑。編輯：我確定答案已經(jīng)在這里了，但是我對(duì) PHP 和這些算法很陌生，所以一直找不到。
1 回答
海綿寶寶撒
TA貢獻(xiàn)1809條經(jīng)驗(yàn) 獲得超8個(gè)贊
使用這樣的結(jié)構(gòu)會(huì)更好：
$data =[
"Y1DP480P" => ["FDVII005" => true],
"Y1DPMS7M" => ["Y1DP480P" => true, "Y1DP4860" => true, "Y1ENDCYP" => true],
// ...etc
];
因此，每個(gè)鍵都有一組子鍵，可以從第一個(gè)鍵開始一步到達(dá)。盡管集合不存在，但您通常會(huì)這樣模仿：使用帶有true值的關(guān)聯(lián)數(shù)組（或者您喜歡的任何東西）。這也將忽略您在輸入中可能存在的重復(fù)條目。
然后，標(biāo)準(zhǔn)的 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 關(guān)注
- 144 瀏覽
添加回答
舉報(bào)
0/150
提交
取消