基于Prolog编程求解图搜索问题(人工智能实验)【100012173】

# 人工智能实验二：Prolog编程求解图搜索问题 ## 一.实验目的 熟悉PROLOG的运行环境，进行PROLOG的基本编程练习； 了解PROLOG语言中常量、变量的表示方法。PROLOG的简单程序结构，掌握分析问题、询问解释技巧；进行事实库、规则库的编写，并在此基础上进行简单的询问。 求解图搜索问题。 任选一个以下实际应用题目：爱因斯坦的超级问题、字谜问题、汉诺塔问题、八数码问题、八皇后问题、农夫过河问题、传教士与野人问题。 ## 二.实验的硬件、软件平台 硬件：计算机 软件：操作系统：WINDOWS 应用软件：GNU Prolog ## 三.实验内容及步骤 熟悉prolog语言的使用并实现求解图搜索问题 实验步骤： 安装prolog集成开发环境 采用prolog编写所选问题的源程序 编译程序，输出查询问题的结果或数据 ## 实验步骤 通过PROLOG的基本编程练习，说明实验的方法和步骤 原子：小写字母开头 变量：大写字母开头 符合用来组成事实 规则：且：, 或：. 非：\+ ``` loves(jack,mia). loves(marsellus,mia). loves(mike,john). loves(john,mike). jealous(X,Y):- loves(X,Z), loves(Y,Z). ``` ``` | ?- jealous(jack, marsellus). yes | ?- jealous(mike, john). no ``` 列表：[A, B, C]，可以通过[Head|Tail]解析 ``` | ?- [Head|Tail] = [A, B, C]. Head = A Tail = [B,C] yes ``` 匿名变量：_ ``` | ?- [A, B, C, D] = [_,Head|Tail]. Head = B Tail = [C,D] yes ``` 内置谓词 member:检查某一个值是否在一个列表内 fd_all_different:检查列表中是否有重复元素 fd_domain:验证值是否在一个范围之内 length：获取列表的长度 针对图搜索要求，说明求解的问题与程序、程序分析、注释、运行结果等，在讨论与结论部分说明实验收获、难点重点讨论等 求解的问题 在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 程序 ``` valid((_,Col)):- Range = [1,2,3,4,5,6,7,8], member(Col,Range). valid_board([]). valid_board([Head|Tail]):- valid(Head),valid_board(Tail). cols([],[]). cols([(_,Col)|QueensTail],[Col|ColsTail]):- cols(QueensTail,ColsTail). main_diag([],[]). main_diag([(Row,Col)|QueensTail],[Diagonal|DiagonalsTail]):- Diagonal is Col - Row, main_diag(QueensTail,DiagonalsTail). diag([],[]). diag([(Row,Col)|QueensTail],[Diagonal|DiagonalsTail]):- Diagonal is Col + Row, diag(QueensTail,DiagonalsTail). eight_queens(Board) :- Board = [(1, _), (2, _), (3, _), (4, _), (5, _), (6, _), (7, _), (8, _)], valid_board(Board), cols(Board,Cols), main_diag(Board,Main_diag), diag(Board,Diag), fd_all_different(Cols), fd_all_different(Main_diag), fd_all_different(Diag). ``` ##### 程序分析及注释 1.主体部分： ``` eight_queens(Board) :- Board = [(1, _), (2, _), (3, _), (4, _), (5, _), (6, _), (7, _), (8, _)], valid_board(Board), cols(Board,Cols), main_diag(Board,Main_diag), diag(Board,Diag), fd_all_different(Cols), fd_all_different(Main_diag), fd_all_different(Diag). ``` 2.既然是8皇后问题，自然要定义一个8 * 8的棋盘，根据约束条件：不能位于同一行，所以按照prolog的语法棋盘可表示为： ``` Board = [(1, _), (2, _), (3, _), (4, _), (5, _), (6, _), (7, _), (8, _)] ``` 棋盘生成之后就需要检查是否符合范围要求，即是不是在棋盘上： ``` valid_board(Board). ``` 由于Board是以列表的形式呈现，所以可以用之前提到的[Head|Tail]进行判断，检查Head指向的当前第一个元素是不是符合要求，再将剩余的Tail作为新的列表继续。检查是不是符合时，只需要判断列号是不是在1-8的范围内，这个可以用到内置谓词member判断是不是在范围内。具体实现为 ``` valid((_,Col)):- Range = [1,2,3,4,5,6,7,8], member(Col,Range). valid_board([]). valid_board([Head|Tail]):- valid(Head),valid_board(Tail). ``` 3.接下来就是生成列号以及得到两个对角线的数值： ``` cols(Board,Cols), main_diag(Board,Main_diag), diag(Board,Diag), ``` 对于Col列号，只需要从棋盘中取出即可 ``` cols([],[]). cols([(_,Col)|QueensTail],[Col|ColsTail]):- cols(QueensTail,ColsTail). ``` 而对于两个对角线，则需要通过计算：主对角线为列 - 行，副对角线为列 + 行 ``` main_diag([],[]). main_diag([(Row,Col)|QueensTail],[Diagonal|DiagonalsTail]):- Diagonal is Col - Row, main_diag(QueensTail,DiagonalsTail). diag([],[]). diag([(Row,Col)|QueensTail],[Diagonal|DiagonalsTail]):- Diagonal is Col + Row, diag(QueensTail,DiagonalsTail). ``` 4.这样在最后，只需要保证列号，两条对角线均不相同，则可完成任务： ``` fd_all_different(Cols), fd_all_different(Main_diag), fd_all_different(Diag). ```