闲来无事，忽然记起有这个博客，便把刚做的两个程序放上来。在Visual Studio 2008下用控制台写的，没认真组织设计数据结构，只是为了给人工智能课那个让我胃痛的老师交差。 野人与修道士问题（忘了是传教士还是修道士，反正就那一路货色，差不多）。3个野人，3个传教士，一条船（只能容纳两个人，当然一个人也不会把船怎么样），两岸和船上修道士人数不能少于野人，否则会被野人吃掉（老实说我也想尝尝），野人绝对服从修道士的安排，设计一个过河方案。解法为状态空间搜索策略。 // AITask.cpp : 定义控制台应用程序的入口点。//////树形空间遍历求解修道士与野人问题#include "stdafx.h"void FindPath(TNode *Node);int TestWay(int i,TNode *Node);int PrePath[100][3];int NodeNum=0;int MoveWay[5][2];int _tmain(int argc, _TCHAR* argv[]){ TNode *Node; Node=(Tree)malloc(sizeof(FIVTree)); Node->Back=NULL; Node->LeafFlag=1; Node->ThisSide[0]=3; Node->ThisSide[1]=3; Node->OtherSide[0]=0; Node->OtherSide[1]=0; for (int i=0;i<3;i++)  Node->Child[i]=NULL; Node->BoatSide=THIS_SIDE; PrePath[NodeNum][0]=3; PrePath[NodeNum][1]=3; PrePath[NodeNum][2]=THIS_SIDE; MoveWay[0][0]=1; MoveWay[0][1]=1; MoveWay[1][0]=1; MoveWay[1][1]=0; MoveWay[2][0]=0; MoveWay[2][1]=1; MoveWay[3][0]=2; MoveWay[3][1]=0; MoveWay[4][0]=0; MoveWay[4][1]=2;    /////根节点初始化及全局数据定义 FindPath(Node); return 0;} void FindPath(TNode *Node){ int i; TNode *Child[5]; TNode *TmpNode; int Test; int TTest[4]; for (i=0;i<5;i++) {  TTest[0]=Node->ThisSide[0];  TTest[1]=Node->ThisSide[1];  TTest[2]=Node->OtherSide[0];  TTest[3]=Node->OtherSide[1];  Test=TestWay(i,Node);  switch(Test)  {  /////可延伸节点  case 1:   NodeNum++;   Child[i]=(Tree)malloc(sizeof(FIVTree));   Child[i]->Back=Node;   if (Node->BoatSide==THIS_SIDE)   {    Node->LeafFlag=0;    Child[i]->LeafFlag=1;    Child[i]->ThisSide[0]=TTest[0]-MoveWay[i][0];    Child[i]->ThisSide[1]=TTest[1]-MoveWay[i][1];    Child[i]->OtherSide[0]=TTest[2]+MoveWay[i][0];    Child[i]->OtherSide[1]=TTest[3]+MoveWay[i][1];    Child[i]->BoatSide=OTHER_SIDE;   }   if (Node->BoatSide==OTHER_SIDE)   {    Node->LeafFlag=0;    Child[i]->LeafFlag=1;    Child[i]->ThisSide[0]=TTest[0]+MoveWay[i][0];    Child[i]->ThisSide[1]=TTest[1]+MoveWay[i][1];    Child[i]->OtherSide[0]=TTest[2]-MoveWay[i][0];    Child[i]->OtherSide[1]=TTest[3]-MoveWay[i][1];    Child[i]->BoatSide=THIS_SIDE;   }   Node->Child[i]=Child[i];                ///递归调用   PrePath[NodeNum][2]=203-Node->BoatSide;   PrePath[NodeNum][0]=Child[i]->ThisSide[0];   PrePath[NodeNum][1]=Child[i]->ThisSide[1];  ///路径记录   for (int j=0;j<3;j++)    Child[i]->Child[j]=NULL;   FindPath(Child[i]);   break;  ////////得出结果  case 2:   Child[i]=(Tree)malloc(sizeof(FIVTree));   Child[i]->Back=Node;   Node->LeafFlag=0;   Child[i]->LeafFlag=1;   Child[i]->ThisSide[0]=TTest[0]-MoveWay[i][0];   Child[i]->ThisSide[1]=TTest[1]-MoveWay[i][1];   Child[i]->OtherSide[0]=TTest[2]+MoveWay[i][0];   Child[i]->OtherSide[1]=TTest[3]+MoveWay[i][1];   Child[i]->BoatSide=OTHER_SIDE;   Node->Child[i]=Child[i];   TmpNode=Child[i];   while (TmpNode!=NULL)   {    cout<<TmpNode->ThisSide[0]<<' '<<TmpNode->ThisSide[1]<<"  "     <<TmpNode->OtherSide[0]<<' '<<TmpNode->OtherSide[1]<<     "  "<<TmpNode->BoatSide<<endl;    TmpNode=TmpNode->Back;   }   return;   break;  } }} /////检测节点可否延伸int TestWay(int i,TNode *Node){ int TTest[4]; TTest[0]=Node->ThisSide[0]; TTest[1]=Node->ThisSide[1]; TTest[2]=Node->OtherSide[0]; TTest[3]=Node->OtherSide[1]; if (Node->BoatSide==THIS_SIDE) {  TTest[0]-=MoveWay[i][0];  TTest[1]-=MoveWay[i][1];  TTest[2]+=MoveWay[i][0];  TTest[3]+=MoveWay[i][1];  if (TTest[0]<0||TTest[1]<0)   return 0;  if (TTest[0]<TTest[1]&&TTest[0]>0)   return 0;  if (TTest[2]<TTest[3]&&TTest[2]>0)   return 0;     if (TTest[0]==0&&TTest[1]==0)   return 2;  for (int j=0;j<=NodeNum;j++)   if (TTest[0]==PrePath[j][0]&&TTest[1]==PrePath[j][1]&&    PrePath[j][2]==OTHER_SIDE)    return 0; } if (Node->BoatSide==OTHER_SIDE) {  TTest[0]+=MoveWay[i][0];  TTest[1]+=MoveWay[i][1];  TTest[2]-=MoveWay[i][0];  TTest[3]-=MoveWay[i][1];  if (TTest[2]<0||TTest[3]<0)   return 0;  if (TTest[0]<TTest[1]&&TTest[0]>0)   return 0;  if (TTest[2]<TTest[3]&&TTest[2]>0)   return 0;  for (int j=0;j<=NodeNum;j++)   if (TTest[0]==PrePath[j][0]&&TTest[1]==PrePath[j][1]&&    PrePath[j][2]==THIS_SIDE)    return 0; } return 1;} /////主程序如上，下为包含文件 // stdafx.h : 标准系统包含文件的包含文件，// 或是经常使用但不常更改的// 特定于项目的包含文件//#pragma once#define THIS_SIDE 101#define OTHER_SIDE 102#include "targetver.h"#include <Windows.h>#include <stdio.h>#include <tchar.h>#include <iostream>using namespace std;typedef struct FIVTree   ////五杈树{ int ThisSide[2]; int OtherSide[2]; bool LeafFlag; int BoatSide; FIVTree *Back; FIVTree *Child[3];}TNode,*Tree;// TODO: 在此处引用程序需要的其他头文件

评论