人工智能8位数码难题的问题求解.doc

实 验 报 告 实验名称：8位数码难题的问题求解 实验目的和要求： 目的： 1.理解和掌握解决实际问题的有哪些信誉好的足球投注网站算法或策略； 2.能够用选定的编程语言实现有哪些信誉好的足球投注网站算法； 要求： 1.随机输入1-8数字； 2.采用所学过的有哪些信誉好的足球投注网站算法（算法不限，但需要有注释，采用算法之 一，或几种算法实现）； 3.要求输出算法执行的过程结果； 4.按顺序输出1-8数字； 实验软硬件要求：网络计算机，c++编程环境 实验内容、方法和步骤（可附页） 我们将八数码难题分布在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态如图所示，可以使用的操作有:空格上移，空格左移，空格右移，空格下移。我们将是用广度优先有哪些信誉好的足球投注网站算法来解决这一问题。 我们先拟定初始数列为0 3 5 2 1 4 8 7 6（0表示空位） 算法流程图：初始状态 3 5 2 1 4 8 7 6 1 2 3 8 4 7 6 5 结果 数据结构： 本实验使用的数据结构是队列，应用队列先进先出的特点来实现对节点的保存和扩展。首先建立一个队列，将初始结点入队，并设置队列头和尾指，然后取出队列（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列，然后判断扩展出的新结点与队列中的结点是否重复，如果重复则，否则记录其父结点，并将它加入队列，更新队列尾指针，然后判断扩展出的结点是否是目标结点，如果是则显示路径，程序结束。否则如果队列头的结点可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步，知道扩展出的结点是目标结点结束，并显示路径。 代码如下： #include stdio.h #include stdlib.h #include windows.h #include queue #include stack using namespace std; #define HashTableSize 362881 #define NOT ! #define UP 0 #define DOWN 1 #define LEFT 2 #define RIGHT 3 #define Bit char typedef struct maps { Bit detail[9]; int myindex; // 记录自己节点在hash表中的位置 Bit position; // 记录 空格（0）在序列中的位置 }Map,*PMap; Map org; // 初始状态 int EndIndex; //目标,上移 ，下移 ， 左移 ，右移 int const derection[4] ={ -3 , 3 , -1 , 1 } ; // 可移动的四个方向 int const Factorial[9] = {40320 , 5040 , 720 , 120 , 24 , 6 , 2 , 1 , 1 }; int HashTable[HashTableSize]={0}; //hash表,其中记录的是上一个父节点对应的位置 /****八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）***/ void input() { int i,j; int sum , count ,index ; printf(输入九个数：\n); //必须输入一个0作为空值 for(i = 0 ; i 9 ; i ++ ) { scanf(%1d, org.detail[ i ] ); org.detail[ i ] || (org.position = i) ; } for(i = 0 ; i 9 ; i ++ ) //计算逆序 { if( 0 == org.detail[ i ] ) continue; for(j = 0 ; j i; j ++ ) sum += ( 0 != org.detail[ j ] org.detail[ j ] org.detail[ i ] ); } for( i = 0 , index = 0 ; i 9 ; i ++ ) // 计算初始状态的hash值 { for(j = 0 , count = 0 ; j i ; j ++) count += org.d