编程语言导论/穷举搜索

尽管 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).