我加紧学习，我要慢慢赶超你们！！

楼主开QQ吧，QQ上说

BUG我已经找到了，哈哈，低级错误

BUG描述如下：
        if(dir!=left&&j<2 )    //可以向右
        {
            matrix[i][j] = matrix[i][j+1];
            matrix[i][j+1] = 0;
            ret = iterative_deepening(k+1,d,i,j+1,left);
            matrix[i][j+1] = matrix[i][j];
            matrix[i][j] = 0;
            if(!ret)
                return print_matrix(k);
        }
        
        if(dir!=right&&j>0 )    //可以向左
        {
            matrix[i][j] = matrix[i][j-1];
            matrix[i][j-1] = 0;
            ret = iterative_deepening(k+1,d,i,j-1,left);
            matrix[i][j-1] = matrix[i][j];
            matrix[i][j] = 0;
            if(!ret)
                return print_matrix(k);
        }

仔细看一下这段代码中，有什么应该不一样的东西，却一样了？？

一天了没有人报告gug，基本上可以说偶的代码是完美的了，这回的自信不算盲目的

我之所以使用迭代加深是因为DFS可能会绕圈子，不保证找到最优解，而BFS要记录OPEN表的状态节点，太麻烦，A*跟BFS一样要需要记录节点的表。所以偶使用深度优先，有DFS不需要节点表的优点，又有BFS可以找到最优解的优点。迭代加深在每一次给定边界的搜索中都是DFS，而从不断修改深度边界来看又是BFS，扬长避短，迭代加深在信息不完全的盲目搜索中算是优秀的算法。

Uninformed breadth-first search:
Requires the construction and memorization of almost the complete search tree.
Is guaranteed to find the shortest path to a solution.

Uninformed depth-first search:
Requires the memorization of only the current path and the branches from this path that were already visited.
May search unnecessarily deep for a shallow goal.

蓝色线段树同学帮我找到了31这个深度边界，MAX_DEPTH的值就确定了。其实偶发代码就是想让人帮我测试找到这个值，哇哈哈~~


这意思貌似是BS偶的迭代加深算法的时间复杂度，迭代加深最坏情况下的时间复杂度和广度优先是一个数量级的，这是因为状态树的节点数随深度增加近似指数增长，搜索到最后一层遍历的节点数才是影响时间复杂度的主要因素，迭代加深搜索这一层时遍历的节点数跟BFS相同。
我前面给的课件中有复杂度的详细分析，节选部分：
For large d, you see that Nid/Nbf approaches b/(b – 1), which in turn approaches 1 for large b.

理论上一个数量级，实际运行差多少你有兴趣测试出来了告诉我。
这个问题最快的是启发式的A*搜索，不过除非程序运行时间超出我忍耐限度，否则偶不会改算法的。

收到的鲜花

• liyanhong 于 2008-10-21 18:52 送鲜花  49朵   附言：很精彩

我早运行过了，时间是严重超时

你到底上不上Q啊？

>>  这意思貌似是BS偶的迭代加深算法的时间复杂度
这是绝对BS的，因为偶的程序最坏情况下也只要0.5秒

并且，假如是在OJ上，有多组数据的时候，这个差距将不断地拉大

偶写完程序只测试了一组数据2 8 3 1 6 4 7 0 5没有发现问题。
偶看起来好像有些小白，每次自信心过剩就出问题，真是严重伤害偶幼小的心灵。
这个错误是因为程序快写完了，过于兴奋造成的。

偶曾今在Solaris服务器上运行一个垃圾算法36小时，现在天气凉爽忍耐限度至少有72小时，至于oj时间要求和我无关。