Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

半成品，還沒有用hash判重複
作法 : IDA*
跟 A* 的差別就是少一個 heap去抓最小值出來擴張，因此會重複走點
15 數碼，只能用 IDA* ，A* 會記憶體爆炸

IDA*(Iterative deepening A*)即是迭代加深启发式搜索.在这题当中,实际上是把启发函数用来做剪枝了,算法如下:

1.定义启发函数 H()为∑[abs(xInit-xTarget)+abs(yInit-yTarget)],由于每次移动H值最多少1,所以它是相容的.
2.设初始迭代深度为初始状态的H值 H(initStatus);
3.迭代加深进行搜索.
4.如果 当前搜索深度 + H值 > 迭代深度,则剪枝.


/**********************************************************************************/
/*  Problem: d920 "智慧盤" from                                                */
/*  Language: C                                                                   */
/*  Result: AC (3ms, 258KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-07-07 11:45:41                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct status {
    int board[4][4];
    int px, py;
}init, target = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,3,3};
int pos[17][2], MaxDepth, flag;
int step[4][2] = {{-1,0}, {0,-1},{0,1},{1,0}};/*u l r d*/
void Swap(int *x, int *y) {
    int t;
    t = *x, *x = *y, *y= t;
}
int H() {
    int sum = 0, tmp, a, b;
    for(a = 0; a < 4; a++) {
        for(b = 0; b < 4; b++) {
            tmp = init.board[a][b];
            if(tmp < 16)
                sum += abs(a-pos[tmp][0]) + abs(b-pos[tmp][1]);
        }
    }
    return sum;
}
int SingleH(int x, int y, int tmp) {
    return abs(x-pos[tmp][0]) + abs(y-pos[tmp][1]);
}
int IDAstar(int dv, int hv, int prev) {
    if(hv == 0) { flag = dv;return dv; }
    if(dv + hv > 10 || dv + hv > MaxDepth)    return dv + hv;

    int a, nx, ny, x = init.px, y = init.py;
    int tMaxDepth = 10000, dn, ht;
    
    for(a = 0; a < 4; a++) {
        if(a + prev == 3) continue;
        nx = x + step[a][0], ny = y + step[a][1];
        if(nx < 0 || nx == 4 || ny < 0 || ny == 4)
            continue;
       
        ht = hv - SingleH(nx, ny, init.board[nx][ny]) + SingleH(x, y, init.board[nx][ny]);
        Swap(&init.board[x][y], &init.board[nx][ny]);
        init.px = nx, init.py = ny;
        dn = IDAstar(dv+1, ht, a);
        Swap(&init.board[x][y], &init.board[nx][ny]);
        init.px = x, init.py = y;
        if(flag)    return dv;
        if(tMaxDepth > dn) tMaxDepth = dn;
    }
    return tMaxDepth;
}
main() {
    int T, a, b, ini;
    int index = 0;
    for(a = 0; a < 4; a++)
        for(b = 0; b < 4; b++) {
            scanf("%d", &init.board[a][b]);
            if(init.board[a][b] == 0) {
                init.board[a][b] = 16;
                init.px = a, init.py = b;
            }
            index++;
            pos[index][0] = a, pos[index][1] = b;
        }
    if(H()) {
        MaxDepth = H(), flag = 0, ini = MaxDepth;
        while((flag == 0) && (MaxDepth <= 10))
            MaxDepth = IDAstar(0, ini, -1);
        if(flag)
            printf("%d\n", flag);
        else
            puts("TOO LONG");
    }
    else puts("0");
    return 0;
}