华北电力大学
实 验 报 告
实验名称 图搜索问题求解
课程名称 人工智能及应用
专业班级： 学生姓名： 号：
成 绩：
指导教师： 李继荣 实验日期： 2014.5| |
| |
学
华 北 电 力 大 学 实 验 报 告
一、实验目的及要求 熟悉PROLOG语言的特点和某种PROLOG编程环境；掌握编写与调试简单的PROLOG程序的方法。通过设计、编写和调试了解PROLOG编译器；掌握PROLOG语言中常量、变量的表示方法和PROLOG进行事实库、规则库的编写方法。加深对逻辑程序运行机理的理解，掌握PROLOG语言的特点，熟悉其编程环境。针对实际应用问题，分析题目背景，利用编程实现图搜索技术的问题求解方法，以牢固掌握图搜索技术的基本原理和常用算法，加深对图搜索技术的理解。 实验要求采用PROLOG编程求解8*8骑士周游问题以及农夫、狼、羊、菜问题。采用熟悉的高级语言编程实现“过河问题”、“九宫格”等问题的求解。 二、所用仪器、设备 计算机、TRINC－PROLOG及高级语言程序设计环境。 三、实验原理 1. 8*8骑士周游问题求解，以squre（x，y）表示骑士的位置，然后寻找一条是否存在的路径判断是否存在此路径的周游方法。通过x与y的值的范围，判断是否可以向左右方向移动，达到求解周游的问题。 2. 农夫、狼、羊、菜问题求解，采用宽度优先搜索算法，寻找一条安全的路径，农夫把三物品从河的一岸送到对岸，设计状态state（x，y，z，w）表示当前四物所处在的状态，按照算法寻找出最后的路径。 3. 四皇后问题解决，封装Queen类，包括皇后个数，以及皇后位置是否正确而的判断方法，然后再主方法中调用方法即可。 4. 极大极小方法求解井字棋问题，对状态空间采用最大最小值搜索，计算机在生成的子节点中选择评估函数值最大的节点，而计算机在选择着数时使人选择评估函数值最小的节点，也就是对计算机一方最不利的节点。 四、实验方法与步骤 1. 8*8骑士周游问题，通过当前点的坐标范围判断是否可以向“加一”，“加二” 方向移动，而实现8*8周游问题的解决。通过对横纵坐标的范围，确定是否可以对其进行移动而得到判断，只需要写好对应的坐标变化，然后与当前要移动的坐标是否合一，而确定是否存在这样的路径。Path（）则是对于在两坐标判断是否存在其中的路径然后对其蕴含式的解析。 当path（x，y）的x与y参数相同是则退出。 实现算法： move(squre(Row,Column),squre(New_Row,New_Column)):- Row=<6,New_Row is Row+2,Column=<7,New_Column is Column+1. 第 1 页 共 4 页
华 北 电 力 大 学 实 验 报 告
move(squre(Row,Column),squre(New_Row,New_Column)):- Row=<6,New_Row is Row+2,Column>=2,New_Column is Column-1. move(squre(Row,Column),squre(New_Row,New_Column)):- Row>=3,New_Row is Row-2,Column=<7,New_Column is Column+1. move(squre(Row,Column),squre(New_Row,New_Column)):- Row>=3,New_Row is Row-2,Column>=2,New_Column is Column-1. move(squre(Row,Column),squre(New_Row,New_Column)):- Row=<7,New_Row is Row+1,Column=<6,New_Column is Column+2. move(squre(Row,Column),squre(New_Row,New_Column)):- Row=<7,New_Row is Row+1,Column>=3,New_Column is Column-2. move(squre(Row,Column),squre(New_Row,New_Column)):- Row>=2,New_Row is Row-1,Column=<6,New_Column is Column+2. move(squre(Row,Column),squre(New_Row,New_Column)):- Row>=2,New_Row is Row-1,Column>=3,New_Column is Column-2. been(squre(0,0)). path(X,X). path(X,Y):-move(X,Z),not(been(Z)),dynamic(knight_tour,been/1),asserta(knight_tour,been(Z)),path(Z,Y). 2. 农夫、狼、羊、菜过河问题，定义状态state（x，y，z，w）表示四个物体当前所在的位置（河东还是河西用e跟w表示），move（state（x，y，z，w），state（u，v，w，g））表示从和的一岸向另一岸移动，当然移动必须满足要求，移动之后的状态必须处在一个安全的状态，用unsafe（state（））来检测所处位置是否安全，并且是农夫与移动的物体一起移动，采用go（start，goal）表示从现在开始的状态以及要达到的目标态而进行路径搜索，path(Open_queue,Closed_set,Goal)表示移动路径所需要满足的条件之一，即就是本宽度算法中的open，closed表，当然在本算法中涉及到队列的各种方法，拼接，判空等操作都需要在算法中给予具体的实现。 具体实现的算法为： move(state(X,X,G,C),state(Y,Y,G,C)):-opp(X,Y). move(state(X,W,X,C),state(Y,W,Y,C)):-opp(X,Y). move(state(X,W,G,X),state(Y,W,G,Y)):-opp(X,Y). move(state(X,W,G,C),state(Y,W,G,C)):-opp(X,Y). 第 2 页 共 4 页
华 北 电 力 大 学 实 验 报 告
unsafe(state(X,Y,Y,C)):-opp(X,Y). unsafe(state(X,W,Y,Y)):-opp(X,Y). opp(e,w). opp(w,e). go(Start,Goal):-empty_queue(Empty_open_queue), enqueue([Start,nil],Empty_open_queue,Open_queue), empty_set(Closed_set), path(Open_queue,Closed_set,Goal). path(Open_queue,_,_):-empty_queue(Open_queue), write(\ path(Open_queue,Closed_set,Goal):- dequeue([State,Parent],Open_queue,_),State=Goal, write(\ printsolution([State,Parent],Closed_set). %printsolution1(Closed_set). path(Open_queue,Closed_set,Goal):- dequeue([State,Parent],Open_queue,Rest_open_queue), get_children(State,Rest_open_queue,Closed_set,Children), add_list_to_queue(Children,Rest_open_queue,New_open_queue), union([[State,Parent]],Closed_set,New_closed_set), path(New_open_queue,New_closed_set,Goal). get_children(State,Rest_open_queue,Closed_set,Children):- bagof(Child,moves(State,Rest_open_queue,Closed_set,Child),Children). moves(State,Rest_open_queue,Closed_set,[Next,State]):- move(State,Next),not(unsafe(Next)), not(member_queue([Next,_],Rest_open_queue)), not(member_set([Next,_],Closed_set)). 第 3 页 共 4 页
华 北 电 力 大 学 实 验 报 告
%printsolution1(L):-empty_set(L). %printsolution1([H|T]):-printsolution1(T),write(H),nl. printsolution([State,nil],_):-write(State),nl. printsolution([State,Parent],Closed_set):- member_set([Parent,Grandparent],Closed_set), printsolution([Parent,Grandparent],Closed_set), write(State),nl. empty_set([]). member_set([State,Parent],[[State, Parent]|_]). member_set(X,[_|T]):-member_set(X,T). empty_queue([]). enqueue(E,[],[E]). enqueue(E,[H|T],[H|Tnew]):-enqueue(E,T,Tnew). dequeue([State,Parent],[[State,Parent]|T],T). add_list_to_queue(List,Queue,New_queue):-append(Queue,List,New_queue). append(X,Y,Z):-X=[],Z=Y. append(X,Y,Z):-X=[A|B],Z=[A|W],append(B,Y,W). member(X,[X|T]). member(X,[_|T]):-member(X,T). member_queue(Element,Queue):-member(Element,Queue). union([],Set,Set). 第 4 页 共 4 页