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}$ 的f(n)比较，取最小的一个。若在close表中，那就分成两种情况，第一种,close表中的该状态 $S_{0}$ 的f(n)大于S的，不做修改；第二种 $S_{0}$ 的f(n)小于S的,那就要需要将close表中 $S_{0}$ 的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)
{ 
   
    //1 up 2 down 3 left 4 right
    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){ 
   //not add
                    path[id] = Curid;
                    passLen[id] = passLen[Curid] + 1;
                    fitness[id] = evalute(tmp,target) + passLen[id];
                    statecpy(a,tmp,id++);
                }else{ 
   //add
                    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 start[N][N] = {4,0,5,1,2,3,7,8,6};

    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;
}

今天的文章八数码问题-A*(AStar)算法实现分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：http://bianchenghao.cn/13348.html

八数码问题-A*(AStar)算法实现

文章目录