10405321试验一.docx

10405321试验一.docx

《10405321试验一.docx》由会员分享，可在线阅读，更多相关《10405321试验一.docx（13页珍藏版）》请在冰点文库上搜索。

10405321试验一

昆明理工大学信息工程与自动化学院学生实验报告

（2012—2013学年第1学期）

课程名称：

人工智能开课实验室：

信自楼机房4452012年11月5日

年级、专业、班

10级计科103班

学号

201010405321

姓名

何贵锟

成绩

实验项目名称

野人与传教士过河问题

指导教师

王剑

教师评语

该同学是否了解实验原理：

A.了解□B.基本了解□C.不了解□

该同学的实验能力：

A.强□B.中等□C.差□

该同学的实验是否达到要求：

A.达到□B.基本达到□C.未达到□

实验报告是否规范：

A.规范□B.基本规范□C.不规范□

实验过程是否详细记录：

A.详细□B.一般□C.没有□

教师签名：

年月日

一、实验目的

运用人工智能中学过的相关算法知识解决传教士和野人渡河问题找出能够解决问题的所有可行方案。

二、实验内容

1问题描述

有m个传教士和n个野人过河，只有一条能装下k个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教就会有危险，要求找出一种安全的渡河方法。

2工具

VisualC++6.0编辑环境；Win7电脑一台

三、实验步骤

1算法分析

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

初始状态：

左岸，m个传教士，n个野人；

右岸，0个传教士，0个野人；

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

目标状态：

左岸，0个传教士，0个野人；

右岸，m个传教士，n个野人；

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

回溯算法中采用的一些规则如下：

1）．开始状态传教士的人数一定要大于等于野人的人数。

2）．进行深度优先算法首先取当前节点，判断当前节点是否已经出现在初始节点到当前节点的路径上，如果出现过则回溯。

3）．接着判断当前节点是否是目标节点，如果是则释放掉路径上所有节点，以“空”作为解路径返回，表示从目标节点到目标节点不需要任何规则操作。

算法成功结束。

4）．判断当前节点是否是非法节点，即满足在河的任何一岸和船上，传教士人数不少于野人人数，或者只有野人而没有传教士，如果是非法节点则准备回溯。

5）．判断当前节点的搜索深度是否到达给定的深度，如果是则准备回溯。

2程序流程及具体设计

#include

#include

#defineFAIL（（structRULE*）-1）

staticintM;

staticintC;

staticintK;

voidInput_MCK（）

{

inta,b,c;

printf（"请输入传教士的数目:

\n"）;

scanf（"%d",&a）;

printf（"请输入野人的数目:

\n"）;

scanf（"%d",&b）;

printf（"请输入船上最大载客量:

\n"）;

scanf（"%d",&c）;

M=a,C=b,K=c;

}

structNODE

{

intm;

intc;

intb;

structNODE*pNext;

};

structRULE

{

intm;

intc;

structRULE*pNext;

};

structRULE*g_pRuleSet=NULL;

intEqual（structNODE*pNode1,structNODE*pNode2）

{

if（pNode1->m==pNode2->m&&

pNode1->c==pNode2->c&&

pNode1->b==pNode2->b）

return1;

else

return0;

}

structNODE*NewNode（intm,intc,intb）

{

structNODE*pNode=NULL;

pNode=（NODE*）malloc（sizeof（structNODE））;

if（pNode==NULL）returnNULL;

pNode->m=m;

pNode->c=c;

pNode->b=b;

pNode->pNext=NULL;

returnpNode;

}

structRULE*NewRule（intm,intc）

{

structRULE*pRule=NULL;

pRule=（RULE*）malloc（sizeof（structRULE））;

if（pRule==NULL）returnNULL;

pRule->m=m;

pRule->c=c;

pRule->pNext=NULL;

returnpRule;

}

structRULE*InitRules（void）

{

structRULE*pRules=NULL,*pRule=NULL;

inti,j;

for（i=0;i<=K;i++）

{

for（j=0;j<=K;j++）

{

if（i+j==0||

i+j>K||

（i!

=0&&i

pRule=NewRule（i,j）;

if（pRule==NULL）returnNULL;

pRule->pNext=pRules;

pRules=pRule;

}

}

returnpRules;

}

intIsGoal（structNODE*pNode）

{

if（pNode->m==0&&

pNode->c==0&&

pNode->b==0）

return1;

else

return0;

}

intSafe（structNODE*pNode）

{

if（pNode->m<0||

pNode->c<0||

pNode->m>M||

pNode->c>C||

pNode->c>M）return0;

if（pNode->m==M||

pNode->m==0）return1;

return（pNode->m==pNode->c）;

}

voidPrintNode（structNODE*pNode）

{

printf（"（%d,%d,%d）\n",pNode->m,pNode->c,pNode->b）;

}

voidPrintRule（structRULE*pRule）

{

printf（"（%d%d）\n",pRule->m,pRule->c）;

}

voidPrintNodeList（structNODE*pList）

{

while（pList）

{

printf（"（%d,%d,%d）\n",pList->m,pList->c,pList->b）;

pList=pList->pNext;

}

}

voidPrintRuleList（structRULE*pList）

{

if（pList==FAIL）

{

printf（"nosolution!

\n"）;

return;

}

if（pList==NULL）

{

printf（"（）\n"）;

return;

}

else

{

printf（"（0,0,0）\n"）;

}

while（pList）

{

pList=pList->pNext;

}

}

intLength（structNODE*pList）

{

if（pList==NULL）return0;

returnLength（pList->pNext）+1;

}

structNODE*ConsNode（structNODE*pNode,structNODE*pList）

{

pNode->pNext=pList;

returnpNode;

}

structRULE*ConsRule（structRULE*pRule,structRULE*pList）

{

pRule->pNext=pList;

returnpRule;

}

structNODE*Gen（structRULE*pRule,structNODE*pData）

{

if（pData->b==1）

{

returnNewNode（pData->m-pRule->m,pData->c-pRule->c,0）;

}

else

{

returnNewNode（pData->m+pRule->m,pData->c+pRule->c,1）;

}

}

structRULE*CopyRule（structRULE*pRule）

{

returnNewRule（pRule->m,pRule->c）;

}

structNODE*In（structNODE*pNode,structNODE*pList）

{

if（pList==NULL）returnNULL;

if（Equal（pNode,pList））returnpList;

returnIn（pNode,pList->pNext）;

}

voidFreeNodeList（structNODE*pNodeList）

{

structNODE*pNode=NULL;

while（pNodeList）

{

pNode=pNodeList;

pNodeList=pNodeList->pNext;

free（pNode）;

}

}

voidFreeRuleList（structRULE*pRuleList）

{

structRULE*pRule=NULL;

if（pRuleList==FAIL）return;

while（pRuleList）

{

pRule=pRuleList;

pRuleList=pRuleList->pNext;

free（pRule）;

}

}

structRULE*Backtrack1（structNODE*pDataList,intbound）

{

structNODE*pData=NULL,*pRData=NULL,*pRDataList=NULL;

structRULE*pRule=NULL,*pRules=NULL,*pPath=NULL;

pData=pDataList;

if（In（pData,pDataList->pNext））

{

returnFAIL;

}

if（IsGoal（pData））

{

FreeNodeList（pDataList）;

returnNULL;

}

if（!

Safe（pData））

{

returnFAIL;

}

if（Length（pDataList）>bound）

{

returnFAIL;

}

pRules=g_pRuleSet;

PrintNode（pDataList）;

while（pRules）

{

pRule=pRules;

pRules=pRules->pNext;

pRData=Gen（pRule,pData）;

if（pRData==NULL）returnFAIL;

if（!

Safe（pRData））

{

free（pRData）;

continue;

}

pRDataList=ConsNode（pRData,pDataList）;

pPath=Backtrack1（pRDataList,bound）;

if（pPath==FAIL）

{

free（pRData）;

continue;

}

pRule=CopyRule（pRule）;

if（pRule==NULL）returnFAIL;

returnConsRule（pRule,pPath）;

}

returnFAIL;

}

voidmain（void）

{

structNODE*pData=NULL;

structRULE*pPath=NULL;

Input_MCK（）;

g_pRuleSet=InitRules（）;

pData=NewNode（M,C,1）;

pPath=Backtrack1（pData,20）;

PrintRuleList（pPath）;

if（pPath==FAIL）

{

free（pData）;

}

FreeRuleList（pPath）;

FreeRuleList（g_pRuleSet）;

}

四、程序运行结果

五、实验总结：

通过本次实验，我用c语言编程实现了野人与传教士过河问题，运用人工智能中学过的相关算法知识解决了传教士和野人渡河问题找出能够解决问题的所有可行方案。