湖南大学人工智能实验二:Prolog编程求解图搜索问题

说在前面:这个实验我也是抄的 真的有人会写prolog嘛?

代码链接:人工智能实验

文章目录

人工智能实验二:Prolog编程求解图搜索问题

一.实验目的

  1. 熟悉PROLOG的运行环境,进行PROLOG的基本编程练习;

    了解PROLOG语言中常量、变量的表示方法。PROLOG的简单程序结构,掌握分析问题、询问解释技巧;进行事实库、规则库的编写,并在此基础上进行简单的询问。

  2. 求解图搜索问题。

    任选一个以下实际应用题目:爱因斯坦的超级问题、字谜问题、汉诺塔问题、八数码问题、八皇后问题、农夫过河问题、传教士与野人问题

二.实验的硬件、软件平台

__硬件:__计算机

__软件:__操作系统:WINDOWS

__应用软件:__GNU Prolog

三.实验内容及步骤

熟悉prolog语言的使用并实现求解图搜索问题

实验步骤:

  1. 安装prolog集成开发环境
  2. 采用prolog编写所选问题的源程序
  3. 编译程序,输出查询问题的结果或数据

四.实验报告要求

  1. 通过PROLOG的基本编程练习,说明实验的方法和步骤;

  2. 针对图搜索要求,说明求解的问题与程序、程序分析、注释、运行结果等,在讨论与结论部分说明实验收获、难点重点讨论等;

  3. 附上所有实验源代码。

五.实验步骤

通过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).
  1. 既然是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).
  1. 接下来就是生成列号以及得到两个对角线的数值:
    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).
  1. 这样在最后,只需要保证列号,两条对角线均不相同,则可完成任务:
    fd_all_different(Cols),
    fd_all_different(Main_diag),
    fd_all_different(Diag).
运行结果

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QsnSdAVv-1609253228360)(C:\Users\a2783\AppData\Roaming\Typora\typora-user-images\image-20201121165519777.png)]

均符合要求

实验收获

这次实验最大的应该就是一定程度上掌握了prolog语言吧,了解到了还有一门这样的可以进行逻辑推理,编程也比较方便的语言。主要的难点部分的话,应该就是prolog语法的学习,因为在之前一直没有接触过,而且有的地方的不熟练也在一定程度上限制了编程,所以这次实验主要的时间都是耗费在了prolog的学习之上。

实验源代码

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).
上一篇:熟悉编程语言


下一篇:熟悉编程语言