文章目录
A*算法1 前言2 简介2.1 启发式函数 f(n) = g(n) + h(n)2.2 open表与close表的维护2.3 实例演示
3 八数码问题4 问题分析5 代码实现
A*算法
1 前言
\qquad
八数码问题可以说得上是搜索问题中比较经典的，可以有很多种搜索策略，比如说有最常见的BFS，DFS，此外，A也是一个比较普遍的搜索算法。在八数码问题A往往可以得到最优的求解路径。（再也不用担心不会拼图了，哈哈哈
2 简介
\qquad
可能还有很多没有对A很深的理解，以下是自己的一些小看法。
\qquad
A算法作为启发式搜索的一种，第一个必不可少是启发式函数；同时作为A*算法的比较显著的一个特点就是对open表和close表的维护.
2.1 启发式函数 f(n) = g(n) + h(n)
\qquad
启发式函数听起来很有学问，其实可以很简单的理解为从源点到目标的所需要消耗的总代价f(n)（和适应度函数比较相像），这个总代价可以分成两个部分从源点到中间节点（搜索的中间状态）已经消耗的实际代价g（n），另一个部分就是对从中间节点到目标的预测h(n)。
\qquad
通常来说，这里的代价一般是指各种距离，像欧式距离，曼哈顿距离等等，这个根据你所求解的实际问题决定。
\qquad
另一个值得指出的就是预测，预测值直接影响了问题求解的效率以及能否求得合理的解。这里给出一个结论：对于任意预测值h(n）均小于等于实际值的话，我们可以说最终解就是问题的最优解。
2.2 open表与close表的维护
open表：先可以简单认为是一个未搜索节点的表 close表：先可以简单认为是一个已完成搜索的节点的表（即已经将下一个状态放入open表内）
\qquad
为什么说是简单认为呢？理由很简单，因为open表与close表中的元素在一定规则下可以相互转化，最终实现搜到解。
\qquad
规则一：对于新添加的节点S（open表和close表中均没有这个状态），S直接添加到open表中
\qquad
规则二：对于已经添加的节点S（open表或者close表中已经有这个状态），若在open表中，与原来的状态
S
0
S_{0}
S0的f(n)比较，取最小的一个。若在close表中，那就分成两种情况，第一种,close表中的该状态
S
0
S_{0}
S0的f(n)大于S的，不做修改；第二种
S
0
S_{0}
S0的f(n)小于S的,那就要需要将close表中
S
0
S_{0}
S0的f(n)更新，同时将该状态移入到open表中。
\qquad
规则三：下一个搜索节点的选择问题，选取open表中f(n)的值最小的状态作为下一个待搜索节点
\qquad
规则四：每次需要将带搜索的节点下一个所有的状态按照规则一二更新open表,close表，搜索完该节点后，移到close表中。
2.3 实例演示
按照上述规则我们来体验一次简单的A*算法
A添加到open表中，更新A的f(n)为10 open 表 ：A(10) close表 ：null将B,C,D按照规则一添加到open表中，更新好B,C,D的f（n）后，将A移到close表中 open 表 ：B(13) C(18) D(20) close表 ：A(10)依据规则三，选取节点B作为下一个节点，同理将E,F移到open表，B移到close表 open 表 ：C(18) D(20) E(12) F(14) close表 ：A(10) B(13)依据规则三，选取E作为下一个节点，同理将G移到open表，E移到close表 open 表 ：C(18) D(20) F(14) G(15) close表 ：A(10) B(13) E(12)依据规则三，选取F作为下一个节点，按照规则二G(13) < G(15) 更新open表中的G。F移到close表 open 表 ：C(18) D(20) G(13) close表 ：A(10) B(13) E(12) F(14)继续搜索直至发现目标状态f（n）为open表中最小值
3 八数码问题
这里需要说明的A能找到的解是局部最优解，但是独特的启发式函数可以使得解为全局最优解，八数码问题就是一个能通过A求得最优解的问题。 像下图所示，通过将数字位向空格位移动直至将棋盘从初始状态变化到目标状态。
4 问题分析
启发式函数的确定 h(n):已经移动的步数 g(n):此状态与目标状态九宫格中相异数字的个数状态保存
\qquad
A*算法有个很大的问题就是消耗内存资源，我们可以用char型数据保存，这里我另一种保存策略：用一个long int数值表示，方法如下 0-8九个状态可以四位二进制数来表示0000B-1000B,所以九个状态就可以用36个二进制位来表示，然后这36位二进制数就可以用一个long int型数据来表示，这样增加编码和解码工作，不过操作很风骚，位运算很好实现，只是这是后来想到的，没有实现算法优化
\qquad
在找最小值的时候，我们可以用二分查找，o(n)优化到o(logn)，这就要求我们再插入时顺序插入，因为查询次数是要大于添加open\close表项的，所以这个方法是可以优化执行效率的无解情况
\qquad
将九宫格变成线性后，计算初始状态和目标状态的奇偶性是否一致，一致有解，否则无解。
5 代码实现
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#define maxState 10000
#define N 3
using namespace std
;
bool
isEqual(int a
[N
][N
][maxState
],int b
[N
][N
],int n
)
{
for(int i
= 0;i
< N
;i
++){
for(int j
= 0;j
< N
;j
++){
if(a
[i
][j
][n
] != b
[i
][j
]) return false
;
}
}
return true
;
}
bool
isEqual(int a
[N
][N
],int b
[N
][N
])
{
for(int i
= 0;i
< N
;i
++){
for(int j
= 0;j
< N
;j
++){
if(a
[i
][j
] != b
[i
][j
]) return false
;
}
}
return true
;
}
int evalute(int state
[N
][N
],int target
[N
][N
])
{
int num
= 0;
for(int i
= 0;i
< N
;i
++){
for(int j
= 0;j
< N
;j
++)
if(state
[i
][j
] != target
[i
][j
]) num
++;
}
return num
;
}
void findBrack(int a
[N
][N
],int x
,int y
)
{
for(int i
= 0;i
< N
;i
++){
for(int j
= 0;j
< N
;j
++){
if(a
[i
][j
] == 0) {
x
= i
;y
= j
;return;
}
}
}
}
bool
move(int a
[N
][N
],int b
[N
][N
],int dir
)
{
int x
= 0,y
= 0;
for(int i
= 0;i
< N
;i
++){
for(int j
= 0;j
< N
;j
++){
b
[i
][j
] = a
[i
][j
];
if(a
[i
][j
] == 0) {
x
= i
;y
= j
;
}
}
}
if(x
== 0 && dir
== 1) return false
;
if(x
== N
-1 && dir
== 2) return false
;
if(y
== 0 && dir
== 3) return false
;
if(y
== N
-1 && dir
== 4) return false
;
if(dir
== 1){b
[x
-1][y
] = 0;b
[x
][y
] = a
[x
-1][y
];}
else if(dir
== 2){b
[x
+1][y
] = 0;b
[x
][y
] = a
[x
+1][y
];}
else if(dir
== 3){b
[x
][y
-1] = 0;b
[x
][y
] = a
[x
][y
-1];}
else if(dir
== 4){b
[x
][y
+1] = 0;b
[x
][y
] = a
[x
][y
+1];}
else return false
;
return true
;
}
void statecpy(int a
[N
][N
][maxState
],int b
[N
][N
],int n
)
{
for(int i
= 0;i
< N
;i
++){
for(int j
= 0;j
< N
;j
++){
a
[i
][j
][n
] = b
[i
][j
];
}
}
}
void getState(int a
[N
][N
][maxState
],int b
[N
][N
],int n
)
{
for(int i
= 0;i
< N
;i
++){
for(int j
= 0;j
< N
;j
++){
b
[i
][j
] = a
[i
][j
][n
];
}
}
}
void statecpy(int a
[N
][N
],int b
[N
][N
])
{
for(int i
= 0;i
< N
;i
++){
for(int j
= 0;j
< N
;j
++)
a
[i
][j
] = b
[i
][j
];
}
}
int checkAdd(int a
[N
][N
][maxState
],int b
[N
][N
],int n
)
{
for(int i
= 0;i
< n
;i
++){
if(isEqual(a
,b
,i
)) return i
;
}
return -1;
}
int Astar(int a
[N
][N
][maxState
],int start
[N
][N
],int target
[N
][N
],int path
[maxState
])
{
bool visited
[maxState
] = {false
};
int fitness
[maxState
] = {0};
int passLen
[maxState
] = {0};
int curpos
[N
][N
];
statecpy(curpos
,start
);
int id
= 0,Curid
= 0;
fitness
[id
] = evalute(curpos
,target
);
statecpy(a
,start
,id
++);
while(!isEqual(curpos
,target
)){
for(int i
= 1;i
< 5;i
++){
int tmp
[N
][N
] = {0};
if(move(curpos
,tmp
,i
)){
int state
= checkAdd(a
,tmp
,id
);
if(state
== -1){
path
[id
] = Curid
;
passLen
[id
] = passLen
[Curid
] + 1;
fitness
[id
] = evalute(tmp
,target
) + passLen
[id
];
statecpy(a
,tmp
,id
++);
}else{
int len
= passLen
[Curid
] + 1,fit
= evalute(tmp
,target
) + len
;
if(fit
< fitness
[state
]){
path
[state
] = Curid
;
passLen
[state
] = len
;
fitness
[state
] = fit
;
visited
[state
] = false
;
}
}
}
}
visited
[Curid
] = true
;
int minCur
= -1;
for(int i
= 0;i
< id
;i
++)
if(!visited
[i
] && (minCur
== -1 || fitness
[i
] < fitness
[minCur
])) minCur
= i
;
Curid
= minCur
;
getState(a
,curpos
,Curid
);
if(id
== maxState
) return -1;
}
return Curid
;
}
void show(int a
[N
][N
][maxState
],int n
)
{
cout
<< "-------------------------------\n";
for(int i
= 0;i
< N
;i
++){
for(int j
=0;j
< N
;j
++){
cout
<< a
[i
][j
][n
] << " ";
}
cout
<< endl
;
}
cout
<< "-------------------------------\n";
}
int calDe(int a
[N
][N
])
{
int sum
= 0;
for(int i
= 0;i
< N
*N
;i
++){
for(int j
= i
+1;j
< N
*N
;j
++){
int m
,n
,c
,d
;
m
= i
/N
;n
= i
%N
;
c
= j
/N
;d
= j
%N
;
if(a
[c
][d
] == 0) continue;
if(a
[m
][n
] > a
[c
][d
]) sum
++;
}
}
return sum
;
}
void autoGenerate(int a
[N
][N
])
{
int maxMove
= 50;
srand((unsigned)time(NULL));
int tmp
[N
][N
];
while(maxMove
--){
int dir
= rand()%4 + 1;
if(move(a
,tmp
,dir
)) statecpy(a
,tmp
);
}
}
int main()
{
int a
[N
][N
][maxState
] = {0};
int start
[N
][N
] = {1,2,3,4,5,6,7,8,0};
autoGenerate(start
);
cout
<< start
[0][0] << start
[1][1];
int target
[N
][N
] = {1,2,3,4,5,6,7,8,0};
if(!(calDe(start
)%2 == calDe(target
)%2)){
cout
<< "无解\n";
return 0;
}
int path
[maxState
] = {0};
int res
= Astar(a
,start
,target
,path
);
if(res
== -1){
cout
<< "达到最大搜索能力\n";
return 0;
}
int shortest
[maxState
] = {0},j
= 0;
while(res
!= 0){
shortest
[j
++] = res
;
res
= path
[res
];
}
cout
<< "第 0 步\n";
show(a
,0);
for(int i
= j
- 1;i
>= 0;i
--){
cout
<< "第 " << j
-i
<< " 步\n";
show(a
,shortest
[i
]);
}
return 0;
}
