一種單目標(biāo)A*算法設(shè)計(jì)與實(shí)現(xiàn)

作者：吳屏珊

最近在學(xué)習(xí)簡(jiǎn)單的單目標(biāo)A*算法，其中在CSDN上閱讀到的一篇博文給了我很大啟發(fā)，于是在該博文的基礎(chǔ)上，筆者記錄了一點(diǎn)自己對(duì)于A*算法的體會(huì)和感悟。
原文鏈接

1. A*算法簡(jiǎn)單介紹

1.1 A*算法的基本要素

1、圖的說明：有一個(gè)8*8的地圖，其中綠色的點(diǎn)為起點(diǎn)，紅色的點(diǎn)為終點(diǎn)，黑色的點(diǎn)為障礙點(diǎn)（即不可達(dá)點(diǎn)），當(dāng)然邊界也是不可達(dá)點(diǎn)。

2、將要實(shí)現(xiàn)的目標(biāo)：從起點(diǎn)走到終點(diǎn)，其中要求所走距離最短并且要繞開所有不可達(dá)點(diǎn)。
3、移動(dòng)方向：每個(gè)點(diǎn)只有上，下，左，右四個(gè)方向可以行進(jìn)。

1.2 A*算法的中心思想

我們首先思考一個(gè)問題作為引入：既然每一個(gè)點(diǎn)有四種移動(dòng)方向，那如何判斷該點(diǎn)下一步的移動(dòng)方向呢，如何選出在該點(diǎn)下一步即將到達(dá)的所有點(diǎn)中選出最好的點(diǎn)呢？
（1）這里我們需要用到一個(gè)公式：F=G+H；其中F稱為代價(jià)，G為從起點(diǎn)到該點(diǎn)已走過的距離，H為從該點(diǎn)到終點(diǎn)將走的曼哈頓距離。
（2）曼哈頓距離：在地圖上我們忽略所有障礙點(diǎn)（不可達(dá)點(diǎn)），兩點(diǎn)的橫坐標(biāo)之差的絕對(duì)值與縱坐標(biāo)之差的絕對(duì)值之和即為兩點(diǎn)之間的曼哈頓距離，數(shù)學(xué)公式表示如下：\({|x_1-x_2|+|y_1-y_2|}\) ；代碼表示如下：Math.abs(x1-x2)+Math.abs(y1-y2)
（3）選取移動(dòng)方向的依據(jù)：F，每次移動(dòng)前，計(jì)算下一步可到達(dá)點(diǎn)的 F 值，然后對(duì)所有可到達(dá)點(diǎn)（不限于下一步）的 F 值進(jìn)行比較，優(yōu)先選取移動(dòng)代價(jià)最小即 F 值最小的點(diǎn)。

1.3 A*算法所需數(shù)據(jù)結(jié)構(gòu)

1.3.1 定義點(diǎn)Node的結(jié)構(gòu)

1、點(diǎn)的坐標(biāo)（x，y）
2、計(jì)算點(diǎn)的代價(jià)時(shí)所需數(shù)值：F，G，H
3、父節(jié)點(diǎn)：Father；父節(jié)點(diǎn)記錄的是該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)（即該節(jié)點(diǎn)是由哪個(gè)節(jié)點(diǎn)遍歷到的）。
? 父節(jié)點(diǎn)的作用：A*算法從起點(diǎn)開始尋路，當(dāng)找到終點(diǎn)的時(shí)候代表最短路徑已經(jīng)找到，這時(shí)我們可以利用終點(diǎn)結(jié)構(gòu)的Father來回溯到起點(diǎn)（起點(diǎn)的Father為NULL），從而找出并且輸出這條最短路徑。

1.3.2 記錄點(diǎn)狀態(tài)的幾個(gè)表

1、優(yōu)先隊(duì)列Open表：記錄由該點(diǎn)下一步可以到達(dá)的所有點(diǎn)，并且每次將F值最小的點(diǎn)放在隊(duì)首。
2、Close表：記錄所有已經(jīng)走過的點(diǎn)。
3、Exist表：記錄所有遍歷過的點(diǎn)（即在Open與Close中出現(xiàn)過的點(diǎn)）。
4、Close表與Exist表的區(qū)別：Close中存儲(chǔ)的點(diǎn)是已走過的點(diǎn)，Exist表中存儲(chǔ)的點(diǎn)是已遍歷過，但不一定走過的點(diǎn)。

2. A*算法步驟演示

Open表不為空且未找到終點(diǎn)時(shí)一直進(jìn)行循環(huán)

2.1 第一輪操作

首先我們將起點(diǎn)放入Open表中
在Open表中找到當(dāng)前F值最小的結(jié)點(diǎn)A，并將該點(diǎn)移出Open表，加入到Close表中。
遍歷該點(diǎn)A四周所有可到達(dá)節(jié)點(diǎn)，如果這些節(jié)點(diǎn)不包含在Exist表中（即未出現(xiàn)過），則計(jì)算它們的F值，并且根據(jù)F值大小順序加入到Open表中。
記錄這些點(diǎn)的父節(jié)點(diǎn)為該點(diǎn)A。

2.2 第二輪操作

在第一輪操作結(jié)束后的Open表中，將隊(duì)首節(jié)點(diǎn)（即F值最小的節(jié)點(diǎn)）移出Open表，加入到Close表中。
遍歷該點(diǎn)B四周所有可到達(dá)節(jié)點(diǎn)，如果這些節(jié)點(diǎn)不包含在Exist表中（即未出現(xiàn)過），則計(jì)算它們的F值，并且根據(jù)F值大小順序加入到Open表中。
（3,3）節(jié)點(diǎn)為障礙物，（3,1）節(jié)點(diǎn)已被Exist表包含，所以兩個(gè)點(diǎn)都不加入到Open表中。
記錄新加入這些點(diǎn)的父節(jié)點(diǎn)為該點(diǎn)B。

3. A*算法實(shí)現(xiàn)代碼

3.1 定義Node類

init_Node(Father,end)：傳入父節(jié)點(diǎn)和終點(diǎn)，并計(jì)算兩者間的曼哈頓距離，最終根據(jù)公式算出該點(diǎn)的F值。
compareTo(Node)：用于比較出F值最小的點(diǎn)

class Node implements Comparable<Node> {
    public int x;  //x坐標(biāo)
    public int y;  //y坐標(biāo)
    public int F;  //F屬性
    public int G;  //G屬性
    public int H;  //H屬性
    public Node Father;    //此結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)
    //獲取當(dāng)前結(jié)點(diǎn)的坐標(biāo)
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
    //通過結(jié)點(diǎn)的坐標(biāo)可以得到F， G， H三個(gè)屬性
    //需要傳入這個(gè)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)和最終的結(jié)點(diǎn)
    public void init_node(Node father, Node end) {//father是父節(jié)點(diǎn)
        this.Father = father;
        if (this.Father != null) {
            this.G = father.G + 1;
        } else { //父節(jié)點(diǎn)為空代表它是第一個(gè)結(jié)點(diǎn)
            this.G = 0;
        }
        //計(jì)算通過現(xiàn)在的結(jié)點(diǎn)的位置和最終結(jié)點(diǎn)的位置計(jì)算H值
        this.H = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
        this.F = this.G + this.H;
    }
    // 用來進(jìn)行和其他的Node類進(jìn)行比較
    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.F, o.F);
    }
}

3.2 Solution方法

is_exist方法：判斷是否在Exist表中出現(xiàn)過。

public boolean is_exist(Node node)
    {
        for (Node exist_node : Exist) {
            if (node.x == exist_node.x && node.y == exist_node.y) {
                return true;
            }
        }
        return false;
    }

is_valid方法：判斷是否合法（邊界，不可達(dá)點(diǎn)，已存在于Exist表中都為不合法）

public boolean is_valid(int x, int y) {
        // 如果結(jié)點(diǎn)的位置是-1，則不合法
        if (map[x][y] == -1) return false;
        for (Node node : Exist) {
            //如果結(jié)點(diǎn)出現(xiàn)過，不合法
//            if (node.x == x && node.y == y) {
//                return false;
//            }
            if (is_exist(new Node(x, y))) {
                return false;
            }
        }
        //以上情況都沒有則合法
        return true;
    }

extend_current_node方法：遍歷該點(diǎn)的上下左右四個(gè)方向，并判斷這些點(diǎn)是否合法。

public ArrayList<Node> extend_current_node(Node current_node) {
        int x = current_node.x;
        int y = current_node.y;
        ArrayList<Node> neighbour_node = new ArrayList<Node>();
        if (is_valid(x + 1, y))
        {
            Node node = new Node(x + 1, y);
            neighbour_node.add(node);
        }
        if (is_valid(x - 1, y))
        {
            Node node = new Node(x -1, y);
            neighbour_node.add(node);
        }
        if (is_valid(x, y + 1))
        {
            Node node = new Node(x, y + 1);
            neighbour_node.add(node);
        }
        if (is_valid(x, y - 1))
        {
            Node node = new Node(x, y - 1);
            neighbour_node.add(node);
        }
        return neighbour_node;
    }

astarSearch方法：A*算法具體實(shí)現(xiàn)方法。

public Node astarSearch(Node start, Node end) {
        //把第一個(gè)開始的結(jié)點(diǎn)加入到Open表中
        this.Open.add(start);
        //把出現(xiàn)過的結(jié)點(diǎn)加入到Exist表中
        this.Exist.add(start);
        //主循環(huán)
        while (Open.size() > 0) {
            //取優(yōu)先隊(duì)列頂部元素并且把這個(gè)元素從Open表中刪除
            Node current_node = Open.poll();
            //將這個(gè)結(jié)點(diǎn)加入到Close表中
            Close.add(current_node);
            //對(duì)當(dāng)前結(jié)點(diǎn)進(jìn)行擴(kuò)展，得到一個(gè)四周結(jié)點(diǎn)的數(shù)組
            ArrayList<Node> neighbour_node = extend_current_node(current_node);
            //對(duì)這個(gè)結(jié)點(diǎn)遍歷，看是否有目標(biāo)結(jié)點(diǎn)出現(xiàn)
            //沒有出現(xiàn)目標(biāo)結(jié)點(diǎn)再看是否出現(xiàn)過
            for (Node node : neighbour_node) {
                if (node.x == end.x && node.y == end.y) {//找到目標(biāo)結(jié)點(diǎn)就返回
                    node.init_node(current_node,end);
                    return node;//返回的是終止結(jié)點(diǎn)
                }
                if (!is_exist(node)) {  //沒出現(xiàn)過的結(jié)點(diǎn)加入到Open表中并且設(shè)置父節(jié)點(diǎn)
                    node.init_node(current_node, end);
                    Open.add(node);
                    Exist.add(node);
                }
            }
        }
        //如果遍歷完所有出現(xiàn)的結(jié)點(diǎn)都沒有找到最終的結(jié)點(diǎn)，返回null
        return null;
    }

3.3 main方法

繪制8*8地圖，并設(shè)置好起點(diǎn)和終點(diǎn)（原文直接在地圖中進(jìn)行起點(diǎn)終點(diǎn)的設(shè)置，修改起點(diǎn)和終點(diǎn)時(shí)相對(duì)麻煩，我在這里對(duì)原文進(jìn)行了改進(jìn)，在代碼中設(shè)置起點(diǎn)終點(diǎn)，測(cè)試不同種情況時(shí)相對(duì)便捷）。

int[][] map = {
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
                {-1,  0,  0,  0,  0,  0,  0,  0,  0, -1},
                {-1,  0,  0,  0,  0, -1,  0,  0,  0, -1},
                {-1,  0,  0,  0, -1,  0,  0,  0,  0, -1},
                {-1,  0,  0,  0, -1,  0,  0,  0,  0, -1},
                {-1,  0,  0,  0,  0, -1,  0,  0,  0, -1},
                {-1,  0,  0,  0, -1,  0,  0,  0,  0, -1},
                {-1,  0,  0,  0,  0, -1,  0,  0,  0, -1},
                {-1,  0,  0,  0,  0,  0,  0,  0,  0, -1},
                {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
        };
        Node start = new Node(4, 2);
        map[start.x][start.y]=1;
        start.Father = null;
        Node end = new Node(4, 7);
        map[end.x][end.y]=2;

調(diào)用Solution函數(shù)，拿到最短路徑

Solution solution = new Solution();
        Node res_node = solution.astarSearch(start, end);//res—node最先接收的是該地圖的終止
        while (res_node != null) {
            map[res_node.x][res_node.y] = res_node.G;
            res_node = res_node.Father;//迭代操作，從終止結(jié)點(diǎn)開始向后退，直到起點(diǎn)的父節(jié)點(diǎn)為null。循環(huán)終止
        }

輸出路徑，我在這里對(duì)輸出地圖進(jìn)行了一定程度上的渲染，紅色代表邊界和障礙不可達(dá)點(diǎn)，綠色代表起點(diǎn)和終點(diǎn)，藍(lán)色代表路徑，數(shù)字代表所走的步數(shù)（我在這里進(jìn)行了改進(jìn)，使輸出地圖更加直觀）。

//渲染迷宮
        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                Node nownode =new Node(i,j);
                if(map[i][j]==-1)
                    System.out.printf("\033[31m%3d\033[0m", map[i][j]);//red
                else if (equal_node(nownode,start) || equal_node(nownode,end))
                    System.out.printf("\033[32m%3d\033[0m", map[i][j]);//green
                else if(map[i][j]==0 && !equal_node(nownode,start))
                    System.out.printf("%3d", map[i][j]);//black
                else
                    System.out.printf("\033[34m%3d\033[0m", map[i][j]);//blue
            }
            System.out.println();
        }

3.4 輸出結(jié)果

源代碼已保存到課題組github文件夾

posted @ 2024-09-24 14:02 WUST許志偉閱讀(42) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部

cloud&ken

一種單目標(biāo)A*算法設(shè)計(jì)與實(shí)現(xiàn)

一種單目標(biāo)A*算法設(shè)計(jì)與實(shí)現(xiàn)

目錄

1. A*算法簡(jiǎn)單介紹

1.1 A*算法的基本要素

1.2 A*算法的中心思想

1.3 A*算法所需數(shù)據(jù)結(jié)構(gòu)

1.3.1 定義點(diǎn)Node的結(jié)構(gòu)

1.3.2 記錄點(diǎn)狀態(tài)的幾個(gè)表

2. A*算法步驟演示

2.1 第一輪操作

2.2 第二輪操作

3. A*算法實(shí)現(xiàn)代碼

3.1 定義Node類

3.2 Solution方法

3.3 main方法

3.4 輸出結(jié)果

公告