实验二 搜索策略
一、实验目的
加深学生对图搜索技术的理解，使学生掌握图搜索基本编程方法，并能利用图搜索技术解决一些应用问题。
1. 掌握Visual prolog软件编程方法； 2. 熟悉状态图和与或图搜索的基本算法；
3．掌握图搜索问题求解中的问题表示、节点表示、close表和open表的构造。
二、实验环境
计算机，Visual PROLOG教学软件
三、预习要求
1. 预习教材中有关状态图和与或图问题求解的内容，熟悉状态图和与或图求解的过程和方法；
2. 了解Visual PROLOG程序设计的基本知识。
四、实验内容
走迷宫是人们熟悉的一种游戏, 如图1就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点, 把通道作为边, 则该迷宫可以由一个有向图表示。 那么, 走迷宫其实就是从该有向图的初始节点（入口）出发, 寻找目标节点（出口）的问题, 或者是寻找通向目标节点（出口）的路径的问题。
用状态图搜索或与或图搜索方法，求出迷宫图中路径。图中S0为入口，Sg为出口。
五、实验方法和步骤
1. 启动prolog编辑环境；
2. 用状态图搜索思想编辑迷宫问题求解的源程序； 3. 运行程序，分析结果；
4. 用与或图搜索思想编辑迷宫问题求解的源程序； 5．运行程序，分析结果。
六、示例程序
3
下面是一个通用的状态图搜索程序。对于求解的具体问题，只需将其状态图的程序表示并入该程序即可。
/*状态图搜索通用程序*/ DOMAINS
state=<领域说明> %例如: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
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(<初始状态>,<目标状态>),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),!.
4
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),nl,fail. resulting(_): -!.
rule(X,Y): -<问题中的状态转换规则>. % 例如: rule(X,Y): -road(X,Y).
七、实验报告要求
1. 实验报告应简单明了，语言通顺，结果正确，程序规范。实验报告的重点是实验结果的正确性与分析。包括：实验题目、要求、实验环境、实验内容与实验结果（要求附上运行的源程序）、实验中出现的问题、对问题的解决方案、实验总结等；
2. 迷宫问题求解的搜索结果及分析； 3．比较状态图搜索和与或图搜索的特点。
5
实验三 专家系统
一、实验目的
加深学生对专家系统原理的理解，使学生初步掌握专家系统的设计和实现方法。
二、实验环境
计算机，Visual PROLOG教学软件或VC++等
三、预习要求
1.了解专家系统设计与实现的一般方法；
2.熟悉和掌握产生式系统的运行机制、产生式规则的程序语言实现。
四、实验原理
产生式系统用来描述若干个不同的以一个基本概念为基础的系统，这个基本概念就是产生式规则或产生式条件和操作对。在产生式系统中，论域的知识分为两部分：用事实表示静态知识；用产生式规则表示推理过程和行为。
五、实验内容
综合利用人工智能的产生式系统、图搜索算法以及专家系统的框架，建造一个小型的医疗诊断专家系统，要求系统具有知识库、推理机和动态数据库三部分。编程语言不限。
六、示例程序
下面给出一个示例程序，以供参考。 例：小型动物分类专家系统
/* An Animal Classifying Expert System */ database
xpositive(symbol,symbol) xnegative(symbol,symbol) predicates run
animal_is(symbol) it_is(symbol)
positive(symbol,symbol) negative(symbol,symbol) clear_facts
remember(symbol,symbol,symbol) ask(symbol,symbol) goal
6
run. clauses run:-
animal_is(X),!
write(\ run:-
write(\ write(\ positive(X,Y):-xpositive(X,Y),!.
positive(X,Y):-not(xnegative(X,Y)),ask(X,Y). negative(X,Y):-xnegative(X,Y),!.
negative(X,Y):-not(xnegative(X,Y)),ask(X,Y). ask(X,Y):-
write(X,\ readln(Reply), remember(X,Y,Reply).
remember(X,Y,y):-asserta(xpositive(X,Y)). remember(X,Y,n):-asserta(xnegative(X,Y)),fail. clear_facts:-retract(xpositive(_,_)),fail. clear_facts:-retract(xnegative(_,_)),fail.
clear_facts:-write(\ animal_is(cheetah):- it_is(mammal), it_is(carnivore)), positive(has,tawny_color), positive(has,black_spots). animal_is(tiger):- it_is(mammal), it_is(carnivore),
positive(has,tawny_color), positive(has,black_stripes). animal_is(giraffe):- it_is(ungulate), positive(has,long_neck), positive(has,long_legs), positive(has,dark_spots). animal_is(zebra):- it_is(ungulate),
positive(has,black_stripes). animal_is(ostrich):- it_is(bird), negtive(does,fly), positive(has,long_neck),
7
