《人工智能导论》实验指导书(新)

实验一 PROLOG语言编程练习·································2

实验二图搜索问题求解······································4

实验三小型专家系统(原型)设计······························7

实验一 PROLOG语言编程练习

一、 实验目的

加深学生对逻辑程序运行机理的理解，使学生掌握PROLOG语言的特点、熟悉其编程环境，同时为后面的人工智能程序设计做好准备。

1、熟悉PROLOG语言编程环境的使用；

2、了解PROLOG语言中常量、变量的表示方法；

3、了解利用PROLOG进行事实库、规则库的编写方法；

二、 实验环境

计算机，Turbo PROLOG教学软件。

三、 预习要求

实验前应阅读实验指导书，了解实验目的、预习PROLOG语言的相关知识。

四、 实验内容

1、学习使用Turbo PROLOG，包括进入PROLOG主程序、编辑源程序、修改环境目录、退出等基本操作。

2、在Turbo prolog集成环境下调试运行简单的Turbo PROLOG程序。

3、编写一个描述亲属关系的PROLOG程序，然后再给出一些事实数据，建立一个小型演绎数据库。可以以父亲和母亲为基本关系（作为基本谓词），再由此来描述祖父、祖母、兄弟、姐妹以及其他亲属关系。

4、修改教材2.2节例2.9的程序，使其能输出图中所有路径（path）。

五、 实验方法和步骤

1、启动Windows XP操作环境。

2、打开文件目录，执行prolog应用程序，启动Turbo prolog，并按空格键(SPACE)进入集成开发环境。

3、选择Setup项，打开下拉菜单，选择Directories项，进行工作目录修改，按Esc键退出，选择Save Configuration项，保存修改。

4、选择Files项，打开下拉菜单，选择New file项，进入源程序输入和编辑，或选择Load项，选择要打开的示例程序，再选择Edit项，可以进行编辑源程序。

5、编辑之后，可以选择Run项，执行程序，可以在Dialog窗口进行询问，即外部目标的执行，查看程序运行结果，分析程序之功能。

6、仿前例，可以选择其他程序并运行，分析程序功能。

7、退出，选择Quit项，可以退出Turbo Prolog程序，返回到Windows XP环境。

六、 示例程序

一个简单的学生成绩数据库查询程序。

predicates

student(integer,string,real)

grade

goal

grade.

clauses

student(1,"zhang",90.2).

student(2,"li",95.5).

student(3,"wang",96.4).

grade:-write("please input the name:"),

readln(Name),

student(_,Name,Score),

nl,write(Name," score is:",Score).

grade:-write("Sorry,can't find the student!").

七、 实验报告要求

实验报告应简单明了，语言通顺，结果正确，程序规范。实验报告的重点是实验结果的正确性与分析。包括：实验题目、要求、实验环境、实验内容与实验结果（要求附上运行的源程序）、实验中出现的问题、对问题的解决方案、实验总结等。

实验二图搜索问题求解

一、实验目的

加深学生对图搜索技术的理解，使学生掌握图搜索基本编程方法，并能利用图搜索技术解决一些应用问题。

1. 掌握Turbo prolog软件编程方法；

2. 熟悉状态图和与或图搜索的基本算法；

3．掌握图搜索问题求解中的问题表示、节点表示、close表和open表的构造。

二、 实验环境

计算机，Turbo PROLOG教学软件

三、 预习要求

1. 预习教材中有关状态图和与或图问题求解的内容，熟悉状态图和与或图求解的过程和方法；

2. 了解Turbo PROLOG程序设计的基本知识。

四、 实验内容

走迷宫是人们熟悉的一种游戏, 如图1就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点, 把通道作为边, 则该迷宫可以由一个有向图表示。那么, 走迷宫其实就是从该有向图的初始节点（入口）出发, 寻找目标节点（出口）的问题, 或者是寻找通向目标节点（出口）的路径的问题。

用状态图搜索或与或图搜索方法，求出迷宫图中路径。图中S₀为入口，Sg为出口。

图1 迷宫图

五、 实验方法和步骤

1. 启动prolog编辑环境；

2. 用状态图搜索思想编辑迷宫问题求解的源程序；

3. 运行程序，分析结果；

4. 用与或图搜索思想编辑迷宫问题求解的源程序；

5．运行程序，分析结果。

六、 示例程序

下面是一个通用的状态图搜索程序。对于求解的具体问题，只需将其状态图的程序表示并入该程序即可。

/*状态图搜索通用程序*/

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),!.

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．比较状态图搜索和与或图搜索的特点。

实验三小型专家系统(原型)设计

一、实验目的

加深学生对专家系统原理的理解，使学生初步掌握专家系统的设计和实现方法。

二、实验环境

计算机，Turbo 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

run.

clauses

run:-

animal_is(X),!

write("\nYour animal may be a(n)",X),n1,n1,clear_facts.

run:-

write("\Unbale to determine what"),

write("your animal is. \n\n"),clear_facts.

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,"it",Y,"\n"),

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("\n\nPlease press the space bar to Exit"),readchar(_).

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),

positive(has,long_legs),

positive(has,black_and_white_color).

animal_is(penguin):-

it_is(bird),

negtive(does,fly),

positive(does,swim),

positive(has,black_and_white_color).

animal_is(albatross):-

it_is(bird),

positive(does,fly_well).

it_is(mammal):-

positive(has,hair).

it_is(mammal):-

positive(does,give_milk).

it_is(bird):-

positive(has,feathers).

it_is(bird):-

positive(does,fly),

positive(does,lay_eggs).

it_is(carnivore):-

positive(does,eat_meat).

it_is(carnivore):-

positive(has,pointed_teeth),

positive(has,claws),

positive(has,forward_eyes).

it_is(ungulate):-

it_is(mammal),

positive(has,hooves).

it_is(ungulate):-

it_is(mammal),

positive(does,chew_cud).

七、实验报告要求

第二篇：人工智能导论实验指导书

实验一基本的搜索技术

【实验目的】

通过运行演示程序，理解深度优先、广度优先、A*算法的原理和运行过程。

【实验内容】

1. 分别以深度优先、广度优先、A*算法为例演示搜索过程

2. 观察运行过程记录搜索顺序

3. 设置不同属性，观察和记录搜索过程的变化

4. 分析不同算法的特点

【实验原理】

在知识不完全时，一般不存在成熟的求解算法可以利用，只有利用已有的知识摸索前进，从许多可能的解中寻找真正的解这就是搜索。即使对于结构性能较好，理论上有算法可依的问题，由于问题本身的复杂性以及计算机在时间、空间上的局限性，往往也需要通过搜索来进行求解。

总的来说搜索策略分为两大类：盲目搜索和启发式搜索

一、无信息的搜索策略——盲目搜索

在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随即调用操作算子）进行的搜索，它能快速地运用一个操作算子。盲目搜索中，由于没有可参考的信息，因此只要能匹配的操作算子都须运用，这会搜索更多的状态。最重要的宽度优先和深度优先是最重要的盲目搜索方法。

1. 宽度优先搜索：从根结点出发，按从低到高的层次顺序搜索，同一层的结点按固定的顺序（例如从左到右、从右到左）搜索。宽度优先总是先搜索到距离最近的目标结点。宽度优先搜索不适合用于分支较多的情况。

2. 深度优先搜索：用回溯的思想搜索图。深度优先搜索适用于分支较多而层次较浅的情况。

二、利用知识引导搜索——启发式搜索

盲目搜索复杂度很大，为了提高算法效率，应该具体问题具体分析，利用与问题有关的信息，从中得到启发而来引导搜索，以达到减少搜索量的目的，这就是启发式搜索。

启发信息：

(1) 陈述性启发信息：一般被用于更准确、更精炼地描述状态，使问题的状态空间缩小,如待求问题的特定状况等属于此类信息

(2) 过程性启发信息：一般被用于构造操作算子，使操作算子少而精如一些规律性知识等属于此类信息

(3) 控制性启发信息：如何选择操作算子

控制性启发信息往往被反映在估价函数之中。估价函数的任务就是估计待搜索结点的“有希望”程度(或者说估计操作算子的“性能”)，并依此给它们排定次序。

估价一个结点的价值，必须综合考虑两方面的因素：已经付出的代价(实际)和将要付出的代价(估计)

f (n) = g (n) + h (n)

采用这种估价函数的搜索叫A搜索。令h^*(n)为n到目的结点的实际最小代价，如果对任意节点n均有h(n)≤h*(n)，则此时的A算法为A^*算法。

如某一问题有解，那么利用A*搜索算法对该问题进行搜索则一定能搜索到解，并且一定能搜索到最优的解而结束。

这三种搜索算法都使用了两张表来记录状态信息：在open表中保留所有已生成而子状态未扩展的状态；在closed表中记录已扩展过子状态的状态。

广度优先搜索算法中的open表采用的是先进先出的“队列”。

深度优先搜索算法中的open表采用的是后进先出的“栈”。

启发式搜索算法中的open表中的元素是按启发估价函数值的大小排列的一个表，每次从表中优先取出启发估价函数值最小的状态加以扩展。同时并不丢弃其它的状态，而把它们保留在open表中。

【实验步骤】

1. 浏览器打开下面网址，单击“Start Applet”按钮进入演示系统

http://cai.csu.edu.cn/jpkc/rengongzhineng/rengongzhineng/search/search.html

2. 单击主菜单中“File”→“Load Sample Graph”，载入一个例子（例如“简单搜索树”），如图2红色椭圆标注，激活左侧“create”卡，鼠标指针指向右侧图中的结点或边，右击弹出菜单，单击“Properties”（即属性），可以查看或修改结点或边的属性。结点的heuristics属性表示结点的启发值，边的Edge cost属性表示边的代价。

（A^*算法中结点的估价函数值为从开始结点到该结点所有边的代价和再加上该结点的启发值。

如图3所示B的估价值为13。）

3. 查看并记录所有结点的启发值和边的代价。

4. 激活左侧的“Solved”卡，如图4红色椭圆标注

5. 单击主菜单中“Search Algorithms”，分别选定“Depth First”、“Breadth First”、“A^*”。重复单击左侧“Step”按钮（图4蓝色椭圆标注），直到右侧图中所有结点访问完毕。记录访问的结点顺序，并与自己预测的深度优先、宽度优先、A^*的搜索顺序比较。

（注：运行过程中红色的结点保存于closed表中，绿色的结点保存于open表中，蓝色的结点表示新展开的结点）

6. 单击主菜单中“File”→“Create new Graph”，激活左侧“create”卡，新建一个图。分别选定“Depth First”、“Breadth First”、“A^*”，进行搜索，记录搜索顺序，并与自己预测的深度优先、宽度优先、A^*的搜索顺序比较。

实验二传教士和野人问题

【实验目的】

通过具体问题的编程求解，了解人工智能的基本解决方法；使用一种搜索策略，以加深理解。

【实验内容】

设在河的一岸有三个野人、三个传教士和一条船，要用这条船把所有的人运到河对岸，但受以下条件的约束：

(1) 传教士和野人都会划船，但每次船上至多可载两个人；

(2) 二是在河的任一岸，如果野人数目超过修道士数，传教士会被野人吃掉。

(3) 如果野人会服从任何一次过河安排

编程实现一个确保传教士和野人都能过河，且没有传教士被野人吃掉的安全过河计划。

【实验原理】

传教士和野人问题是一个经典的智力游戏问题。有N个传教士和N个野人来到河边准备渡河，河岸(甲岸和乙岸)有一条船，每次至多可供k人乘渡。应如何规划摆渡方案，使得任何时刻，在河的两岸以及船上的野人数目总是不超过传教士的数目。即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M（传教士数）≥C（野人数）和M＋C≤k的摆渡方案。

设N＝3，k＝2，则给定的问题可用下图表示，图中L和R表示左岸和右岸，B＝1或0分别表示有船或无船。约束条件是：两岸上M≥C，船上M＋C≤2

简单的分析，总共有10种可能的操作：

两个野人过河（从甲到乙，从乙到甲)

两个传教士过河从（从甲到乙，从乙到甲)

一个传教士和一个野人过河（从甲到乙，从乙到甲)

一个野人过河（从甲到乙，从乙到甲)

一个传教士过河（从甲到乙，从乙到甲)

但对于一个具体状态，只有5种可能的操作（从甲到乙或从乙到甲)。

先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：

初始状态：甲岸，3野人，3牧师；

乙岸，0野人，0牧师；

船停在甲岸，船上有0个人；

目标状态：甲岸，0野人，0牧师；

乙岸，3野人，3牧师；

船停在乙岸，船上有0个人；

整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：

渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师

算符知道以后，剩下的核心问题就是搜索方法了，本文以深度优先搜索为基础，通过一个FindNext(…)函数找出下一步可以进行的渡河操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。

搜索中的算符采用下面的规则固定排序，合理的排序能更快的搜索到较优的解：

甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；

同时注意下面两点：

1. 不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环;

2. 任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；

【实验过程】

设计程序求解传教士和野人问题。附录C++程序及注释如下：

//wildman.cpp

#include "iostream.h"

typedef struct _riverside // 岸边状态类型

{

int wildMan; // 野人数

int churchMan; // 牧师数

}RIVERSIDE;

typedef struct _boat // 船的状态类型

{

int wildMan; // 野人数

int churchMan; // 牧师数

}BOAT;

typedef struct _question // 整个问题状态

{

RIVERSIDE riverSide1; // 甲岸

RIVERSIDE riverSide2; // 乙岸

int side; // 船的位置, 甲岸为-1, 乙岸为1

BOAT boat; // 船的状态

_question* pPrev; // 指向前一渡船操作

_question* pNext; // 指向后一渡船操作

}QUESTION;

//函数定义

bool Process(QUESTION* pQuest);

bool FindNext(QUESTION* pQuest);

void VisitList(QUESTION* pQuest); //遍历链表输出结果

int main()

{

// 初始化

QUESTION* pHead = new QUESTION;

pHead->riverSide1.wildMan = 3;

pHead->riverSide1.churchMan = 3;

pHead->riverSide2.wildMan = 0;

pHead->riverSide2.churchMan = 0;

pHead->side = -1; // 船在甲岸

pHead->pPrev = NULL;

pHead->pNext = NULL;

pHead->boat.wildMan = 0;

pHead->boat.churchMan = 0;

if (Process(pHead))

{

cout<<"成功渡河！"<<endl;

VisitList(pHead);

}

else

cout<<"到底怎样才能渡河呢? 郁闷!"<<endl;

// 回收内存空间

while (pHead)

{

QUESTION* pTemp = pHead->pNext;

delete pHead;

pHead=pTemp;

}

pHead = NULL;

return 0;

}

// 渡船过程, 递归调用函数FindNext(...)

bool Process(QUESTION* pQuest)

{

if (FindNext(pQuest))

{

QUESTION* pNew = new QUESTION;

pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan + pQuest->boat.wildMan*(pQuest->side);

pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side);

pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan;

pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan;

pNew->side = (-1)*pQuest->side;

pNew->pPrev = pQuest;

pNew->pNext = NULL;

pNew->boat.wildMan = 0;

pNew->boat.churchMan = 0;

pQuest->pNext = pNew;

if (pNew->riverSide2.wildMan==3 && pNew->riverSide2.churchMan==3)

return true; // 完成

return Process(pNew);

}

else

{

QUESTION* pPrev = pQuest->pPrev;

if (pPrev == NULL)

return false; // 无解

delete pQuest;

pPrev->pNext = NULL;

return Process(pPrev); // 返回其父节点重新再找

}

return true;

}

// 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作

// 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧

bool FindNext(QUESTION* pQuest)

{

// 基本规则

// 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先.

static BOAT boatState[5]; // 5个算符

if (pQuest->side == -1)

{

boatState[0].wildMan = 2;

boatState[0].churchMan = 0;

boatState[1].wildMan = 1;

boatState[1].churchMan = 1;

boatState[2].wildMan = 0;

boatState[2].churchMan = 2;

boatState[3].wildMan = 1;

boatState[3].churchMan = 0;

boatState[4].wildMan = 0;

boatState[4].churchMan = 1;

}

else

{

boatState[0].wildMan = 0;

boatState[0].churchMan = 1;

boatState[1].wildMan = 1;

boatState[1].churchMan = 0;

boatState[2].wildMan = 0;

boatState[2].churchMan = 2;

boatState[3].wildMan = 1;

boatState[3].churchMan = 1;

boatState[4].wildMan = 2;

boatState[4].churchMan = 0;

}

int i; // 用来控制算符

if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0)

// 初始状态, 第一次渡河时

i = 0; // 取算符1

else

{

for (i=0; i<5; i++) // 扩展同一节点时, 已用过的算符不再用, 按优先级来

if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)

break;

i++;

}

if (i < 5)

{

int j;

for (j=i; j<5; j++)

{

int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;

int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;

int nWildMan2 = 3 - nWildMan1;

int nChurchMan2 = 3 - nChurchMan1;

// 判断本次操作的安全性, 即牧师数量>=野人或牧师数为0

if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&

(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&

nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)

{

// 本操作是否重复上次操作,注意方向不同

if (pQuest->pPrev != NULL)

{

if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&

pQuest->pPrev->boat.churchMan == boatState[j].churchMan)

continue;

}

break; // 该操作可行, 推出循环

}

if (j < 5)

{

pQuest->boat.wildMan = boatState[j].wildMan;

pQuest->boat.churchMan = boatState[j].churchMan;

return true;

}

return false;

}

//遍历链表输出结果

void VisitList(QUESTION* pQuest)

{

QUESTION* HD=pQuest;

cout<<"甲岸[野人,传教士]数量的变化:"<<endl;

while(HD!=NULL)

{

cout<<"["<<(HD->riverSide1).wildMan<<","<<HD->riverSide1.churchMan<<"]";

if(HD->pNext!=NULL)

cout<<"-->";

HD=HD->pNext;

}

cout<<endl;

}

实验三八数码问题

【实验目的】

启发式搜索就是利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。本实验通过解决八数码问题，帮助学生更好的熟悉和掌握启发式搜索的定义、估价函数和算法过程。

【实验内容】

在3×3的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态S₀，目标状态S_g，如下图所示。可以使用的操作有

空格左移，空格上移，空格右移，空格下移

即只允许把位于空格左、上、右、下方的牌移入空格。请编程实现该问题的解决。

【实验原理】

一、搜索策略简介

1. 无信息的搜索策略——盲目搜索

在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随即调用操作算子）进行的搜索，它能快速地运用一个操作算子。盲目搜索中，由于没有可参考的信息，因此只要能匹配的操作算子都须运用，这会搜索更多的状态。

2. 有信息的搜索——启发式搜索

考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选取较合适的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态，提高搜索效率。

启发式搜索每使用一个操作算子便需做更多的计算与判断，其性能一般要优于盲目搜索，但不可过于追求更多的甚至完整的启发信息。

二、搜索算法

1. 辅助用的数据结构

open表：记录已生成但其子状态未扩展的状态。

closed表：记录其子状态已被扩展的状态。

(1) 广度优先搜索算法中的open表采用的是先进先出的“队列”。

(2) 深度优先搜索算法中的open表采用的是后进先出的“栈”。

(3) 启发式搜索算法中的open表中的元素是按启发估价函数值的大小排列的一个表，每次从表中优先取出启发估价函数值最小的状态加以扩展。同时并不丢弃其它的状态，而把它们保留在open表中。

2. 算法过程

Procedure breadth_first_search

Begin

Open:=[start];closed:=[ ]; 　 {*初始化*}

While open ≠ [ ] do

Begin

从open表中删除第一个状态,称之为n;

将n放入closed表中;

If n=目的状态 Then Return(success);

生成n的所有子状态;

从n的子状态中删除已在open或closed表中出现的状态; {*避免循环搜索*}

将n的其余子状态,由不同的算法按不同的顺序加入到open表;

End;

End.

三、启发式策略中估价函数的确定

启发式策略中的“启发”（heuristic）可以体现在三个方面：问题的表达；操作算子的构造；操作算子的选择。这里特别关注操作算子的选择——控制性启发信息。

估价一个结点的价值，必须综合考虑两方面的因素：已经付出的代价(实际)；

将要付出的代价(估计)

f (n) = g(n) + h(n)

g(n)项保持了搜索的宽度优先成分，有利于搜索的完备性，但会影响搜索的效率，h(n)体现了搜索的启发信息，有利于搜索的效率，但影响搜索的完备性。

定义h^*(n)为状态n到目的状态的最优路径的代价。对一具体问题，只要有解，则一定存在h^*(n)。于是，当要求估价函数f(n)中的h(n)都小于等于h^*(n)即

h(n)≤h^*(n) 时，A搜索算法就成为A*搜索算法。

【例】八数码问题的搜索树

初始 S₀

2 8 3 1 2 3

1 6 4 —>?8 4

7 5 7 6 5

S_g(0)

其估价函数可以定义为：

f(n) = d(n) + w(n) (1)

其中d(n)代表状态的深度，每步为单位代价；w(n)表示以“不在位”的将牌数。

估价函数的另一个定义为：

f(n) = d(n) + p(n) (2)

其中p(n) = 将牌“不在位”的距离和。

采用这两种估价函数的A算法都是A^*算法。附录程序采用的估价函数为(2)式，但其d(n)=0。

【实验过程】

估价函数：

////////////////////////////////////

// CaculateH:计算当前H值

// 参数:当前节点

// 返回值:H值

////////////////////////////////////

int CMain::CaculateH(CDisplay *Item)

{

DataType Src[MaxItem][MaxItem];

for(int i=0; i<MaxItem; i++)

for(int j=0; j<MaxItem; j++)

Src[i][j] = Item->GetDispData(i,j); // 数组Src为当前状态

int Hop = 0;

for(i=0; i<MaxItem; i++)

for(int j=0; j<MaxItem; j++)

{

if(Src[i][j] == m_Desc[i][j]) continue; // 数组m_Desc为目标状态

if(Src[i][j] == 0 ) continue;

else

{

int Hhop = Scan(Src[i][j], Position(i,j));

if(Hhop == 65535) return 65535;

Hop += Hhop;

}

return Hop;

}

//////////////////////////////////////////////

// Scan: 扫描计算H值的辅助函数

// 入口:CaculateH()

// 参数:i的位置,与i的值

// 返回值:H(i)的值

//////////////////////////////////////////////

int CMain::Scan(DataType Desc,Position Srcpos)

{

Position Descpos;

for(int i=0;i<MaxItem;i++)

for(int j=0;j<MaxItem;j++)

{

if(this->m_Desc[i][j] == Desc) //m_Desc数组表示目标状态

{

Descpos = Position(i,j);

return (int)fabs(Descpos.x - Srcpos.x)

+(int)fabs(Descpos.y-Srcpos.y);

}

return 65535;

}

附录1：广度优先搜索eightnum.c

附录2：A^*算法 8数码A星VC.rar

相关推荐

《人工智能导论》实验指导书(新)

第二篇：人工智能导论实验指导书

专栏推荐