程式語言導論/窮舉搜尋

儘管 Prolog 是一種通用程式語言，但當我們需要處理涉及窮舉搜尋的問題時，它真正閃耀。許多問題都是這樣的，即找到精確解的唯一方法是透過蠻力搜尋。兩種技術是實現簡單優雅搜尋的關鍵。第一種是從集合中生成子集的方法，我們將其實現如下

subSet([], []).
subSet([H|T], [H|R]) :- subSet(T, R).
subSet([_|T], R) :- subSet(T, R).

第二種技術是生成序列排列的方法。有幾種方法可以實現此謂詞。下面我們找到一個簡單的實現

perm([], []).
perm(List, [H|Perm]) :- select(H, List, Rest), perm(Rest, Perm).

那麼，哪些型別的問題可以透過窮舉搜尋很好地解決？NP 完全問題就是一個很好的開始。也許最簡單的 NP 完全問題是子集和問題，我們將其表述如下：給定一個集合 S 和一個整數 N，是否存在 S 中的一個子集 L，其和加起來等於 N？下面給出了 Prolog 中此問題的解決方案

intSum(L, N, S) :- subSet(L, S), sumList(S, N).

我們正在使用之前見過的兩個謂詞subSet和sumList。此解決方案的妙處在於它的簡潔性。實際上，Prolog 解決方案是對問題的陳述，幾乎是用簡單的英語。我們說一種程式語言是高階的，如果它減少了問題與其解決方案的實現之間的語義差距。對於這個特定示例，子集和問題解決方案的描述也是解決方案本身。這個問題說明了邏輯程式語言在解決涉及窮舉搜尋的問題時的優雅性和表達能力。

請注意，即使是可以高效精確求解的問題也可以透過窮舉搜尋來解決。這種蠻力解決方案通常效率不高；但是，它們很優雅，並且很好地說明了我們想要解決的問題的基本結構。例如，考慮下面透過窮舉搜尋實現的排序演算法，它使用perm上面看到的謂詞。已排序列表的版本是其元素的排列，它滿足以下屬性：給定已排序列表中的任意兩個連續元素 H1 和 H2，我們有 H1 小於或等於 H2

isSorted([]).
isSorted([_]).
isSorted([H1,H2|T]) :- H1 =< H2, isSorted([H2|T]).

mysort(L, S) :- perm(L, S), isSorted(S).

當然，我們可以使用窮舉搜尋編寫更有用的謂詞。例如，如果我們想發現某個字串是否表示任何英語單詞的字謎？假設我們有一個字典dic.txt，其中包含已知的單詞，用點隔開。下面可以看出 Prolog 中此謂詞的實現

file_to_list(FILE, LIST) :- see(FILE), inquire([], LIST), seen.

inquire(IN, OUT):-
  read(Data),
  (Data == end_of_file -> OUT = IN; atom_codes(Data, LData), inquire([LData|IN], OUT)).

find_anagram(Dic, A, S) :- file_to_list(Dic, L), perm(A, X), member(X, L), name(S, X).

上面程式中的幾個術語是 swipl 標準庫的一部分，例如，see, seen, read, atom_codes和name。這些謂詞用於處理輸入和輸出，或將原子轉換為列表（atom_codes）和原子轉換為字串（name）。注意如何perm用於查詢輸入字串的所有排列。其中一些排列可能在從輸入檔案構建的列表中具有等效項。如果是這種情況，那麼我們將其報告為我們問題的解決方案。要執行此謂詞，假設我們在本地目錄中有一個名為“dic.txt”的檔案，我們可以執行

?- find_anagram('dic.txt', "topa", S).
S = pato ;
S = atop ;

而且，如果我們想將所有解決方案連線到單個列表中，Prolog 為我們提供了謂詞findall，其工作原理如下

?- findall(S, find_anagram('dic.txt', "topa", S), Solutions).
Solutions = [pato, atop].

此謂詞接收三個引數。術語findall(S, Q, L)將構建一個列表L，使用模式S這些模式是在解決查詢時產生的Q。每個模式S是Q的可能解決方案都應插入輸出列表中。例如，讓我們考慮以下三個查詢

?- findall(S, intSum([2, 3, 5, 7, 9, 11], 25, S), Answers).
Answers = [[2, 3, 9, 11], [2, 5, 7, 11], [5, 9, 11]].

?- findall(S, perm([a, b, c], S), Answers).
Answers = [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].

?- findall(S, subSet([0, 1, 2], S), Answers).
Answers = [[0, 1, 2], [0, 1], [0, 2], [0], [1, 2], [1], [2], []].

作為窮舉搜尋的最後一個示例，我們使用 Prolog 在圖中查詢團。在圖中查詢大小為 N 的團的問題是 NP 完全的。因此，我們不太可能對此問題有一個有效的解決方案。然而，我們可以在 Prolog 中有一個簡單的解決方案。為了表示圖，我們可以使用一組表示邊的謂詞。例如

edge(a, b).
edge(a, c).
edge(b, c).
edge(c, d).
edge(c, e).
edge(b, d).
edge(b, e).
edge(e, f).
edge(b, f).

這些謂詞確定一個有向圖。如果我們不需要方向，那麼我們可以有一個謂詞來檢查是否edge(X, Y)或edge(Y, X)在我們的謂詞資料庫中

linked(X, Y) :- edge(X, Y).
linked(X, Y) :- edge(Y, X).

根據這些定義，很容易生成一個謂詞來確定節點列表是否形成一個團

clique([]).
clique([_]).
clique([X1,X2|R]) :- linked(X1, X2), clique([X1|R]), clique([X2|R]).

最後，我們真正想知道的是我們的圖中是否有一個大小為 N 的團。鑑於我們已經擁有的謂詞，生成此查詢幾乎就像用簡單的英語編寫它一樣

cliqueN(V, C, N) :- sublist(V, C), clique(C), length(C, N).