A*算法

2024-09-14 14:49:27 算法编辑:黎为乐

一、**A*算法介绍**

1. 公式:f(n)=g(n)+h(n)

f(n) 是从初始状态经由状态n到目标状态的代价估计，称作估计函数
d(n) 是在状态空间从初始状态到状态n的实际代价，称作节点深度
h(n) 是从状态n到目标状态的的估计代价，称作启发函数

2. 算法步骤

创建Open列表和Close列表，并初始化

起点加入Open列表中，设置起点优先级

While open!=NULL

node=选取优先级最高的节点

If node节点为终点

追踪父节点，一直到起点为止

结束程序

Else

将node节点删除，并加入Close列表

遍历node节点的所有邻近节点

If邻近节点在Close列表中，跳过

Else

设置邻近节点的父节点为node节点

计算节点优先级

将节点加入Open列表中

二、八数码问题

给定两个3*3矩阵，起始矩阵与目标矩阵

| 2 | 4 | 1 |
| - | - | - |
| 0 | 3 | 6 |
| 8 | 7 | 5 |

起始

目标

| 6 | 8 | 4 |
| - | - | - |
| 0 | 3 | 7 |
| 5 | 1 | 2 |

八数码问题，又称八皇后问题。即在大小为33的棋盘上，通过移动空棋盘附近棋子来改变棋盘状态。使其从起始状态到达目标状态。

有解条件

将初始状态和目标状态以从左到右从上到下的方式排列成一列。求目标状态和起始状态的这个排列的逆序数，如果两个排列的逆序数的奇偶性相同，则二者互为可达。即可以通过有限次移动将一种状态转换为另一种状态。

按上述例子来说

起始:241036875

2<4 2>1 2>0 2<3 2<6 2<8 2<7 2<5

4>1 4>0 4>3 4<6 4<8 4<7 4<5

1>0 1<3 1<6 1<8 1<7 1<5

0<3 0<6 0<8 0<7 0<5

3<6 3<8 3<7 3<5

6<8 6<7 6>5

8>7 8>5

7>5

共有10个逆序对，为偶

684037512

6<8 6>4 6>0 6>3 6<7 6>5 6>1 6>2

8>4 8>0 8>3 8>7 8>5 8>1 8>2

4>0 4>3 4<7 4<5 4>1 4>2

0<3 0<7 0<5 0<1 0<2

3<7 3<5 3<1 3<2

7>5 7>1 7>2

5>1 5>2

1<2

共有22个逆序对，为偶

三、JAVA完整代码

启发函数

当前节点与目标节点差异 count(node[i]!=node[j])

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.Scanner;

enum Move{

UP,DOWN,LEFT,RIGHT;
}

public class EightPuzzle implements Comparable{

private int[] num = new int[9];

private int f;

//估计函数f(n)**：从起始状态到目标的最小估计值

private int d; //d(n)**：当前的深度，即走到当前状态的步骤

private int h; //启发函数 h(n)：到目标的最小估计(记录和目标状态有多少个数不同)

private EightPuzzle parent; *//*当前状态的父状态

private ArrayList result = new ArrayList(); *//*保存最终路径

public int[] getNum() {

return num;
}

public void setNum(int[] num) {

this.num = num;
}

public int getD() {

return d;
}

public void setD(int d) {

this.d = d;
}

public int getEvaluation() {

return f;
}

public void setEvaluation(int evaluation) {

this.f = evaluation;
}

public int getH() {

return h;
}

public void setH(int h) {

this.h = h;
}

public EightPuzzle getParent() {

return parent;
}

public void setParent(EightPuzzle parent) {

this.parent = parent;
}

/**
** * 判断当前状态是否为目标状态

** @param*

target

** @return*

/
public boolean isTarget(EightPuzzle target){

return Arrays.equals(getNum(), target.getNum());
}

/**
** * 求估计函数**f(n) = g(n)+h(n);

** * 初始化状态信息

** @param*

target

public void init(EightPuzzle target){

int temp = 0;

for(int i=0;i<9;i++){

if(num[i]!=target.getNum()[i])

temp++; *//*记录当前节点与目标节点差异的度量

this.setH(temp);

if(this.getParent()==null){

this.setD(0); *//*初始化步数（深度）

}else{

this.d = this.parent.getD()+1;

*//*记录步数

this.setEvaluation(this.getD()+this.getH());

*//*返回当前状态的估计值

/**
** * 求逆序值并判断是否有解，逆序值同奇或者同偶才有解

** @param*

target

** @return*

*有解：*true *无解：*false

/
public boolean isSolvable(EightPuzzle target){

int reverse = 0;

for(int i=0;i<9;i++){

for(int j=0;j<i;j++){//遇到0**跳过

if(num[j]>num[i] && num[j]!=0 && num[i]!= 0)

 reverse++;

if(target.getNum()[j]>target.getNum()[i] && target.getNum()[j]!=0 && target.getNum()[i]!=0)

reverse++;

}
}

if(reverse % 2 == 0)

return true;
return false;
}

/**
** * *对每个子状态的**f(n)*进行由小到大排序

**

@Override

public int compareTo(Object o) {

EightPuzzle c = (EightPuzzle) o;

return this.f-c.getEvaluation();*//默认排序为f(n)*由小到大排序

/**

** @return * 返回0在八数码中的位置

public int getZeroPosition(){

int position = -1;

for(int i=0;i<9;i++){

if(this.num[i] == 0){

position = i;
}
}

return position;
}

/**
** * 去重，当前状态不重复返回*-1*

** @param * *open * 状态集合

** @return*

判断当前状态是否存在于open表中

public int isContains(ArrayList

open){

for(int i=0; i<open.size(); i++){

if(Arrays.equals(open.get(i).getNum(), getNum())){

return i;
}
}

return -1;
}

/**
** * 一维数组

** @return*

小于3（第一行）的不能上移返回**false

/
public boolean isMoveUp() {

int position = getZeroPosition();

if(position<=2){

return false;
}

return true;
}

/**

** @return * 大于6（第三行）返回**false

/
public boolean isMoveDown() {
int position = getZeroPosition();
if(position>=6){
return false;
}
return true;
}
/**
- - @return 0**，3，6（第一列）返回**false*
  - /
    public boolean isMoveLeft() {
    int position = getZeroPosition();
    if(position%3 == 0){
    return false;
    }
    return true;
    }
    /**
    - - @return 2**，5，8（第三列）不能右移返回**false*
      - /
        public boolean isMoveRight() {
        int position = getZeroPosition();
        if((position)%3 == 2){
        return false;
        }
        return true;
        }
        /**
        ** @param * move 0*：上，1：下，2：左，3：右*
        ** @return*
        返回移动后的状态
        *
        /
        public EightPuzzle move(Move move){
        EightPuzzle temp = new EightPuzzle();
        int[] tempnum = num.clone();
        temp.setNum(tempnum);
        int position = getZeroPosition();    //0**的位置
        int p=0;                            //与0**换位置的位置
        switch(move){
        case UP:
        p = position-3;
        temp.getNum()[position] = num[p];
        break;
        case DOWN:
        p = position+3;
        temp.getNum()[position] = num[p];
        break;
        case LEFT:
        p = position-1;
        temp.getNum()[position] = num[p];
        break;
        case RIGHT:
        p = position+1;
        temp.getNum()[position] = num[p];
        break;
        }
        temp.getNum()[p] = 0;
        return temp;
        }
        /**
        ** * 按照**33**格式输出*
        *
        /
        public void print(){
        for(int i=0;i<9;i++){
        if(i%3 == 2){
        System.out.println(this.num[i]);
        }else{
        System.out.print(this.num[i]+" ");
        }
        }
        }
        /**
        ** * 将最终答案路径保存下来并输出
        *
        /
        public void printRoute(){
        EightPuzzle temp = null;
        int count = 0;
        temp = this;
        System.out.println("----------开始移动----------");
        while(temp!=null){
        result.add(temp);
        temp = temp.getParent();
        count++;
        }
        for(int i = result.size()-1; i>=0 ; i--){
        result.get(i).print();
        System.out.println("--------------------");
        }
        System.out.println("最小移动步数："+(count-1));
        }
        /**
        ** @param * open open**表
        ** @param*
        close close**表
        ** @param*
        parent 父状态
        ** @param*
        target 目标状态
        *
        /
        public void operation(ArrayList
        open,ArrayList close,EightPuzzle parent,EightPuzzle target){
        if(this.isContains(close) == -1){//如果不在close**表中
        int position = this.isContains(open);//获取在open**表中的位置
        if(position!=-1 && this.getD()<open.get(position).getD())
        open.remove(position);
        this.parent = parent;*//*指明它的父状态
        this.init(target);*//*计算它的估计值
        open.add(this);//把它添加进open**表
        }
        }
        @SuppressWarnings("unchecked")
        public static void main(String args[]){
        //定义open**表
        ArrayList open = new ArrayList();
        ArrayList close = new ArrayList();
        EightPuzzle start = new EightPuzzle();
        EightPuzzle target = new EightPuzzle();
        //        int stnum[] = {8,6,7,2,5,4,3,0,1};
        //        int tanum[] = {6,4,7,8,5,0,3,2,1};
        Scanner s = new Scanner(System.in);
        int stnum[] = new int[9];
        int tanum[] = new int[9];
        System.out.println("请输入初始状态：");
        for(int i = 0; i< 9; i++){
        stnum[i] = s.nextInt();
        }
        System.out.println("请输入目标状态：");
        for(int j= 0; j< 9; j++){
        tanum[j] = s.nextInt();
        }
        s.close();
        start.setNum(stnum);
        target.setNum(tanum);
        long startTime=System.currentTimeMillis();
        if(start.isSolvable(target)){
        *//*初始化初始状态
        start.init(target);
        open.add(start);
        while(!open.isEmpty()){
        Collections.sort(open);            //按照evaluation**的值排序
        EightPuzzle best = open.get(0);    //从open表中取出最小估值的状态并移出open**表
        open.remove(0);
        close.add(best);
        if(best.isTarget(target)){
        *//**输出* best.printRoute(); long end=System.*currentTimeMillis*(); System.*out*.println((end-startTime) +" ms"); break;
        }
        Move move;
        //由best状态进行扩展并加入到open**表中
        *//0的位置上移之后状态不在close和open中设定best为其父状态，并初始化f(n)*估值函数
        if(best.isMoveUp()){
        *//*可以上移的话
        move = Move.*UP*;*//**上移标记* EightPuzzle up = best.move(move);*//best**的一个子状态* up.operation(open, close, best, target);
        }
        *//0的位置下移之后状态不在close和open中设定best为其父状态，并初始化f(n)*估值函数
        if(best.isMoveDown()){
        move = Move.*DOWN*; EightPuzzle down = best.move(move); down.operation(open, close, best, target);
        }
        *//0的位置左移之后状态不在close和open中设定best为其父状态，并初始化f(n)*估值函数
        if(best.isMoveLeft()){
        move = Move.*LEFT*; EightPuzzle left = best.move(move); left.operation(open, close, best, target);
        }
        *//0的位置右移之后状态不在close和open中设定best为其父状态，并初始化f(n)*估值函数
        if(best.isMoveRight()){
        move = Move.*RIGHT*; EightPuzzle right = best.move(move); right.operation(open, close, best, target);
        }
        }
        }else{
        System.out.println("目标状态不可达");
        }
        }
        }
        四、运行结果
        请输入初始状态：
        2
        4
        1
        0
        3
        6
        8
        7
        5
        请输入目标状态：
        6
        8
        4
        0
        3
        7
        5
        1
        2
        ----------开始移动----------
        2 4 1
        0 3 6
        8 7 5
        2 4 1
        8 3 6
        0 7 5
        2 4 1
        8 3 6
        7 0 5
        2 4 1
        8 0 6
        7 3 5
        2 4 1
        8 6 0
        7 3 5
        2 4 0
        8 6 1
        7 3 5
        2 0 4
        8 6 1
        7 3 5
        0 2 4
        8 6 1
        7 3 5
        8 2 4
        0 6 1
        7 3 5
        8 2 4
        6 0 1
        7 3 5
        8 0 4
        6 2 1
        7 3 5
        0 8 4
        6 2 1
        7 3 5
        6 8 4
        0 2 1
        7 3 5
        6 8 4
        7 2 1
        0 3 5
        6 8 4
        7 2 1
        3 0 5
        6 8 4
        7 2 1
        3 5 0
        6 8 4
        7 2 0
        3 5 1
        6 8 4
        7 0 2
        3 5 1
        6 8 4
        0 7 2
        3 5 1
        6 8 4
        3 7 2
        0 5 1
        6 8 4
        3 7 2
        5 0 1
        6 8 4
        3 7 2
        5 1 0
        6 8 4
        3 7 0
        5 1 2
        6 8 4
        3 0 7
        5 1 2
        6 8 4
        0 3 7
        5 1 2
        最小移动步数：24
        6745 ms
        进程已结束,退出代码0
        五、搜索树绘制
        六、代码解读
        创建EightPuzzle类，初始化类变量及其起止与目标数组，并生成setter和getter方法及其移动枚举
        2.用户输入并初始化起始数组与目标数组。
        3.判断两个二维数组展平后的逆序数奇偶性是否一致。
        if(start.isSolvable(target))
        isSolvable暴力实现
        如果为False，输出目标不可达，程序结束。
        初始化start对象，设置start对象的目标对象target，将start对象放入open队列中。
        循环判断直到open队列为空（即搜索树全部搜索完毕）
        ----------------------------------------------------------------循环----------------------------------------------------------
        排序open表，按照f(n)估计值来由小到大排序
        从open表取出第一个对象，类似队列的出队。并将此对象放入close列表中，表示已经遍历过（剪枝操作）
        判断该对象是否为目标状态，如果是，打印并结束程序
        如果不是判断是否可以上下左右移动，非跳过，是则做对应的移动操作
        判断该移动是否在Close表已经存在，如果存在则跳过
        如果不在Close表，则查询Open表，如果Open表内存在，比对两个状态的深度，取深度小的替换到open表，如果不在Open表中，则添加该状态到Open表中
        直至状态相同，跳出循环
        七、更换启发函数
        1.曼哈顿距离+差异值度量
        因为状态只能上下左右移动，我在之前的基础上添加了曼哈顿距离（Manhattan distance）作为启发函数
        public int getIntIndex(int[] nums, int key) {
        for (int i = 0; i < nums.length; i++) {
        if (nums[i] == key) {
        return i;
        }
        }
        return -1;
        }
        public int distance (int value1,int value2){
        int v1_r=value1/3;
        int v2_r=value2/3;
        int v1_c=value1%3;
        int v2_c=value2%3;
        return Math.abs(v1_r-v2_r)+Math.abs(v1_c-v2_c);
        }
        int tar=getIntIndex(target.getNum(),0);
        int loc=getIntIndex(num,0);
        temp+=distance(tar,loc);
        for(int i=0;i<9;i++){
        if(num[i]!=target.getNum()[i])
        temp++;            *//*记录当前节点与目标节点差异的度量
        }
        ----------开始移动----------
        2 4 1
        0 3 6
        8 7 5
        2 4 1
        8 3 6
        0 7 5
        2 4 1
        8 3 6
        7 0 5
        2 4 1
        8 0 6
        7 3 5
        2 4 1
        8 6 0
        7 3 5
        2 4 0
        8 6 1
        7 3 5
        2 0 4
        8 6 1
        7 3 5
        2 6 4
        8 0 1
        7 3 5
        2 6 4
        0 8 1
        7 3 5
        0 6 4
        2 8 1
        7 3 5
        6 0 4
        2 8 1
        7 3 5
        6 8 4
        2 0 1
        7 3 5
        6 8 4
        0 2 1
        7 3 5
        6 8 4
        7 2 1
        0 3 5
        6 8 4
        7 2 1
        3 0 5
        6 8 4
        7 2 1
        3 5 0
        6 8 4
        7 2 0
        3 5 1
        6 8 4
        7 0 2
        3 5 1
        6 8 4
        0 7 2
        3 5 1
        6 8 4
        3 7 2
        0 5 1
        6 8 4
        3 7 2
        5 0 1
        6 8 4
        3 7 2
        5 1 0
        6 8 4
        3 7 0
        5 1 2
        6 8 4
        3 0 7
        5 1 2
        6 8 4
        0 3 7
        5 1 2
        最小移动步数：24
        16204 ms
        2. 差异值
        for(int i=0;i<9;i++){
        if(num[i]!=target.getNum()[i])
        temp+=Math.abs(num[i]-target.getNum()[i]);            *//*记录当前节点与目标节点差异
        }
        ----------开始移动----------
        2 4 1
        0 3 6
        8 7 5
        2 4 1
        3 0 6
        8 7 5
        2 4 1
        3 6 0
        8 7 5
        2 4 0
        3 6 1
        8 7 5
        2 0 4
        3 6 1
        8 7 5
        2 6 4
        3 0 1
        8 7 5
        2 6 4
        3 1 0
        8 7 5
        2 6 4
        3 1 5
        8 7 0
        2 6 4
        3 1 5
        8 0 7
        2 6 4
        3 1 5
        0 8 7
        2 6 4
        0 1 5
        3 8 7
        2 6 4
        1 0 5
        3 8 7
        2 6 4
        1 8 5
        3 0 7
        2 6 4
        1 8 5
        0 3 7
        2 6 4
        0 8 5
        1 3 7
        0 6 4
        2 8 5
        1 3 7
        6 0 4
        2 8 5
        1 3 7
        6 8 4
        2 0 5
        1 3 7
        6 8 4
        0 2 5
        1 3 7
        6 8 4
        1 2 5
        0 3 7
        6 8 4
        1 2 5
        3 0 7
        6 8 4
        1 0 5
        3 2 7
        6 8 4
        1 5 0
        3 2 7
        6 8 4
        1 5 7
        3 2 0
        6 8 4
        1 5 7
        3 0 2
        6 8 4
        1 0 7
        3 5 2
        6 8 4
        0 1 7
        3 5 2
        6 8 4
        3 1 7
        0 5 2
        6 8 4
        3 1 7
        5 0 2
        6 8 4
        3 0 7
        5 1 2
        6 8 4
        0 3 7
        5 1 2
        最小移动步数：30
        592 ms
        3. 差异值度量+差异值
        for(int i=0;i<9;i++){
        if(num[i]!=target.getNum()[i])
        temp+=Math.abs(num[i]-target.getNum()[i])+1;
        }
        ----------开始移动----------
        2 4 1
        0 3 6
        8 7 5
        2 4 1
        3 0 6
        8 7 5
        2 4 1
        3 6 0
        8 7 5
        2 4 0
        3 6 1
        8 7 5
        2 0 4
        3 6 1
        8 7 5
        2 6 4
        3 0 1
        8 7 5
        2 6 4
        0 3 1
        8 7 5
        2 6 4
        8 3 1
        0 7 5
        2 6 4
        8 3 1
        7 0 5
        2 6 4
        8 0 1
        7 3 5
        2 6 4
        0 8 1
        7 3 5
        0 6 4
        2 8 1
        7 3 5
        6 0 4
        2 8 1
        7 3 5
        6 8 4
        2 0 1
        7 3 5
        6 8 4
        0 2 1
        7 3 5
        6 8 4
        7 2 1
        0 3 5
        6 8 4
        7 2 1
        3 0 5
        6 8 4
        7 2 1
        3 5 0
        6 8 4
        7 2 0
        3 5 1
        6 8 4
        7 0 2
        3 5 1
        6 8 4
        0 7 2
        3 5 1
        6 8 4
        3 7 2
        0 5 1
        6 8 4
        3 7 2
        5 0 1
        6 8 4
        3 7 2
        5 1 0
        6 8 4
        3 7 0
        5 1 2
        6 8 4
        3 0 7
        5 1 2
        6 8 4
        0 3 7
        5 1 2
        最小移动步数：26
        28 ms
        对比
        执行用时(ms) 移动步数
        差异值度量 6745 24
        曼哈顿距离+差异值度量 16204 24
        差异值 592 30
        差异值度量+差异值 28 26
        按着差异值+差异值度量直接计算，综合来看执行用时最快，但结果不一定最佳。曼哈顿+差异值的度量执行用时很慢，结果与差异值度量差不多。
        八、总结
        从该次实验得知，不同的启发函数对算法的用时影响巨大。A算法作为启发式搜索，可以根据每一步的结果来决定下一步的走向，在通常情况下能够很容易找到目标结果。这次的最短路径问题,与之前所学的宽度优先搜索紧密结合，让我对算法方面的学习有更深的体会和理解。