完整性的A *搜索

我一直在閱讀有關A *的完整性和我的理解，它必須是完整的，如果它有一個有限的分支因子，但爲什麼一定要還完成後，每個邊的權大於0？完整性的A *搜索

2017-04-10 Denjvf

因爲如果你有負權，你不能永遠保證你的最佳路徑。您的路徑可能會延伸通過這些負向加權分支。或者更糟糕的是，可能會出現一個負權重循環，您的算法將永遠循環。 –

我認爲你在這個定理的轉錄中犯了兩個錯誤。「如果分支因子有限且所有權重都大於ε> 0，則A *是完整的。」你用「或」替代了「和」，並用「正」代替了「大於某些ε> 0」。看到我的答案爲什麼你對這個定理的陳述是錯誤的。 –

這不是真的，如果圖形具有有限的支化因子和每個邊緣的重量大於零，那麼A *終止。

例如，考慮頂點0，1，2，3，圖表......和一個頂點*。讓i和i+1之間的邊緣的權重爲1/2^i和讓0和*之間的邊緣的權重是2。讓啓發式是0，所以A *退化成Dijkstra算法。

然後A *不會找到（在有限時間內）從0到*路徑 - 這將探討由於從0到n的距離沿自然數的路徑總是小於2。所以儘管此圖具有有限的分支因子和正邊權重，A *未找到解決方案。

定理的正確的說法是：「如果有圖有一個有限的分支因子和所有的權重比一些ε> 0，則A *是完整的更大。」證明很簡單：如果從開始到結束的路徑具有權重d，那麼在最壞的情況下，所有頂點距離< = d都會在末端節點之前訪問。但最多可以有很多，因爲從起始節點到每個節點的路徑最多可以由d /ε頂點組成。

2017-04-10 13:57:25

回答