其实在此之前还是相当没有重视搜索。

最近还是要赶快把各种姿势学起来。

Table of Contents

  1. Overview
  2. Examples
    1. Problem 1 BZOJ1975
      1. Solution
      2. Code
    2. Problem 2 BZOJ1085
      1. Solution
      2. Code
    3. Problem 3 BZOJ1598

Overview

A*算法其实就是带有估价函数，并以此作为剪枝手段，保证时间复杂度的搜索算法。

其中估价函数越接近实际答案，搜索进行得越快。

Examples

Problem 1 BZOJ1975

Solution

k短路是一个经典的运用A*算法的问题（在不被卡的情况下）。

由于A*算法保证每次选出最优解，在本题中，我们就可以逐步累加代价直到耗尽能量。估价函数定义为到达节点$1$所需的距离，利用小根堆，维护当前节点到节点$n$的最短路 + 估价函数最小值，每次取出，进行决策。注意需要跑反图的最短路。

洛谷上有Hack数据，复杂度更稳定的做法在这里暂不讨论。

Code

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
 
using std::min;
using std::max;
using std::swap;
using std::memset;
using std::bitset;
using std::priority_queue;
 
const int maxn = 5002;
const int maxm = 200002;
const int maxp = 5e+6 + 5;
 
struct edge
{
    int to, nxt;
    double v;
}e[maxm], re[maxm];
int n, m, ans;
int lnk[maxn], ptr, rlnk[maxn], rptr;
struct que
{
    int a[maxn], h, t;
    que()
    {
        memset(a, 0, sizeof a);
        h = t = 0;
    }
    inline bool empty()
    {
        return h == t;
    }
    inline void push(int x)
    {
        t++; if(t == maxn) t = 0;
        a[t] = x;
    }
    inline void move()
    {
        h++; if(h == maxn) h = 0;
    }
    inline int front()
    {
        return a[h];
    }
};
double E, dis[maxn];
bitset<maxn> vis;
struct node
{
    int id;
    double g;
    bool operator < (const node &rhs) const
    {
        if(g + dis[id] == rhs.g + dis[rhs.id]) return g > rhs.g;
        return dis[id] + g > dis[rhs.id] + rhs.g;
    }
};
priority_queue<node> hp;
 
inline void add(int bgn, int end, double val, bool type)
{
    if(type)
    {
        e[++ptr] = (edge){end, lnk[bgn], val};
        lnk[bgn] = ptr;
    }
    else
    {
        re[++rptr] = (edge){end, rlnk[bgn], val};
        rlnk[bgn] = rptr;
    }
}
inline void spfa()
{
    que q;
    for(int i = 1; i <= n; ++i) dis[i] = 1e12;
    dis[n] = 0.0; vis.set(n); q.push(n);
    while(!q.empty())
    {
        q.move();
        int u = q.front(); vis.reset(u);
        for(int p = rlnk[u]; p; p = re[p].nxt)
        {
            int y = re[p].to;
            if(dis[y] > dis[u] + re[p].v)
            {
                dis[y] = dis[u] + re[p].v;
                if(!vis.test(y))
                {
                    q.push(y);
                    vis.set(y);
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        if(i == 1) hp.push((node){i, 0});
        else hp.push((node){i, 1e9});
    }
}
 
inline void A_star()
{
    while(!hp.empty())
    {
        node u = hp.top(); hp.pop();
        if(u.id == n)
        {
            E -= u.g;
            if(E < 0) return;
            ans++;
        }
        else
        {
            for(int p = lnk[u.id]; p; p = e[p].nxt)
            {
                int y = e[p].to;
                hp.push((node){y, u.g + e[p].v});
            }
        }
    }
}
 
int main()
{
    scanf("%d%d%lf", &n, &m, &E);
    int u, v; double w;
    for(register int i = 1; i <= m; ++i)
        scanf("%d%d%lf", &u,&v,&w), add(u, v, w, 1), add(v, u, w, 0);
    spfa();
    A_star();
    printf("%d\n", ans);
    return 0;
}

Problem 2 BZOJ1085

Solution

比较朴素的想法是直接对棋盘局面搜索，直到符合条件，这样会TLE。

定义估价函数为到达最终局面的最坏步数，这样答案一定不会更劣。

计算方法是，每当目前局面与最终局面有不同时计数器就++，如果计数器+当前步数超过了限定步数就不搜索。

Code

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 <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
 
using std::min;
using std::max;
using std::swap;
using std::memset;
 
char mtr[6][6];
int sts[6][6];
int standard[6][6]=
{
    {0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 1, 1},
    {0, 0, 1, 1, 1, 1},
    {0, 0, 0, 2, 1, 1},
    {0, 0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0, 0}
};
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
int ans, T, tagx, tagy, k;
bool sol;
 
bool jud(int matrix[6][6])
{
    for(int i = 1; i <= 5; ++i)
        for(int j = 1; j <= 5; ++j)
        {
            if(matrix[i][j] != standard[i][j]) return false;
        }
    return true;
}
bool g(int matrix[6][6], int now)
{
    int val = 0;
    for(int i = 1; i <= 5; ++i)
        for(int j = 1; j <= 5; ++j)
        {
            if(matrix[i][j] != standard[i][j]) {
                val++;
                if(val + now > k) return false;
            }
        }
    return true;
}
void A_star(int st, int matrix[6][6], int x, int y)
{
    if(st == k) {if(jud(matrix)) sol = true; return;}
    if(sol) return;
    for(int i = 0; i < 8; ++i)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || nx > 5 || ny < 1 || ny > 5) continue;
        swap(matrix[x][y], matrix[nx][ny]);
        if(g(matrix, st)) A_star(st + 1, matrix, nx, ny);
        swap(matrix[x][y], matrix[nx][ny]);
    }
}
 
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        sol = false;
        memset(sts, 0, sizeof sts);
        for(int i = 1; i <= 5; ++i)
        {
            scanf("%s", mtr[i] + 1);
            for(int j = 1; j <= 5; ++j)
            {
                if(mtr[i][j] == '*') sts[i][j] = 2, tagx = i, tagy = j;
                else if(mtr[i][j] == '0') sts[i][j] = 0;
                else sts[i][j] = 1;
            }
        }
        for(k = 1; k <= 15; ++k)
        {
            A_star(0, sts, tagx, tagy);
            if(sol){ printf("%d\n", k); break; }
        }
        if(!sol) puts("-1");
    }
    return 0;
}

Problem 3 BZOJ1598

$= BZOJ1975$

利用A*每次找到最优解的性质，依次记录答案，不足的-1补齐即可。

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
 
using std::min;
using std::max;
using std::swap;
using std::memset;
using std::bitset;
using std::queue;
using std::priority_queue;
 
const int maxn = 5002;
const int maxm = 10005;
const int maxp = 5e+6 + 5;
 
struct edge
{
    int to, nxt;
    int v;
}e[maxm], re[maxm];
int n, m, k;
int lnk[maxn], ptr, rlnk[maxn], rptr;
int dis[maxn], ans[105], num;
bitset<maxn> vis;
struct node
{
    int id;
    int g;
    bool operator < (const node &rhs) const
    {
        if(g + dis[id] == rhs.g + dis[rhs.id]) return g > rhs.g;
        return dis[id] + g > dis[rhs.id] + rhs.g;
    }
};
priority_queue<node> hp;
 
inline void add(int bgn, int end, int val, bool type)
{
    if(type)
    {
        e[++ptr] = (edge){end, lnk[bgn], val};
        lnk[bgn] = ptr;
    }
    else
    {
        re[++rptr] = (edge){end, rlnk[bgn], val};
        rlnk[bgn] = rptr;
    }
}
inline void spfa()
{
    //puts("spfa");
    queue<int> q;
    for(int i = 1; i <= n; ++i) dis[i] = 0x3f3f3f3f;
    dis[1] = 0; vis.set(1); q.push(1);
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis.reset(u);
        for(int p = rlnk[u]; p; p = re[p].nxt)
        {
            int y = re[p].to;
            if(dis[y] > dis[u] + re[p].v)
            {
                dis[y] = dis[u] + re[p].v;
                if(!vis.test(y))
                {
                    q.push(y);
                    vis.set(y);
                }
            }
        }
    }
}

int tim[maxn];
 
inline void A_star()
{
    //puts("start");
    hp.push((node){n, 0});
    while(!hp.empty())
    {
        node u = hp.top(); hp.pop();
        if(tim[u.id] >= k) continue;
        if(u.id == 1)
        {
            ans[tim[1]] = u.g;
        }
        tim[u.id]++;
        for(int p = lnk[u.id]; p; p = e[p].nxt)
        {
            int y = e[p].to;
            hp.push((node){y, u.g + e[p].v});
        }
    }
}
 
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    int u, v, w;
    for(register int i = 1; i <= m; ++i)
        scanf("%d%d%d", &u,&v,&w), add(u, v, w, 1), add(v, u, w, 0);
    //puts("GG");
    spfa();
    A_star();
    for(int i = 0; i < tim[1]; ++i) printf("%d\n", ans[i]);
    for(int i = tim[1]; i < k; ++i) puts("-1");
    return 0;
}