野人与传教士问题A算法

野人与传教士问题（A*算法）SY0903620 赵磊一、实验题目请用A*算法实现传教士和野人问题问题：设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？算法设计要求给出：状态表示，规则库，启发函数等二、实验目的通过具体问题的编程求解，利用A*算法解决此经典问题，了解人工智能的启发式搜索算法的基本过程与原理。 三、设计思想1、编程工具采用C+语言在Visual Studio 6.0环境下编写；2、整体思想(1) 把初始结点So放入OPEN 表中，计算f(So)。(2) 如果OPEN为空，则搜索失败，退出。(3) 把OPEN中的第一个节点(记为节点n)从表中移出放入CLOSED表。(4) 考察节点n是否为目标节点。若是，则求得问题的解，退出。(5) 若节点n不可扩展，则转第(2)步。(6) 扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每个子节点配置指向父节点的指针，把这些子节点都送到OPEN表中，然后对OPEN表中的全部节点按估价值从小到大的顺序排列。3、具体说明用A*算法求解传教士与野人问题。M=C=5, K=3。节点估价值设为f(n)=h(n)+g(n)，g(n)设为节点搜索深度，而h(n) = m(n) + c(n) - 2b(n),其中m：河左岸的传教士人数；c：河左岸的野人人数；b：船是否在左岸，1：表示在左岸，0：表示不在左岸。采用结构体定义形式，定义状态节点*NewNode(int m, int c, int b)，其中包含m左岸传教士人数、c左岸野人人数、b船状态（左或右）。开始状态为（3，3，1），目标状态为（0，0，0）。若需要条件满足，即任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉，要对状态结点的安全性进行判断，判断一个状态是否为安全的，即是否满足在河的任何一岸，传教士人数不少于野人人数，或者只有野人而没有传教士。对于超出参数范围的状态，也认为是不安全的。即判断：if (pNode-m c m M |pNode-c M) return 0; if (pNode-m = M |pNode-m = 0) return 1;要扩展节点n生成其全部后继节点. 对于n的每一个后继节点m配置指向父节点的指针时：a) 计算f(m)b) 如果m既不在OPEN表中, 也不在CLOSED表中, 则用估价函数f把它添入OPEN表. 从m加一指向父辈节点n的指针。c) 如果m已在OPEN表或CLOSED表上, 则比较刚刚对m计算过的值f和前面计算过的该节点在表中的f值. 如果新的f值较小, 则I. 以此新值取代旧值II. 从m指向n, 而不是指向它的父辈节点 III. 如果节点m在CLOSED表中, 则把它移回OPEN表四、具体函数功能1)int Equal(struct NODE *pNode1, struct NODE *pNode2)功能：判断两个节点所表示的状态是否相等 入口参数： pNode1：指向节点1的指针 pNode2：指向节点2的指针 返回值：当两个节点所表示的状态相等时，返回1，否则返回0 2)struct NODE *NewNode(int m, int c, int b)功能：动态产生一个节点，其状态值由参数m，c，b给定。入口参数： m：河左岸的传教士人数 c：河左岸的野人人数 b：船是否在左岸，1：表示在左岸，0：表示不在左岸 返回值：指向新产生的节点的指针，或者空间不够时，返回NULL3)void FreeList(struct NODE *pList)功能：释放动态产生的链表 入口参数： pList：指向OPEN表或者CLOSED表的指针 返回值：无 4)struct NODE *In(struct NODE *pNode, struct NODE *pList)功能：判断一个节点是否在一个链表中 入口参数： pNode：指向给定节点的指针 pList：指向给点链表的指针 返回值：当pNode在pList中时，返回以pNode为首的链表的后一部分；否则返回NULL 5)struct NODE *Del(struct NODE *pNode, struct NODE *pList)功能：从链表pList中删除节点pNode 入口参数： pNode：指向给定节点的指针 pList：指向给定的链表 返回值：删除给定节点后的链表 6)struct NODE *AddToOpen(struct NODE *pNode, struct NODE *pOpen)功能：将一个节点按照f值（从小到大）插入到OPEN表中入口参数： pNode: 指向给定节点的指针 pOpen：指向OPEN表的指针 返回值：指向插入给定节点后OPEN表的指针 注意：同一个节点（具有相同指针的一个节点），只能向表中添加一次，否则可能会造成循环链表 7)struct NODE *AddToClosed(struct NODE *pNode, struct NODE *pClosed)功能：将一个节点插入到CLOSED表中 入口参数： pNode: 指向给定节点的指针 pClosed：指向CLOSED表的指针 返回值：指向插入给定节点后CLOSED表的指针 注意：同一个节点（具有相同指针的一个节点），只能向表中添加一次，否则可能会造成循环链表 8)void PrintList(struct NODE *pList)功能：在屏幕上打印一个链表，用于调试程序 入口参数： pList：指向链表的指针 返回值：无 9)void PrintNode(struct NODE *pNode)功能：在屏幕上打印一个节点，用于调试程序 入口参数： pNode：指向节点的指针 返回值：无 10)void PrintPath(struct NODE *pGoal) 功能：在屏幕上打印解路径。在搜索过程中，每个节点指向其父节点，从目标节点开始，逆向打印各节点，既得到解路径入口参数： pGoal：指向求解得到的目标节点 返回值：无 11)int IsGrandFather(struct NODE *pNode, struct NODE *pFather)功能：判断一个节点是否与自己的祖父节点所表示的状态一样 入口参数： pNode：指向给定节点的指针 pFather：指向给定节点的父节点的指针 返回值：当给定节点所表示的状态与自己的祖父一样时，返回1，否则返回0 12)int IsGoal(struct NODE *pNode)功能：判断给定节点是否为目标节点入口参数： pNode：指向给定节点的指针 返回值：当给定节点是目标节点时，返回1，否则返回0 13)int Safe(struct NODE *pNode)功能：判断一个状态是否为安全的，即是否满足在河的任何一岸，传教士人数不少于野人人数，或者只有野人而没有传教士。对于超出参数范围的状态，也认为是不安全的入口参数：pNode：指向给定节点的指针 返回值：当给定节点安全时，返回1，否则返回0 14)int H_Function(struct NODE *pNode)功能：计算给定节点的h值，h = m + c - 2b入口参数： pNode：指向给定节点的指针返回值：h值 15)struct NODE *A_Star(struct NODE *s)功能：A*算法主函数入口参数： s：指向初始节点的指针 返回值：指向求解得到的目标节点的指针，或者返回NULL表示空间不够用或者找不到问题的解 五、程序源代码#defineM3/传教士总人数#defineC3/野人总人数#defineK2/船一次可以乘坐的最多人数struct NODEint m;/在左岸的传教士人数int c;/在左岸的野人人数int b;/b=1表示船在左岸,b=0表示船在右岸double g;/该节点的g值double f;/该节点的f值struct NODE *pFather;/指向该节点的父节点struct NODE *pNext;/在OPEN表或者CLOSED表中，指向下一个元素;struct NODE *g_pOpen = NULL;/全程变量，OPEN表struct NODE *g_pClosed = NULL;/全程变量，CLOSED表int Equal(struct NODE *pNode1, struct NODE *pNode2)if (pNode1-m = pNode2-m &pNode1-c = pNode2-c &pNode1-b = pNode2-b) return 1;else return 0;struct NODE *NewNode(int m, int c, int b)struct NODE *pNode = NULL;pNode = malloc(sizeof(struct NODE);if (pNode = NULL) return NULL;pNode-m = m;pNode-c = c;pNode-b = b;pNode-g = 0;pNode-f = 0;pNode-pFather = NULL;pNode-pNext = NULL;return pNode;void FreeList(struct NODE *pList)struct NODE *pNode = NULL;while (pList)pNode = pList;pList = pList-pNext;free(pNode);struct NODE *In(struct NODE *pNode, struct NODE *pList)if (pList = NULL) return NULL;if (Equal(pNode, pList) return pList;return In(pNode, pList-pNext);struct NODE *Del(struct NODE *pNode, struct NODE *pList)if (pList = NULL) return pList;if (Equal(pNode, pList) return pList-pNext;pList-pNext = Del(pNode, pList-pNext);return pList;struct NODE *AddToOpen(struct NODE *pNode, struct NODE *pOpen)if (pOpen = NULL)/OPEN表为空pNode - pNext = NULL;return pNode;if (pNode-f f)/给定节点的f值小于OPEN表第一个节点的f值pNode-pNext = pOpen;/插入到OPEN的最前面return pNode;pOpen-pNext = AddToOpen(pNode, pOpen-pNext);/递归return pOpen;struct NODE *AddToClosed(struct NODE *pNode, struct NODE *pClosed)pNode-pNext = pClosed;return pNode;void PrintList(struct NODE *pList)while (pList)/依次打印链表printf(%d %d %d) %f %f)n, pList-m, pList-c, pList-b, pList-g, pList-f);pList = pList-pNext;void PrintNode(struct NODE *pNode)printf(%d %d %d) %f %f)n, pNode-m, pNode-c, pNode-b, pNode-g, pNode-f);void PrintPath(struct NODE *pGoal) if (pGoal = NULL) return;PrintPath(pGoal-pFather);/递归printf(%d %d %d)n, pGoal-m, pGoal-c, pGoal-b);int IsGrandFather(struct NODE *pNode, struct NODE *pFather)if (pFather = NULL) return 0;if (pFather-pFather = NULL) return 0;return Equal(pNode, pFather-pFather);int IsGoal(struct NODE *pNode)if (pNode-m = 0 &pNode-c = 0 &pNode-b = 0) return 1;else return 0;int Safe(struct NODE *pNode)if (pNode-m c m M |pNode-c M) return 0;if (pNode-m = M |pNode-m = 0) return 1;return (pNode-m = pNode-c);int H_Function(struct NODE *pNode)return pNode-m + pNode-c - 2*pNode-b;struct NODE *A_Star(struct NODE *s)struct NODE *n = NULL, *m = NULL, *pNode = NULL;int i, j;g_pOpen = s;/初始化OPEN表和CLOSED表g_pClosed = NULL;while (g_pOpen)/OPEN表不空n = g_pOpen;/取出OPEN表的第一个元素nif (IsGoal(n) return n; /如果n为目标节点，则成功结束g_pOpen = g_pOpen-pNext; /否则，从OPEN表中删除ng_pClosed = AddToClosed(n, g_pClosed);/将n加入到CLOSED中/ 以下两重循环，i表示上船的传教士人数，j表示上船的野人人数for (i = 0; i = K; i+)for (j = 0; j K |(i != 0 & i b = 1)/当船在左岸时m = NewNode(n-m-i, n-c-j, 0);/产生下一个状态melse/当船在右岸时m = NewNode(n-m+i, n-c+j, 1);/产生下一个状态mif (m = NULL) return NULL;/如果空间不够用，则失败结束if (IsGrandFather(m, n) | !Safe(m)free(m);continue;m-pFather = n;/标记其父节点为nm-g = n-g + 1;/其g值为其父节点的g值加1m-f = m-g + H_Function(m