作业帮八数码问题算法,谁有?
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/05/17 06:27:42
八数码问题算法,谁有?
我要算法,不要代码
广度优先或者深度优先等都行.
我要算法,不要代码
广度优先或者深度优先等都行.
广度优先搜索法
在搜索法中,广度优先搜索法是寻找最短路经的首选.
1.广度优先搜索算法的基本步骤
1）建立一个队列,将初始结点入队,并设置队列头和尾指针
2）取出队列头（头指针所指）的结点进行扩展,从它扩展出子结点,并将这些结点按扩展的顺序加入队列.
3）如果扩展出的新结点与队列中的结点重复,则抛弃新结点,跳至第六步.
4）如果扩展出的新结点与队列中的结点不重复,则记录其父结点,并将它加入队列,更新队列尾指针.
5）如果扩展出的结点是目标结点,则输出路径,程序结束.否则继续下一步.
6）如果队列头的结点还可以扩展,直接返回第二步.否则将队列头指针指向下一结点,再返回第二步.
2.搜索路径的输出
搜索到目标结点后,需要输出搜索的路径.每个结点有一个数据域last,它记录了结点的父结点,因此输出搜索路径时,就是从目标结点Q出发,根据last找到它的父结点,再根据这个结点的last找到它的父结点,.,最后找到初始结点.搜索的路径就是从初始结点循相反方向到达目标结点的路径.
在搜索法中,广度优先搜索法是寻找最短路经的首选.
1.广度优先搜索算法的基本步骤
1）建立一个队列,将初始结点入队,并设置队列头和尾指针
2）取出队列头（头指针所指）的结点进行扩展,从它扩展出子结点,并将这些结点按扩展的顺序加入队列.
3）如果扩展出的新结点与队列中的结点重复,则抛弃新结点,跳至第六步.
4）如果扩展出的新结点与队列中的结点不重复,则记录其父结点,并将它加入队列,更新队列尾指针.
5）如果扩展出的结点是目标结点,则输出路径,程序结束.否则继续下一步.
6）如果队列头的结点还可以扩展,直接返回第二步.否则将队列头指针指向下一结点,再返回第二步.
2.搜索路径的输出
搜索到目标结点后,需要输出搜索的路径.每个结点有一个数据域last,它记录了结点的父结点,因此输出搜索路径时,就是从目标结点Q出发,根据last找到它的父结点,再根据这个结点的last找到它的父结点,.,最后找到初始结点.搜索的路径就是从初始结点循相反方向到达目标结点的路径.