Prolog/搜尋技術

Prolog 的預設搜尋演算法是 深度優先搜尋 (DFS)，它有時並不方便：DFS 並不總是能找到所有問題的解決方案，即使它能找到，也可能找不到最佳解決方案。

假設我們想在一個有向圖中找到最短路徑，其中節點由符號表示，弧由謂詞 arc/2 表示。然後我們可以輕鬆實現 迭代加深搜尋 來找到最短路徑。

path(X, Z, Path) :-
    length(Path, _),
    path_r(X, Z, Path).

path_r(Z, Z, []).
path_r(X, Z, [X|Path]) :-
    arc(X, Y),
    path(Y, Z, Path).

path/3 按長度對路徑進行回溯，如果存在至少一條路徑，則會進行回溯。讓我們試一試。

?- path(a, g, P).
P = [a] ;
P = [a, b, f] ;
P = [a, c, d, f] ;
P = [a, b, c, d, f]

工作原理：當 length/2 以變數作為第一個引數被呼叫時，它會生成一個包含新變數的指定長度的列表。此外，如果第二個引數也是一個變數，它會從零開始，每次遞增一個，對所有可能的長度進行回溯。每次都用固定的路徑長度呼叫輔助謂詞 path_r。