人工智能课内实验报告2

1、人工智能课内实验报告（二） -重排九宫（ a*算法）一、实验目的1. 熟悉启发式搜索的思想，加深对各种图搜索策略概念的理解；2. 运用搜索算法重排九宫使之从初始状态到底目标状态，并求解最短路径。二、实验内容在三种不同的搜索算法中任选一种实现重排九宫。这三种方法分别是：a* 算法、有界深度优先搜索和广度优先搜索。具体描述：在一个33 的方格棋盘上放置8 个标有 1、2、3、4、5、6、7、8 数字的将牌，留下一个空格（用0 表示） 。规定：与空格相邻的将牌可以移入空格。要求：寻找一条从初始状态到目标状态的将牌移动路线。三、实验原理启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着

2、最有希望的方向前进，加速问题的求解过程并找到最优解。a* 算法是一种启发式搜索。广度优先搜索按照“先扩展出的节点先被考察”的原则进行搜索。深度优先搜索按照“后扩展出的节点先被考察”的原则进行搜索。有界深度优先搜索的原则与深度优先搜索相同，但是它规定了深度限界，使搜索不得无限制地向纵深方向发展。（一）搜索的一般描述：1. 把初始节点s0放入 open 表，并建立目前只包含s0 的图，记为g；2. 检查 open 表是否为空，若为空则问题无解，退出；3. 把 open 表的第一个节点取出放入close 表，并计该节点为n；4. 考察节点n 是否为目标节点。若是，则求得了问题的解，退出；5. 扩展节

3、点n，生成一组子节点。把其中不是节点n 先辈的那些子节点记做集合m，并把这些子节点作为节点n 的子节点加入g 中；6. 针对 m 中子节点的不同情况，分别进行如下处理：（1）对于那些未曾在g 中出现过的m 成员设置一个指向父节点（即节点n）的指针，并把它们放入open 表； （不在 open 表）（2）对于那些先前已经在g 中出现过的m 成员，确定是否需要修改它指向父节点的指针； （在 open 表中）（3） 对于那些先前已在g 中出现并且已经扩展了的m 成员，确定是否需要修改其后继节点指向父节点的指针；（在 close 表中）7. 按某种搜索策略对open 表中的节点进行排序；8. 转第 2

4、 步。（二） a*算法描述：1. 把初始节点s0放入 open 表，并建立目前只包含s0 的图，记为g；2. 检查 open 表是否为空，若为空则问题无解，退出；3. 把 open 表的第一个节点取出放入close 表，并计该节点为n；4. 考察节点n 是否为目标节点。若是，则求得了问题的解，退出；5. 扩展节点n，生成一组子节点。把其中不是节点n 先辈的那些子节点记做集合m，并把这些子节点作为节点n 的子节点加入g 中；6. 针对 m 中子节点的不同情况，分别进行如下处理：（1）对于那些未曾在g 中出现过的m 成员设置一个指向父节点（即节点n）的指针，并把它们放入open 表； （不在 op

5、en 表）（2）对于那些先前已经在g 中出现过的m 成员，确定是否需要修改它指向父节点的指针； （在 open 表中 ,对 g(x)进行更新）（3）对于那些先前已在g 中出现并且已经扩展了的m 成员，确定是否需要修改其后继节点指向父节点的指针；（在 close 表中 , 对节点 n 子节点的子节点更新g(x) ）7. 对 open 表中的节点按估价函数进行排序；8. 转第 2 步。四、a*算法实验程序及运行结果程序如下：#include iostream.h #include #include #include #include static int target9=1,2,3,8,0,4,7

6、,6,5; /class definition class eight_num private: int num9; int not_in_position_num; int deapth; int eva_function; public: eight_num* parent; eight_num* leaf_next; eight_num* leaf_pre; eight_num(int init_num9); eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9

7、) num0=num1; num1=num2; num2=num3; num3=num4; num4=num5; num5=num6; num6=num7; num7=num8; num8=num9; eight_num(void) for (int i=0;i9;i+) numi=i; void cul_para(void); void get_numbers_to(int other_num9); int get_nipn(void) return not_in_position_num; int get_deapth(void) return deapth; int get_evafun

8、(void) return eva_function; void set_num(int other_num9); void show(void); eight_num& operator=(eight_num&); eight_num& operator=(int other_num9); int operator=(eight_num&); int operator=(int other_num9); ; /计算启发函数g(n)的值void eight_num:cul_para(void) int i; int temp_nipn=0; for (i=0;i

9、parent=null) deapth=0; else deapth=this-parent-deapth+1; eva_function=not_in_position_num+deapth; /构造函数1 eight_num:eight_num(int init_num9) for (int i=0;i9;i+) numi=init_numi; /显示当前节点的状态void eight_num:show() coutnum0; cout ; coutnum1; cout ; coutnum2; coutn; coutnum3; cout ; coutnum4; cout ; coutnum

10、5; coutn; coutnum6; cout ; coutnum7; cout ; coutnum8; coutn; /复制当前节点状态到一个另数组中void eight_num:get_numbers_to(int other_num9) for (int i=0;i9;i+) other_numi=numi; /设置当前节点状态(欲设置的状态记录的other 数组中 ) void eight_num:set_num(int other_num9) for (int i=0;i9;i+) numi=other_numi; eight_num& eight_num:operator

11、=(eight_num& another_8num) for (int i=0;i9;i+) numi=another_8num.numi; not_in_position_num=another_8num.not_in_position_num; deapth=another_8num.deapth+1; eva_function=not_in_position_num+deapth; return *this; eight_num& eight_num:operator=(int other_num9) for (int i=0;i9;i+) numi=other_numi

12、; return *this; int eight_num:operator=(eight_num& another_8num) int match=1; for (int i=0;i9;i+) if(numi!=another_8num.numi) match=0; break; if (match=0) return 0; else return 1; int eight_num:operator=(int other_num9) int match=1; for (int i=0;i9;i+) if(numi!=other_numi) match=0; break; if (ma

13、tch=0) return 0; else return 1; /class definition over /空格向上移int move_up(int num9) for (int i=0;i9;i+) if (numi=0) break; if (i3) return 0; else numi=numi-3; numi-3=0; return 1; /空格向下移int move_down(int num9) for (int i=0;i5) return 0; else numi=numi+3; numi+3=0; return 1; /空格向左移int move_left(int num

14、9) for (int i=0;i9;i+) if (numi=0) break; if (i=0|i=3|i=6) return 0; else numi=numi-1; numi-1=0; return 1; /空格向右移int move_right(int num9) for (int i=0;i9;i+) if (numi=0) break; if (i=2|i=5|i=8) return 0; else numi=numi+1; numi+1=0; return 1; /判断可否解出int icansolve(int num9,int target9) int i,j; int co

15、unt_num,count_target; for (i=0;i9;i+) for (j=0;ji;j+) if(numjnumi&numj!=0) count_num+; if(targetjparent) if(*p=num) return 1; return 0; /寻找估价函数最小的叶子节点eight_num* find_ok_leaf(eight_num* start) eight_num *p,*ok; p=ok=start; int min=start-get_evafun(); for(p=start;p!=null;p=p-leaf_next) if(minp-get

16、_evafun() ok=p; min=p-get_evafun(); return ok; /主函数开始int main(void) double time; clock_t start,finish; int memery_used=0,step=0; int num9; int flag=0;/ 是否输入错误标志，1 表示输入错误int bingo=0;/ 是否查找成功标志，1 表示成功int i,j; /cout 重排九宫 nn; cout初始状态 :n; for (i=0;inumi; for(j=0;ji;j+) if(numi=numj) flag=1; if (numi8|fl

17、ag=1) i-; cout 包含无效的数字!n; eight_num s(num),target(target); s.parent=s.leaf_next=s.leaf_pre=null; s.cul_para(); memery_used+; cout初始状态为 :n; s.show(); cout目标状态为 :n; target.show(); if(!icansolve(num,target) couti; return 1; else coutleaf_pre; ok_leaf-get_numbers_to(num); if(move_up(num)&!existed(nu

18、m,ok_leaf) new_8num=new eight_num; new_8num-set_num(num); new_8num-parent=ok_leaf; new_8num-cul_para(); new_8num-leaf_pre=p; if(p=null) leaf_start=new_8num; else p-leaf_next=new_8num; p=new_8num; memery_used+; ok_leaf-get_numbers_to(num); if(move_down(num)&!existed(num,ok_leaf) new_8num=new eigh

19、t_num; new_8num-set_num(num); new_8num-parent=ok_leaf; new_8num-cul_para(); new_8num-leaf_pre=p; if(p=null) leaf_start=new_8num; else p-leaf_next=new_8num; p=new_8num; memery_used+; ok_leaf-get_numbers_to(num); if(move_left(num)&!existed(num,ok_leaf) new_8num=new eight_num; new_8num-set_num(num)

20、; new_8num-parent=ok_leaf; new_8num-cul_para(); new_8num-leaf_pre=p; if(p=null) leaf_start=new_8num; else p-leaf_next=new_8num; p=new_8num; memery_used+; ok_leaf-get_numbers_to(num); if(move_right(num)&!existed(num,ok_leaf) new_8num=new eight_num; new_8num-set_num(num); new_8num-parent=ok_leaf; new_8num-cul_para(); new_8num-leaf_pre=p; if(p=null) leaf_start=new_8num; els