IDA* ，也就是在 ID （迭代加深搜索）上使用 A* 的思想，引入一个估值函数 h(x)h(x) ，来及时剪枝，减少不必要的搜索

但其实吧，我感觉这个也没什么好讲的，这东西感觉也没什么新意，就是一个简单的剪枝，并不是像 A* 一样让更有潜力状态的更先搜索

附上一道例题

UVA1343 旋转游戏 The Rotation Game ，或者是 HDU1667

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;

//        1     2
//        3     4
//  5  6  7  8  9 10 11
// 		  12    13
//  14 15 16 17 18 19 20
//        21    22
//        23    24

int board[32];
int centerId[8] = {7, 8, 9, 13, 18, 17, 16, 12};
int movePath[8][7] = {{1, 3, 7, 12, 16, 21, 23},
                      {2, 4, 9, 13, 18, 22, 24},
                      {11, 10, 9, 8, 7, 6, 5},
                      {20, 19, 18, 17, 16, 15, 14},
                      {24, 22, 18, 13, 9, 4, 2},
                      {23, 21, 16, 12, 7, 3, 1},
                      {14, 15, 16, 17, 18, 19, 20},
                      {5, 6, 7, 8, 9, 10, 11}};
int rollbackMoveId[8] = {5, 4, 7, 6, 1, 0, 3, 2};

char ans[10024];
int lim = 1;


// h(x)估值函数
int h()
{
    int count[4] = {0};
    for (int i = 0; i < 8; i++)
        count[board[centerId[i]]]++;
    return 8 - max(count[1], max(count[2], count[3]));
}

void move(int dir)
{
    int tmp = board[movePath[dir][0]];
    for (int i = 0; i < 6; i++)
        board[movePath[dir][i]] = board[movePath[dir][i + 1]];
    board[movePath[dir][6]] = tmp;
}

bool IDA_Star(int now)
{
    if (h() == 0)
        return 1;
    if (h() + now > lim)
        return 0;
    for (int i = 0; i <= 7; i++)
    {
        move(i);
        ans[now] = i + 'A';
        if (IDA_Star(now + 1))
            return 1;
        move(rollbackMoveId[i]);
    }
    return 0;
}

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    while (1)
    {
        cin >> board[1];
        if (board[1] == 0)
            return 0;
        for (int i = 2; i <= 24; i++)
            cin >> board[i];
        if (h() == 0)
        {
            cout << "No moves needed" << endl
                 << board[centerId[1]] << endl;
            continue;
        }
        lim = 1;
        while (!IDA_Star(1))
            lim++;
        for (int i = 1; i < lim; i++)
            cout << ans[i];
        cout << endl
             << board[centerId[1]] << endl;
    }
}