实 验 报 告
课程名称 人工智能_____________ 实验项目 野人过河问题_______________ 实验仪器 电脑 、visual C++_________
系 别 计算机学院____________ 专 业 __计算机科学与技术_____ 班级/学号 学生姓名 _ __
实验日期 2010年 月 日_______ 成 绩 _______________________ 指导教师
一、 实验目的
理解并熟悉掌握深度优先搜索和广度优先搜索地方法。
二、 实验内容
题目：设有3个传教士和3个野人来到河边，打算乘一只船从右岸到左岸去。 该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人 就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?
三、代码和结果
#include
#define maxloop 100 /* 最大层数，对于不同的扩展方法自动调整取值 */ #define pristnum 3 /*初始化时设定有3个野人3个传教士，实际可以改动*/ #define slavenum 3
struct SPQ{ int sr,pr; /* 船运行一个来回后河右岸的野人、传教士的人数 int sl,pl; /* 船运行一个来回后河左岸的野人、传教士的人数 */ int ssr,spr; /* 回来（由左向右时）船上的人数 */ int sst,spt; /* 去时（由右向左时）船上的人数 */
int loop; /* 本结点所在的层数 */
struct SPQ *upnode ,*nextnode;/* 本结点的父结点和同层的下一个结点的地址 */ }spq;
int loopnum;/* 记录总的扩展次数 */
int openednum;/* 记录已扩展节点个数 */ int unopenednum;/* 记录待扩展节点个数 */ int resultnum;
struct SPQ *opened; struct SPQ *oend;
struct SPQ *unopened; struct SPQ *uend; struct SPQ *result; void initiate();
void releasemem(); void showresult();
void addtoopened(struct SPQ *ntx); int search(); void goon();
int stretch(struct SPQ* ntx); void recorder();
int main() {
*/
int flag; /* 标记扩展是否成功 */ for( ; ; ) {
initiate();
flag = search (); if(flag == 1) {
recorder(); releasemem(); showresult(); goon(); }
else {
printf(\无法找到符合条件的解\ releasemem(); goon(); } }
system(\ return 0; }
void initiate() {
int x;
char choice;
uend = unopened = (struct SPQ*)malloc(sizeof(spq)); if(uend==NULL) {
printf(\内存不够！\\n\ exit(0); }
unopenednum=1; openednum=0;
unopened -> upnode = unopened; /* 保存父结点的地址以成链表 */ unopened -> nextnode = unopened; unopened -> sr = slavenum; unopened -> pr = pristnum; unopened -> sl = 0; unopened -> pl = 0; unopened -> sst = 0; unopened -> spt = 0;
unopened -> ssr = 0; unopened -> spr = 0; unopened -> loop = 0;
printf(\题目：设有n个传教士和m个野人来到河边，打算乘一只船从右岸到左岸去。\\n\
printf(\该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人\\n\ printf(\就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?\\n\ printf(\默认的n、m值皆为3\\n\ for(;;) {
printf(\是否修改？(Y/N)\ scanf(\ choice=toupper(choice); if(choice=='Y') {
printf(\请输入传教士人数\ for(;;) {
scanf(\ if(x>0) {
unopened -> pr = x; break; }
else printf(\输入值应大于0！\\n请重新输入\ }
printf(\请输入野人人数\ for(;;) {
scanf(\ if(x>0) {
unopened -> sr = x; break; }
else printf(\输入值应大于0！\\n请重新输入\ }
break; }
if(choice=='N')break; } }
int search()