33.txt

人工智能中关于五人问题的PROLOG实现

有5个人坐在一起。问第5个人几岁，他说比第4个人大2岁；第4个人说比第3个人大2岁；第3个人说比第2个人大2岁；第2个人说比第1个人大2岁；第1个人说自己的年龄是10岁。问第5个人几岁？

predicates
  age(integer,integer)

goal 
  age(5,X),
  write("The 5th person's age is ",X),nl.

clauses
  age(1,X):-X=10.
  age(N,X):-N1=N-1,age(N1,X1),X=X1+2.


一、从问题解决视角看Prolog

问题就是一种情境，在这个情境中，一个人希望达到一定的目标，但是又不能即刻知道该如何才能达到，个体的任务就是运用某种策略，探索从问题的初始状态达到目标状态的一条路径。因此，问题解决就是人们面临着问题这个情境时产生的一系列有目的指向的认知操作过程。

Prolog是一种逻辑型人工智能程序设计语言，主要适合于处理逻辑推理问题，它的最大特点在于其描述问题的方式。Prolog语言求解问题时，要求编程者描述所求解问题中的对象和反映它们之间关系的某些已知事实，描述和定义各对象和对象之间关系的某些规则。它强调描述对象（和事实）之间的逻辑关系，而不必描述求解问题的详细计算步骤。因此，Prolog程序一般由一组事实、规则和问题组成，其中问题就程序的目标。Prolog程序的运行是从目标出发，并不断进行匹配、合一，有时还要回溯，直到目标被完全满足或不能满足为止。

Prolog是一个很好的问题求解工具，Prolog程序的运行过程实质上就是一种问题求解的过程。利用Prolog求解问题的一般过程包括：理解问题、设计方案、实施方案和回顾求解过程。理解问题主要是明确所求解问题的类型和要求；设计方案主要是确定如何表示问题中的对象和目标；实施方案主要是定义求解问题所需的每个关系；回顾求解过程主要是对问题求解的过程及结果进行评价。

一般说来，利用Prolog求解的问题包括以下三种类型： 

1)发现型问题（problem-to-find）：是指那些需要找到某一未知对象的问题。

2)证明型问题（problem-to-prove）：是指那些需要证明某一关系或猜测的正确性的问题。

3)实现型问题（problem-to-do）：是指那些需要计算机执行某个程序或其他任务的问题。

二、发现型问题（problem-to-find）的求解——农夫过河

问题描述 有一个农夫带着一只狼、一只山羊和一筐白菜过河，要从南岸过河到北岸。岸边有一条小船，农夫可以独自划着小船过河，或者每次带其中的一样东西过河。问题是如果他留下狼和羊在一起，那么狼就会把羊吃掉；如果留下羊和白菜，那么羊就会把白菜吃掉。农夫如何才能安全地将全部东西运到河对岸？

设计方案

可以用farmer、wolf、goat和cabbage分别表示问题中的农夫、狼、山羊和白菜等对象。状态描述了各个成员的位置，可以用字母n和s分别表示北岸和南岸，例如，可以用location(s, n, n, s)表示农夫、狼、山羊和白菜分别在南岸、北岸、北岸和南岸。动作描述了农夫的摆渡操作，根据题意，一共只有四种动作，分别是农夫独自划船、农夫带着狼划船、农夫带着山羊划船和农夫带着白菜划船。

问题求解的目标是一个特定的动作序列（即渡河程序），而每个动作都将当前状态转变成另一个新的状态，所以状态的变化过程可以反应出动作执行的过程。因此，可以将求解动作序列的问题转换成求解状态变化过程的问题，状态变化过程求出来后，只要用某种方法将状态变化转换成相应的动作序列输出即可。我们用一个表X表示这个未知的状态变化过程，X的条件是它必须由和平的状态（即不会出现一个对象将另一个对象吃掉的情况）组成。开始时所有对象都在南岸，到最后所有对象都在北岸。用Prolog规则表示就是

legal_states(location(s, s, s, s), location(n, n, n, n), States, X)

其中States是用来记录状态变化过程的动态表，在问题的开始，即农夫还没做任何事时，States存储的应该是初始状态；到最后，即农夫摆渡结束时，States中所存储的就是目标动作序列所对应的状态变化过程。

实施方案

下面是关系legal_states的一个实例：

legal_states(location(s, s, s, s), location(n, n, n, s), [location(n, n, n, s), location(s, s, n, s), location(n, s, n, s), location(s, s, s, s)], X)

上述状态按动作执行的时间在表中从右到左变化，表示农夫先带着羊渡河到北岸，然后独自返回到南岸，接着再带着狼渡河到北岸。过河问题的求解策略可以归结为：农夫先从四种摆渡动作中选择一种执行，执行后检查所生成的状态是不是和平的，如果和平，就继续执行下一个动作，生成新的状态并进行检查。重复这一过程，如果某一个动作完成后，生成的新状态与目标状态一致，求解过程就结束。

用States表示动态状态表，则上述渡河策略可以描述为：如果农夫执行一个动作将初始状态location(F0,W0,G0,C0)转变成新状态location(F1,W1,G1,C1)，以及如果location(F1,W1,G1,C1)是和平的，那么继续执行下一动作，同时States变为[location(F1,W1,G1,C1)| States]。这是一个递归的过程，我们需要一个特殊的情况作为出口条件。显然，当生成的新状态符合目标状态location(F,W,G,C)时，递归结束。用Prolog表示就是：

legal_states(location(F0,W0,G0,C0),location(F,W,G,C),States,X):-

transform(location(F0,W0,G0,C0),location(F1,W1,G1,C1)),

is_peaceful(F1,W1,G1,C1),

legal_states (location(F1,W1,G1,C1),location(F,W,G,C),[location(F1,W1,G1,C1)|States],X).

legal_states (location(F,W,G,C),location(F,W,G,C),L,L).

现在的任务是定义transform和is_peaceful这两个关系。transform表示执行一个动作将当前状态转变成一个新状态，is_peaceful用来检查新生成的状态是否和平。

先看transform，这个关系的一个实例是transform (location(s, s, s, s), location(n, s, n, s))，即农夫将山羊从南岸带到北岸时的状态变化。用规则描述过河问题中的四种动作所引起的状态变化情况，分别是：

·当农夫独自划船时，状态中唯一的变化就是农夫移动到对岸

·当农夫带着狼划船时，发生的状态变化就是农夫和狼移动到对岸。（但是这个规则只有农夫和狼从同一岸出发时才适用。）

·当农夫带着山羊划船时，与第二条规则相似，只是要将狼替换成山羊。

·当农夫带着白菜划船时，与第二条规则相似，但是要将狼替换成白菜。

转换成Prolog，这些规则分别为：

transform(location(X,W,G,C), location(Y,W,G,C)):-opposite(X,Y).

    transform(location(X,X,G,C), location(Y,Y,G,C)):-opposite(X,Y).

    transform(location(X,W,X,C), location(Y,W,Y,C)):-opposite(X,Y).

    transform(location(X,W,G,X), location(Y,W,G,Y)):-opposite(X,Y).

其中关系opposite可以由两个事实决定，即：

opposite(s, n).

opposite(n, s).

接着看is_peaceful。该关系用来检查某个状态是否和平。因为渡河过程中农夫和狼永远都不会有危险，所以一个和平的状态就是在这个状态下，山羊和白菜都是安全的。用Prolog表示就是：

is_peaceful(X):-safe_goat(X),

             safe_cabbage(X).

可以看出，必须定义safe_goat 和safe_cabbage才能完成is_peaceful的定义。因此，下面讨论如何定义这两个关系。

先看safe_goat。我们观察该关系的两个实例：safe_goat(n, n, n, s)和safe_goat(n, n, s, n)。为什么在这两个状态中山羊是安全的呢？在第一个例子中是因为羊与农夫在同一岸，这样一种状态可以用模式(X, _, X ,_)识别；在第二个例子中是因为狼在山羊的对岸，这里农夫的位置是不重要的，这样一种状态可以用(_, X, Y, _)表示，条件是X和Y是对岸关系。在Prolog中可以这样表示：

safe_goat(X ,_ X, _)

safe_goat(_, X, Y, _):-opposite(X, Y)

同理，关系safe_cabbage的Prolog规则可以如下：

safe_cabbage(X, _, _, X)

safe_cabbage(_, _, X, Y):-opposite(X, Y)

现在程序已经基本完成。输入目标进行询问：

legal_actions(location(s,s,s,s), location(n,n,n,n), [location(s,s,s,s)], X).

农夫过河问题得到解决了吗？

回顾解决方案

输入目标后，发生了堆栈溢出的现象，这是使用递归很容易出现的一个问题。如何解决这个问题呢？

（1）发生溢出的原因在于在我们的描述中，没有给Prolog足够的关于问题的知识，以致于解决方案被一些愚蠢的动作（例如把羊带过河，然后又马上带回来）所阻塞，搜索进入了死胡同。为了解决该问题，可以在legal_states这条规则的transform子目标后面加上一个条件：not(member(location(F1,W1,G1,C1),States))，用来判断是否发生了重复的动作。判断对象是表的成员是关于表的一个最常见的问题之一，其完整程序如下所示。

domains

   s_list=symbol*

predicates

   member(symbol,n_list)

clauses

   member(X,[X|_]).

   member(X,[_|T]):-member(X,T).

（2）再来测试，没有出现溢出现象，但是运行结果重复显示了相同的答案。原因是根据我们的描述，寻找答案的途径不只一条，通过反向跟踪，Prolog发现了其它方案，其根源在于safe_goat和safe_cabbage规则不够完善，例如，状态location(n, s, n, s)对于safe_goat的两条规则都是成立的。为了提高运行效率，我们应该保证在给定的状态下，这两条规则中最多只有一条是成功的。一个简单的方法就是，在每个关系的第二条规则的末尾加上条件F<>Y。

（3）现在再次测试，程序输出了两个答案，即过河问题的两种解决方案。但是输出的是两个状态变化过程，不是题目要求的动作序列，因此需要一个将状态变化转换成动作执行过程的规则。我们用write_out关系实现这个功能。

过河问题的完整程序如图1所示，该程序在Turbo Prolog 2.0环境下运行通过，程序的目标需要在程序运行时临时给出，同时注意答案要反向读。

domains                        /*领域段，说明程序要用到的数据类型*/
  bt=boat(symbol,symbol)
  ln=location(symbol,symbol,symbol,symbol)
  lists=ln*
predicates                      /*谓词段，说明程序要用到的谓词名和参数*/
  opposite(symbol,symbol)
  safe_goat(symbol,symbol,symbol,symbol)
  safe_cabbage(symbol,symbol,symbol,symbol)
  is_peaceful(symbol,symbol,symbol,symbol)
  transform(ln,ln)
  legal_states(ln,ln,lists,lists)
  member(ln,lists)
  write_state(ln,ln)
  write_actions(lists)
  boat(ln,ln)
clauses                        /*子句段，说明程序要用到的事实和规则*/
  opposite(s,n).
  opposite(n,s).
  safe_goat(X,_,X,_).
  safe_goat(F,X,Y,_):-opposite(X,Y),F<>Y.
  safe_cabbage(X,_,_,X).
  safe_cabbage(F,_,X,Y):-opposite(X,Y),F<>Y.
is_peaceful(F,W,G,C):-safe_goat(F,W,G,C),safe_cabbage(F,W,G,C).
  member(X,[X|_]).
  member(X,[_|T]):-member(X,T).
  transform(location(X,W,G,C),location(Y,W,G,C)):-opposite(X,Y).
  transform(location(X,X,G,C),location(Y,Y,G,C)):-opposite(X,Y).
  transform(location(X,W,X,C),location(Y,W,Y,C)):-opposite(X,Y).
  transform(location(X,W,G,X),location(Y,W,G,Y)):-opposite(X,Y).
legal_states(location(F0,W0,G0,C0),location(F,W,G,C),States,X):-
transform(location(F0,W0,G0,C0),location(F1,W1,G1,C1)),
        is_peaceful(F1,W1,G1,C1),not(member(location(F1,W1,G1,C1),States)),
        legal_states(location(F1,W1,G1,C1),location(F,W,G,C),[location(F1,W1,G1,C1)|States],X).
  legal_states(location(F,W,G,C),location(F,W,G,C),L,L).
  write_state(location(X,W,G,C),location(Y,W,G,C)):-!,write("The farmer crosses the river himself"),nl.
  write_state(location(X,X,G,C),location(Y,Y,G,C)):-!,write("The farmer crosses the river with the wolf"),nl.
  write_state(location(X,W,X,C),location(Y,W,Y,C)):-!,write("The farmer crosses the river with the goat"),nl.
  write_state(location(X,W,G,X),location(Y,W,G,Y)):-!,write("The farmer crosses the river with the cabbage"),nl.
write_actions([]).
write_actions([H1,H2|T]):-write_state(H1,H2),write_actions([H2|T]).    boat(location(F0,W0,G0,C0),location(F,W,G,C)):-
legal_states(location(F0,W0,G0,C0),location(F,W,G,C),[location(F0,W0,G0,C0)],X),
        write_actions(X).