首页 > 用户发贴区 > 编程问题提问区 > 求 :八数码启发式搜索算法
2006
05-28

求 :八数码启发式搜索算法

有会八数码启发式搜索算法的程序,也就是八数码问题的程序!如果会 的话请联系我QQ68560901,6月2号之前 哦,谢谢虫虫眼6238865.9146064815


求 :八数码启发式搜索算法》有 4 条评论

  1. VC爱好者 说:

    问题描述:

           有一个3×3的棋盘,其中有0~8九个数字,0表示空格,其他的数字可以和0交换位置。求由初始状态到达目标状态步数最少的解。

           解决八数码问题的常用方法为图搜索法,可用广度优先、深度优先和A*算法实现,其中A*算法又因估价函数的不同而有着不同的搜索时间。

    程序说明:

           在本程序中,用广度优先、深度优先和A*算法分别实现了八数码问题,其中A*算法的估价函数选择的是“不在位”数和当前层数之和,初始状态和目标状态均可由用户设定,目标状态默认为:

    1 2 3
    4 5 6
    7 8 0

            这里是A*算法的可执行程序,由用户输入一组数码,如:

    8 3 5
    1 2 7
    4 6 0

            然后程序会询问用户是否要更改目标,输入N即可。等一会儿(几秒到几十秒)后便可得到结果以及消耗的时间和空间。程序中的Block是指生成的8数码块,以此来衡量空间消耗的多少。

            这里是广度优先的可执行程序,使用方法同上。广度优先算法当步数较多时消耗的时间可能会比A*算法少,但会消耗较多的空间,因此当计算很长一段时间后仍无结果时应按CTRL+C强行退出,谨防死机。

            深度优先算法当问题复杂时时间消耗很多,基本不能用,因此在这里就不给出可执行程序了,需要者可下载下面的源代码自行研究。

    算法简评:

           三种算法在一定条件下均可得到八数码问题的解。但是广度优先算法当目标的深度较深时,产生很多冗余节点,空间消耗很大(在运行中曾造成过死机)。有限深度优先算法在时间或空间复杂度上均没有明显的优势,但如果目标深度较深而且路径选择得当的话,可以较快地得到解答。A*算法可以消耗较少的空间解决问题,但是由于每次选择均需要寻找估价函数最小的节点,因此当深度增加相应的节点数目增加时,A*算法在时间上并不占优势。然而,A*算法总可以在有限的时间内得到问题的解。

    已知可解问题:

    8 3 5    4 3 2     2 0 3
    1 2 7    1 0 5     1 8 5
    4 6 0    6 7 8     4 7 6

            A*算法总可在有限时间内(曾试过75秒)解决文曲星中可解的数字拼图问题。

    源代码:

            这里是程序的源代码,有兴趣的同志可以下载研究,欢迎指教和提问。

  2. 虫虫眼62 说:

    谢谢,大哥,可是没有源码呀!我是什么都不会的,555,麻烦你传个源码给我好吗?万分感谢!

留下一个回复