嗯，长见识～～
收藏起来，慢慢研究。

我当年写的那个树的结构比较烂，只能线性查。
听老杨说他的那个能 O(1) 的查，感觉挺神奇。


[ 本帖最后由 pangding 于 2012-3-7 22:49 编辑 ]

我觉得他的的意思是 O(9!)计算（预处理），只要记录一条最短路径就行了，
O(1)的移动，而不是边计算边移动


++ 说错了，我也不太懂，

[ 本帖最后由 BlueGuy 于 2012-3-7 23:35 编辑 ]

这个问题，只要树建好后，找到结点也就找到了路径。我不态清楚老杨的衡量标准，如果把9！看作常数那就是o(1)了。
我的代码之所以用数组代替了常规的指针结构，就是为了应用二分查找。任何状态都可以在18次内找到。

收到的鲜花

• pangding 于 2012-03-08 11:55 送鲜花  49朵   附言：嗯。所以说你的结构比我好很多。

给代码吧。。。。。。。。。。。。。。。。。怎么没代码呢？？

学习了！！

学习学习哈哈

9!不过36万而已  先广搜预处理 把这36万多个状态的最短路径全部存储起来

至于怎么在O（1）的时间内找到这个状态  就是康托展开式的应用  

比如3！有 123 132 213 231 312 321 这六个  要找到任何一个排列是第几个数

比如123 就是第一个  132 就是第二 。。。 321 就是第六个

其实康托展开式找到的是任何一个排列数前面有几个排列数  具体算法是

对于排列数的每一位判断后面有几个位置 可以把那几个比它小的安排进去

比如123 i = 0*2！(有0个比1小的数)(后面有两个位置) + 0*1！(有1个比2小的数，但是1已经在前面出现了)(后面有1个位置) + 0*0(有2个比3小的数，但是都在前面出现了)(后面有0个位置) = 0 （在123这个排列前面的排列数目为0）

比如231 i = 1*2！(有1个比2小的数)(后面有两个位置) + 1*1！(有2个比3小的数，但是2已经在前面出现了)(后面有1个位置) + 0*0(有0个比1小的数)(后面有0个位置) = 3 （在123这个排列前面的排列数目为3）



[ 本帖最后由 laoyang103 于 2012-3-8 17:15 编辑 ]

把核心代码给大牛们看一下啊  其实就是一个广度有限搜索  还有一个 状态定位函数

int CLaoYangWnd::kangtuo(char a[])
{
    int fac[]={1,1,2,6,24,120,720,5040,40320};//康托展开判重
    int i,j,sum = 0,t = 0;
    for(i = 0;i<9;i++)
    {
        t = 0;
        for(j = i+1;j<9;j++)
            if(a[j]<a[i])
                t++;
        sum += t*fac[9-i-1];
    }
    return sum+1;
}

void CLaoYangWnd::bfs()
{
    char h[4] = {'d','u','r','l'};
    int i,x,y;
    Node now,next;now.pa = "";next.pa = "";
    for(i = 0;i<8;i++)now.a[i] = i+1;
    now.a[8] = 0;now.pos = 8;
    now.index = 46234;foot[46234] = true;   
    queue<Node> q;q.push(now);
    int dec[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        for(i = 0;i<4;i++)
        {
            x = now.pos/3+dec[i][0];
            y = now.pos%3+dec[i][1];
            if(x<0 || y<0 || x>2 || y>2)
                continue;
            next = now;
            next.pos = 3*x+y;
            next.a[next.pos] = 0;
            next.a[now.pos] = now.a[next.pos];
            next.index = kangtuo(next.a);
            if(!foot[next.index])
            {
                foot[next.index] = true;
                next.pa += h[i];
                path[next.index] = next.pa;
                q.push(next);
            }
        }
    }
   
}

完整的工程

[ 本帖最后由 laoyang103 于 2012-3-8 17:24 编辑 ]

这个源代码可不可以玩玩啊丶

为啥不可以呢   有VC6.0就行