Fork me on GitHub

A*学习笔记

例题:$LuoguP2324$:骑士精神

$A*$嘛,很早时候就听说过,貌似是一种很神奇的算法。
听长者讲过一遍,一直都想自己打一遍。但是一直没机会。
所以来自己写一遍就好啦。

$A*$的重点就是一个叫做估价函数的东西,但是这个叫估价函数的东西你必须要好好写,不然你会搜出来$WA$的好成绩
对于这道题,我就是将现在的棋盘和目标棋盘不同棋子数的差当作估价函数(其实是正确的)。
然后,我们就可以加一个类似于剪枝的东西:如果现在的步数$+$估价函数估计的值$>$现在的$max$,直接$return$就好。
剩下的东西就是个大爆搜了,

以下是代码:

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstring>
#include <algorithm>

const int goal[7][7] = {
{ 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 }
};

char mp[6][6];
int now[6][6];
bool flag;

int dx[] = { 0 , 1 , 1 , -1 , -1 , 2 , 2 , -2 , -2 };
int dy[] = { 0 , 2 , -2 , 2 , -2 , 1 , -1 , 1 , -1 };

inline int calcu () {
int tmp = 0;
for ( int i = 1 ; i <= 5 ; i++ )
for ( int j = 1 ; j <= 5 ; j++ ) {
if ( now[i][j] != goal[i][j] )
tmp++;
}
return tmp;
}
inline void swap ( int &x , int &y ) {
int t = x;
x = y;
y = t;
return;
}
void A_Star ( int x , int y , int dep , int MaxStep ) {
if ( flag )
return;
if ( dep == MaxStep ) {
if ( calcu () == 0 ) {
flag = 1;
printf ( "%d\n" , MaxStep );
return;
}
return;
}
for ( int i = 1 ; i <= 8 ; i++ ) {
int xx = x + dx[i];
int yy = y + dy[i];
if ( xx > 5 || xx < 1 || yy > 5 || yy < 1 )
continue;
swap ( now[x][y] , now[xx][yy] );
if ( calcu () + dep <= MaxStep )
A_Star ( xx , yy , dep + 1 , MaxStep );
swap ( now[x][y] , now[xx][yy] );
}
return;
}

int main ( void ) {
int ttt;
scanf ( "%d" , &ttt );
while ( ttt-- ) {
flag = 0;
for ( int i = 1 ; i <= 5 ; i++ )
scanf ( "%s" , mp[i] + 1 );
int st_x , st_y;
for ( int i = 1 ; i <= 5 ; i++ )
for ( int j = 1 ; j <= 5 ; j++ )
if ( mp[i][j] == '*' ) {
st_x = i;
st_y = j;
now[i][j] = 2;
}
else
now[i][j] = mp[i][j] - '0';
if ( calcu () == 0 ) {
puts ( "0" );
return 0;
}
for ( int i = 1 ; i <= 15 ; i++ )
if ( !flag )
A_Star ( st_x , st_y , 0 , i );
if ( !flag )
puts ( "-1" );
}
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:A*学习笔记

文章作者:KRrrrrrrrr

发布时间:2018年10月19日 - 11:10

最后更新:2019年10月21日 - 11:10

原始链接:http://krrrr.xyz/2018/10/19/A-学习笔记/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。