人工智能实验 传教士野人

人工智能实验 传教士野人 人工智能实验 题目:求解传教士和野人问题 姓名: 班级: 学号: 学院:计算机科学与信息 专业:计算机科学与技术 指导教师: 日期:2011年12月6日 一、实验目的, 复习经典谓词演算中的归结原理，掌握人工智能程序设计语言Prolog，理解通过搜索求解问题实现人工智能的思想。 二、实验原理, 谓词演算中的消解法。 三、实验内容: 设有3个传教士和3个野人同在河的左岸，他们都要到对岸去;河里只有一条船，他们都会划船，但每次渡船至多只能乘两人;如果在任何一边河岸上，野人的数量超过传教士，野人就要吃掉传教士，问怎样才能用船将3个传教士和3个野人从左岸都渡到右岸，又不会发生传教士被吃的事件呢,通过Prolog程序，给出乘船过河的动作序列。 四、实验描述及要求: (1) 设计该问题的状态。例如:((左岸牧师数，左岸野人数),(右岸牧师数，右岸野人 数),船的位置)。 (2) 定义目标状态。这里是:((0,0),(3,3),1) (3) 描述可能的动作。船上所能够载人的状态就是可能的操作。用谓词move/2表示。 (4) 判断合法状态 (5) 深度优先搜索 五、实验结果: 六:实验代码 #include "stdafx.h" #include #include #include using namespace std; #define FAIL ((struct BOAT *)-1) #define M 3 #define C 3 #define K 2 struct Lift { int m; int c; int b; struct Lift *pNext; }; struct BOAT { int m; int c; struct BOAT *pNext; }; struct BOAT *g_pBoatSet = NULL; int Equal(struct Lift *pLift1, struct Lift *pLift2) { if (pLift1->m == pLift2->m && pLift1->c == pLift2->c && pLift1->b == pLift2->b) return 1; else return 0; } struct Lift *NewLift(int m, int c, int b) { struct Lift *pLift = NULL; pLift = (Lift*)malloc(sizeof(struct Lift)); if (pLift == NULL) return NULL; pLift->m = m; pLift->c = c; pLift->b = b; pLift->pNext = NULL; return pLift; } struct BOAT *NewBoat(int m, int c) { struct BOAT *pBoat = NULL; pBoat = (BOAT*)malloc(sizeof(struct BOAT)); if (pBoat == NULL) return NULL; pBoat->m = m; pBoat->c = c; pBoat->pNext = NULL; return pBoat; } struct BOAT *InitBoats(void) { struct BOAT *pBoats = NULL, *pBoat = NULL; int i, j; for (i = 0; i <= 2; i++) { for (j = 0; j <= 2; j++) { if(i+j<=2) { pBoat = NewBoat(i, j); if (pBoat == NULL) return NULL; pBoat->pNext = pBoats; pBoats = pBoat; } } } return pBoats; } int IsGoal(struct Lift *pLift) { if (pLift->m == 0 && pLift->c == 0 && pLift->b == 0) return 1; else return 0; } int Safe(struct Lift *pLift) { if (pLift->m < 0 || pLift->c < 0 || pLift->m > M || pLift->c > C || pLift->c > M) return 0; if (pLift->m == M || pLift->m == 0) return 1; return (pLift->m == pLift->c); } void PrintLift(struct Lift *pLift) { int rm=3-(pLift->m), rc=3-(pLift->c); printf("(%d, %d, %d) (%d, %d)\n", pLift->m, pLift->c, pLift->b,rm, rc); } void PrintBoatList(struct BOAT *pList) { if (pList == FAIL) { printf("no solution!\n"); return; } if (pList == NULL) { printf("( )\n"); return; } else { printf("(0, 0, 0)\n"); } } int Length(struct Lift *pList) { if (pList == NULL) return 0; return Length(pList->pNext) + 1; } struct Lift *ConsLift(struct Lift *pLift, struct Lift *pList) { pLift->pNext = pList; return pLift; } struct BOAT *ConsBoat(struct BOAT *pBoat, struct BOAT *pList) { pBoat->pNext = pList; return pBoat; } struct Lift *Gen(struct BOAT *pBoat, struct Lift *pData) { if (pData->b == 1) { return NewLift(pData->m - pBoat->m, pData->c - pBoat->c, 0); } else { return NewLift(pData->m + pBoat->m, pData->c + pBoat->c, 1); } } struct BOAT *CopyBoat(struct BOAT *pBoat) { return NewBoat(pBoat->m, pBoat->c); } struct Lift *In(struct Lift *pLift, struct Lift *pList) { if (pList == NULL) return NULL; if (Equal(pLift, pList)) return pList; return In(pLift, pList->pNext); } void FreeLiftList(struct Lift *pLiftList) { struct Lift *pLift = NULL; while (pLiftList) { pLift = pLiftList; pLiftList = pLiftList->pNext; free(pLift); } } void FreeBoatList(struct BOAT *pBoatList) { struct BOAT *pBoat = NULL; if (pBoatList == FAIL) return; while (pBoatList) { pBoat = pBoatList; pBoatList = pBoatList->pNext; free(pBoat); } } struct BOAT *Backtrack1(struct Lift *pDataList, int bound) { struct Lift *pData = NULL, *pRData = NULL, *pRDataList = NULL; struct BOAT *pBoat = NULL, *pBoats = NULL, *pPath = NULL; pData = pDataList; if (In(pData, pDataList->pNext)) { return FAIL; } if (IsGoal(pData)) { FreeLiftList(pDataList); return NULL; } if (!Safe(pData)) { return FAIL; } if (Length(pDataList) > bound) { return FAIL; } pBoats = g_pBoatSet; PrintLift(pDataList); while (pBoats) { pBoat = pBoats; pBoats = pBoats->pNext; pRData = Gen(pBoat, pData); if (pRData == NULL) return FAIL; if (!Safe(pRData)) { free(pRData); continue; } pRDataList = ConsLift(pRData, pDataList); pPath = Backtrack1(pRDataList, bound); if (pPath == FAIL) { free(pRData); continue; } pBoat = CopyBoat(pBoat); if (pBoat == NULL) return FAIL; return ConsBoat(pBoat, pPath); } return FAIL; } void main(void) { struct Lift *pData = NULL; struct BOAT *pPath = NULL; g_pBoatSet = InitBoats(); cout<<"3个?传ä?教??士º?和?ª3个?野??ã人??过y河??问?º题?a的Ì?答äe案ã?为a:êo\n 左Á??岸ã? 右???岸ã?"<