Prolog中的廣度優先

Question

在Prolog中使用默認深度優先搜索方案中的廣度優先的一般想法是什麼？

不服用無限分支？

在Prolog中有沒有使用廣度優先的一般方法？我一直在Google上搜索，並沒有爲新手找到太多有用的信息。

Answer 1

寬度優先的優勢在於您可以找到所有解決方案。隨着深度優先，你可以陷入無限的分支。

缺點是寬度優先使用大量內存，因此一般不用於執行。

如果你想使用它，你需要明確地使用某種類型的隊列來實現它。

編輯：如果您想要在不使用太多內存的情況下擁有寬度優先搜索的優勢，則可以使用迭代加深。這是深度優先的深度搜索，您會連續增加。這會導致一些重複的計算，但是如果您的搜索空間沒有分支的長線性延伸，那麼這種重複是很小的。

Answer 2

有一些我知道的「議程搜索」。在遍歷樹（數據，關係，規則......）時，你維護一個關於接下來要做什麼的「議程」（列表）。當你進入一個節點時，你把他的孩子放在議程上，然後繼續你彈出的議程的第一個元素。這樣，如果您在議程末尾添加新項目，則可以獲得寬度優先。如果你把它們放在議程前面，你可以先深入研究。

用Prolog很容易實現。

編輯：我可能只是在這裏給一個實現提示。這是議程搜索算法的一個非常基本的實現。

agenda_search([N|T],Mode):- 
    doWithNode(N),   % do whatever you do the searching for 
    getNodeChildren(N,C), 
    (Mode=bf ->    % bf or df (depth-first) 
     append(T,C,A); 
     append(C,T,A)), 
    agenda_search(A,Mode). 

它依賴於代表希望與每個節點執行的動作外謂詞doWithNode（例如節點的數據進行比較，以搜索詞，序列化節點內容，ASF）。並且getNodeChildren將把給定節點的子節點列表綁定到C（即，這個謂詞實際上知道樹結構以及如何找到子節點）。當然，doWithNode謂詞可能需要額外的參數才能完成它的工作，這也將顯示在參數列表agenda_search中。

您可以調用它像這樣：

agenda_search([RootNode], bf) % for breadth-first search 

和

agenda_search([RootNode], df) % for depth-first search 

我也發現有點議程搜索on this web page的解釋。議程搜索的好處在於，您可以輕鬆地在兩種變體df和bf之間切換，並與結果一起玩。該算法在記憶方面表現相當好，因爲議程，仍然需要探索的節點，只能捕捉樹中任何時候（所謂的邊緣）的（或多或少）小部分節點。

Answer 3

agenda_search的代碼應該可以正常工作。 爲了提高效率，您可能希望考慮使用其他數據結構;事實上，在廣度優先模式下，整個節點列表（T）將通過追加（T，C，A）遍歷。 您可以使用SICStus的庫（隊列）模塊。廣度優先搜索然後看起來如下（由謂詞開始/ 1，後繼謂詞s/2和目標謂詞目標/ 1進行參數化）。請注意，我還添加了循環檢查。

 
bfs(Res) :- start(Start), empty_queue(EQ), 
    queue_append(EQ,[e(Start,[])],Q1), 
    bfs1(Q1,Res). 

bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue), 
    bfs2(Next,Path,NQ,Res). 

bfs2(H,Path,_NQ,Res) :- goal(H), reverse([H|Path],Res). 
bfs2(H,Path,NQ,Res) :- 
       findall(e(Succ,[H|Path]), 
         (s(H,Succ),\+ member(Succ,Path)),AllSuccs), 
       queue_append(NQ,AllSuccs,NewQueue), 
       bfs1(NewQueue,Res). 

（你也可以嘗試更換/通過更好的數據結構補充路徑組件;例如，AVL樹） 一個例子解決的問題是：

 
start(env(0,0)). 
s(env(X,Y),env(X1,Y)) :- X1 is X+1. 
s(env(X,Y),env(X,Y1)) :- Y1 is Y+1. 
goal(env(3,3)). 

你也可以用優先級隊列替換隊列，並使用啓發式函數計算優先級。然後，您可以獲得A *搜索（可以仿真深度優先，寬度優先，最佳優先...）。 Bratko的書（人工智能邏輯編程）應該是閱讀這些材料的好資料。