被那女老师气得不轻啊，真想扁她，连学生文章是不是自己写的都看不出来，还敢教人工智能这种高IQ的人才能教好的课，真是受不了。                                                                     八数码广度优先搜索策略         八数码问题，类似于拼图，9格8个数，从当前状态开始移动，到指定状态即完成操作，可以用广度优先搜索或是深度优先搜索来解决。广度优先，顾名思义，就是优先在现深度上扩展，找出当前深度上的所有情况，再向下一级深度进行扩展搜索，所以这种解法必定可以找出答案（当然前提是有答案），代价就是比较恐怖的空间和时间消耗。         首先，我设定一个节点包含的数据有：当前状态，即一个3x3二维数组，一个指向双亲节点的回溯指针，三个指向孩子节点的指针（可有可无，纯粹为了找答案大可不必搞得指针漫天飞），一个指向兄弟节点的指针（我为了设计这个广度优先算法特意添加的，没有看标准的解法，不知道合不合理），一个int型的节点深度数据，由双亲节点加1获得，空格的x和y坐标值。         除此之外还有一个全局型的二维数组专门存放终止状态，一个全局型的节点类型指针存放终止节点地址，一个二维数组存放空格的所有移动方式，由一个TXT的文本来获得初始和终止状态。算法思路：        1.初始化空间树的头结点，生成一个兄弟链表，头结点指向树的头结点，即为0深度的兄弟链表。        2.生成一个新的兄弟链表，成员由双亲层的兄弟节点顺次获得，若有节点满足终止条件，即将此节点地址赋给全局终止状态节点变量，返回。        3.将上一步获得的兄弟链表定义为双亲层，执行步骤2。         由此可见八数码问题的算法并不复杂，本来可以不用递归来实现的（我始终认为能不用递归就不用递归），但是我不愿意再去为这个程序设定新的变量和循环体。关于深度优先搜索的非递归算法我也设计过，但是没实现，感觉这个算法的代码量更少，在这个程序的基础上稍加改动，添加一个移动次数累加计数就行了。算法思路：         1.初始化空间树头结点，设定为当前节点         2.考察当前节点移动计数和深度，若移动计数达到3或深度达到预设值则返回双亲节点，命其为当前节点，执行2，否则对节点状态进行改变考察，同时移动计数加1，若满足移动条件，执行3，否则执行2.         3.新建节点，数据由双亲节点移动获得（2中节点），命其为当前节点，考察是否满足终止条件，满足则返回此节点地址，否则执行2。         算法是否正确合理我不知道，因为没有编程实现，按照这个算法，一个while循环就可以实现此算法。哪位有兴趣可以帮我实现看一下，感激不尽。

评论