《人工智能实验指导书AI》由会员分享，可在线阅读，更多相关《人工智能实验指导书AI（108页珍藏版）》请在金锄头文库上搜索。
1、实验一 八数码问题一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用启发式搜索算法求解八数码难题，理解求解流程和搜索顺序。二、实验原理：启发式搜索就是利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。一般来说，启发信息强，可以降低搜索的工作量，但可能导致找不到最优解；而启发信息弱，一般会导致搜索的工作量加大，极端情况下演变为盲目搜索，但有可能找到最优解。我们希望，通过引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。算法的理论意义在于给出了求解最佳解的条件h(n)h*(n)。对给定的问题，函数h*(n)（n是变量）在问题有解的条件下客观上是存
2、在的，但在问题求解过程中不可能明确知道，因此对实际问题，能不能使所定义的启发函数满足下界范围条件？如果困难很大，那么 算法的实际应用就会受到限制。下面将通过8数码问题来说明这个问题。八数码游戏（八数码问题）描述为：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。12384765 28316475初始状态 目标状态对八数码
3、问题，如果启发函数根据任意结点与目标之间的差异来定义，例如 取h(n)=W(n)，那么很容易看出，尽管我们对具体的h*(n)是多少很难确切知道，但根据“不在位”将牌个数这个估计，就能得出至少要移动W(n)步才能达到目标，显然有W(n) =h*(n)(假定为单位耗散的情况)。如果启发函数进一步考虑任意节点与目标之间的距离信息，例如取h(n)=P(n)，P(n)定义为每一个将牌与其目标位置之间距离（不考虑夹在其间的将牌）的总和，那么同样能断定至少也要移动P(n)步才能达到目标，因此有P(n) =h*(n)。下图给出h(n)=P(n)是的搜索图，节点旁边还标出W(n)和P(n)启发函数值。W=4P=
4、5F=528316475W=5P=6F=7W=5P=6F=7W=3P=4F=5283147652831647528316475283147652318476528314765W=4P=5F=7W=3P=3F=5W=3P=5F=72318476523184765W=4P=4F=7W=2P=2F=512384765W=1P=1F=51238476512378465W=2P=2F=7W=0P=0F=5h(n)=P(n)的搜索树三、实验条件：1. JAVA/VC6.0。2.八数码问题流程图。四、实验内容：1.用启发式搜索算法求解八数码问题。2.分析估价函数对搜索算法的影响。3.分析启发式搜索算法的特点
5、。五、实验步骤：1. 了解启发式搜索算法的算法思想。2. 用启发式搜索算法分析八数码问题，构造启发函数，建立解题思路。3. 根据解题思路编写程序并调试。4. 演示程序。六、实验报告要求：1. 启发式搜索算法流程图和算法框图。2. 试分析估价函数的值对搜索算法速度的影响。3. 根据启发式搜索算法分析启发式搜索的特点。七、参考程序：要想得到最优的就需要使用广度优先搜索，八数码问题的所有排列有！种，也就是种排法，数据量是非常大的，我使用的广度搜索，需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，我们把数据进行适当的压缩。使用形式保存，压缩形式是每个数字用位表示，这样就是位，由于的二
6、进制表示形式，不能用位表示，我使用了一个小技巧就是将表示为，然后用多出来的位表示所在的位置，就可以用表示了。用移位和或操作将数据逐个移入，比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。类CNineGird结构如下：class CNineGirdpublic:struct PlaceList DWORDPlace;PlaceList*Left;PlaceList*Right; ;struct ScanbufDWORD Place;int ScanID;struct PathListunsigned char Path9;private:PlaceList *m_pP
7、laceList;Scanbuf *m_pScanbuf;RECT m_rResetButton;RECT m_rAutoButton;public:int m_iPathsize;clock_t m_iTime;UINT m_iStepCount;unsigned char m_iTargetChess9;unsigned char m_iChess9;HWND m_hClientWin;PathList *m_pPathList;bool m_bAutoRun;private:inline bool AddTree(DWORD place , PlaceList*& parent);voi
8、d FreeTree(PlaceList*& parent);inline void ArrayToDword(unsigned char *array , DWORD & data);inline void DwordToArray(DWORD data , unsigned char *array);inline bool MoveChess(unsigned char *array , int way);bool EstimateUncoil(unsigned char *array);void GetPath(UINT depth);public:void MoveChess(int
9、way);bool ComputeFeel();void ActiveShaw(HWND hView);void DrawGird(HDC hDC , RECT clientrect);void DrawChess(HDC hDC , RECT clientrect);void Reset();void OnButton(POINT pnt , HWND hView);public:CNineGird();CNineGird();类的构造函数与析构函数代码：CNineGird:CNineGird()m_pPathList = NULL;m_pPlaceList = NULL;m_pScanbu
10、f = NULL;m_iPathsize = 0;m_iTime = 0;m_bAutoRun = false;Reset();CNineGird:CNineGird()if (m_pPathList != NULL)delete m_pPathList;if (m_pScanbuf != NULL)delete m_pScanbuf;画图函数代码：void CNineGird:DrawGird(HDC hDC , RECT clientrect)int cx = clientrect.right / 2 - 180 ;int cy = clientrect.bottom / 2 - 60 ;
11、int i , j;HBRUSH hgirdbkbrush = :CreateSolidBrush(RGB(255 , 128 , 64);HBRUSH hbutbrush = :CreateSolidBrush(RGB(0 , 128 , 255);HBRUSH oldbrush = (HBRUSH):SelectObject(hDC , hgirdbkbrush);COLORREF oldbkcolor = SetBkColor(hDC , RGB(0 , 128 , 255);/ Draw fountain girdRECT rect;for (i = 0 ; i 3 ; i +)for
12、 ( j = 0 ; j 3 ; j +)SetRect(&rect , 0 , 0 , 40 , 40);OffsetRect(&rect , i * 40 + cx, j * 40 + cy);Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);/ Draw target girdcx = clientrect.right / 2 + 60 ;for (i = 0 ; i 3 ; i +)for ( j = 0 ; j 3 ; j +)SetRect(&rect , 0 , 0 , 40 , 40);Offset
13、Rect(&rect , i * 40 + cx, j * 40 + cy);Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);SelectObject(hDC , hbutbrush);/ draw step rectcx = clientrect.right / 2 - 30 ;cy += 10;SetRect(&rect , 0 , 0 , 80 , 20);OffsetRect(&rect , cx - 10 , cy);Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);char step100;sprintf(step , Step: %d , m_iStepCount);
