人工智能技术基础图搜索问题求解
实验报告
一、实验目的
加强对图搜索技术的理解，初步掌握图搜索基本编程方法,并能运用图搜索技术解决一些应用问题。
二、实验要求
（1）可使用第3章中的状态图搜索通用程序，这时只需编写规则集程序；也可以用PROLOG 语言或其他语言另行编写。
（2）程序运行时，应能在屏幕上显示程序运行结果。
三、实验内容或题目
实验题目：迷宫求解
实验内容：利用状态图搜索方法求解下列迷宫图
入口
出口12345
12345
四、实验步骤与源程序
实验步骤：
(1) 理解题目；
(2) 对状态进行编码；
(3)转换规则集；
(4)编写程序；
(5)调试运行；
源程序：
/*状态图搜索通用程序*/
DOMAINS
state=symbol %例如:state=symbol
DATABASE-mydatabase
open(state,integer) %用动态数据库实现OPEN表
closed(integer,state,integer) %和CLOSED表
res(state)
open1(state,integer)
min(state,integer)
mark(state)
fail_
PREDICATES
solve
road(state,state)
search(state,state)
result
searching
step4(integer,state)
step56(integer,state)
equal(state,state)
repeat
resulting(integer)
rule(state,state)
GOAL
solve.
CLAUSES
solve:- search(s,e),result.
/*例如
solve:-
search(st(0,1,2,3,4,5,6,7,8),st(0,2,8,3,4,5,6,7,1)),result. */
search(Begin,End):- %搜索
retractall(_,mydatabase),
assert(closed(0,Begin,0)),
assert(open(Begin,0)), %步1 将初始节点放入OPEN表
assert(mark(End)),
repeat,
searching,!.
result:- %输出解
not(fail_),
retract(closed(0,_,0)),
closed(M,_,_),
resulting(M),!.
result:- %输出解
not(fail_),
retract(closed(0,_,0)),
closed(M,_,_),
resulting(M),!.
result:- beep,write("sorry don't find a road!").
searching:-
open(State,Pointer), %步2 若OPEN表为空,则失败,退出
retract(open(State,Pointer)), %步3 取出OPEN表中第一个节点,给其
closed(No,_,_),No2=No+1, %编号
asserta(closed(No2,State,Pointer)), %放入CLOSED表
!,step4(No2,State).
searching:-assert(fail_).
%步4 若当前节点为目标节点,则成功
step4(_,State):- mark(End),equal(State,End). %转步2
step4(No,State):- step56(No,State),!,fail.
step56(No,StateX):- %步5 若当前节点不可扩展,转步2
rule(StateX,StateY), %步6 扩展当前节点X得Y
not(open(StateY,_)), %考查Y是否已在OPEN表中
not(closed(_,StateY,_)), %考查Y是否已在CLOSED表中
assertz(open(StateY,No)), %可改变搜索策略
fail.
step56(_,_):-!.
equal(X,X).
repeat.
repeat:-repeat.
resulting(N):- closed(N,X,M),asserta(res(X)),resulting(M).
resulting(_):- res(X),write(X),write("\t"),fail.
resulting(_):- !.
rule(X,Y):-road(X,Y).
road(s,s11).road(s11,s12).road(s12,s11).road(s12,s13).road(s13,s12).road(s13,s14).r oad(s14,s13).road(s11,s21).road(s21,s11).road(s12,s22).
road(s15,s25).road(s25,s15).road(s23,s24).road(s24,s23).road(s24,s25).road(s25,s24) .road(s21,s31).road(s31,s21).road(s23,s33).road(s33,s23).
road(s24,s34).road(s34,s24).road(s25,s35).road(s35,s25).
road(s31,s32).road(s32,s31).road(s32,s33).road(s33,s32).road(s34,s35).
road(s35,s34).road(s31,s41).road(s41,s31).road(s34,s44).road(s44,s34).road(s42,s43) .
road(s43,s42).road(s43,s44).road(s44,s43).road(s44,s45).road(s45,s44).road(s42,s52) .
road(s52,s42).road(s51,s52).road(s52,s51).road(s52,s53).road(s53,s52).road(s53,s54) .road(s54,s53).road(s54,s55).road(s55,s54).road(s55,e) .
%例如:rule(X,Y):-road(X,Y).
五、实验结果
六、实验总结
该实验的例题较为特殊，要实现深度优先和广度优先搜索，在源代码中修改一致，只需将assertz(open(StateY,No))改为asserta(open(StateY,No))。
实验刚开始出现运行错误，road未定义，在PREDICATES中给road加以定义
road(state,state)。
之后运行还有一个报错，经过反复检查，发现最后结尾语句没加句号。
因为急于验收，修改完代码，直接加载，导致犯下一个结尾少加句号的低级错误，耗时耗力，影响进度。
随着今后编程的增多，深深体会到编程时要静心严谨，否则一个小小的疏忽，将增加额外的工作量。
通过第二次上机实验，自己对prolog运行平台的使用更为熟练。
今后课下会多多关注人工智能方面的科研资讯，学习课外的知识，增加自己知识储备，提高自己的专业技能。