A*算法

A*（念做：A Star）算法是一種很常用的路徑查找和圖形遍歷算法，有較好的性能和準(zhǔn)確度。

可參考這篇文章，詳細(xì)的介紹了它與其他路徑查找算法的區(qū)別。
A* 算法的重點(diǎn)在于計(jì)算節(jié)點(diǎn)的優(yōu)先級(jí)函數(shù)f(n)=g(n)+h(n)。
f(n)是節(jié)點(diǎn)n的綜合優(yōu)先級(jí)。當(dāng)我們選擇下一個(gè)要遍歷的節(jié)點(diǎn)時(shí)，我們總會(huì)選取綜合優(yōu)先級(jí)最高（值最小）的節(jié)點(diǎn)。
g(n)是節(jié)點(diǎn)n距離起點(diǎn)的代價(jià)。
h(n)是節(jié)點(diǎn)n距離終點(diǎn)的預(yù)計(jì)代價(jià)，這也就是A* 算法的啟發(fā)函數(shù)。
只要充分理解并掌握這一點(diǎn)，應(yīng)用A* 算法也不在話下。

有向圖實(shí)現(xiàn)

首先參考一下迷宮地圖的A* 算法實(shí)現(xiàn)的詳細(xì)代碼，這套代碼精練簡(jiǎn)潔，很適合初學(xué)者學(xué)習(xí)。

A* 算法能在網(wǎng)格中找到最短路徑，同理也能應(yīng)用在有向圖上，尋找到代價(jià)最小的路徑，話不多說，直接上代碼。

定義有向圖節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)指向連接的節(jié)點(diǎn)作為該節(jié)點(diǎn)的子節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)的位置以二維平面上的橫縱坐標(biāo)標(biāo)識(shí)。

public class GNode {
    private double x; 
    private double y; 
    private String value;  //表示節(jié)點(diǎn)的值
    private double FValue = 0; //F值
    private double GValue = 0; //G值
    private double HValue = 0; //H值
    private List<GNode> CNode;//子節(jié)點(diǎn)
    private GNode PNode;   //父節(jié)點(diǎn)

    public GNode(int x, int y, String value) {
        super();
        this.x = x;
        this.y = y;
        this.value = value;
    }

    public double getX() {
        return x;
    }

    public void setX(double x) {
        this.x = x;
    }

    public double getY() {
        return y;
    }

    public void setY(double y) {
        this.y = y;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public double getFValue() {
        return FValue;
    }

    public void setFValue(double FValue) {
        this.FValue = FValue;
    }

    public double getGValue() {
        return GValue;
    }

    public void setGValue(double GValue) {
        this.GValue = GValue;
    }

    public double getHValue() {
        return HValue;
    }

    public void setHValue(double HValue) {
        this.HValue = HValue;
    }

    public List<GNode> getCNode() {
        return CNode;
    }

    public void setCNode(List<GNode> CNode) {
        this.CNode = CNode;
    }

    public GNode getPNode() {
        return PNode;
    }

    public void setPNode(GNode PNode) {
        this.PNode = PNode;
    }
}

定義有向圖數(shù)據(jù)結(jié)構(gòu)。

public class DGraph {
    private List<GNode> graph;//節(jié)點(diǎn)數(shù)組
    private GNode startNode;//起點(diǎn)
    private GNode endNode;//終點(diǎn)

    public DGraph(List<GNode> graph, GNode startNode, GNode endNode) {
        this.graph = graph;
        this.startNode = startNode;
        this.endNode = endNode;
    }

    //展示有向圖
    public void showGraph() {
        int vertexNum = graph.size();
        for (int i = 0; i < vertexNum; i++) {
            GNode v = graph.get(i);
            System.out.print(v.getValue() + "->");
            if (v.getCNode() != null) {
                for (int j = 0; j < v.getCNode().size(); j++) {
                    System.out.print(v.getCNode().get(j).getValue() + "->");
                }
            }
            System.out.println("/");
        }
    }

    public List<GNode> getGraph() {
        return graph;
    }

    public void setGraph(List<GNode> graph) {
        this.graph = graph;
    }

    public GNode getStartNode() {
        return startNode;
    }

    public void setStartNode(GNode startNode) {
        this.startNode = startNode;
    }

    public GNode getEndNode() {
        return endNode;
    }

    public void setEndNode(GNode endNode) {
        this.endNode = endNode;
    }
}

在主函數(shù)中初始化有向圖：

        List<GNode> gNodes = new ArrayList<>();
        GNode gNode1 = new GNode(1, 0, "A");
        GNode gNode2 = new GNode(2, 1, "B");
        GNode gNode3 = new GNode(3, 0, "C");
        GNode gNode4 = new GNode(4, 1, "D");
        GNode gNode5 = new GNode(5, 0, "E");

        gNode1.setCNode(Arrays.asList(gNode2, gNode3));
        gNode2.setCNode(Arrays.asList(gNode3));
        gNode3.setCNode(Arrays.asList(gNode4, gNode5));

        gNodes.add(gNode1);
        gNodes.add(gNode2);
        gNodes.add(gNode3);
        gNodes.add(gNode4);
        gNodes.add(gNode5);

        DGraph dGraph = new DGraph(gNodes, gNode1, gNode4);
        dGraph.showGraph();

運(yùn)行，以鄰接表格式展示有向圖。

鄰接表

A*算法實(shí)現(xiàn)，由于是在二維平面里尋找路徑，所以兩個(gè)節(jié)點(diǎn)的距離采用歐幾里得距離，也就是直線距離，估價(jià)函數(shù)h(n)為當(dāng)前節(jié)點(diǎn)和終點(diǎn)的直線距離，實(shí)際的距離一定是大于等于h值。

public class AStarGraph {
    /**
     * 使用ArrayList數(shù)組作為“開啟列表”和“關(guān)閉列表”
     */
    ArrayList<GNode> open = new ArrayList<>();
    ArrayList<GNode> close = new ArrayList<>();

    /**
     * 獲取兩個(gè)節(jié)點(diǎn)的歐幾里得距離
     */
    public double getDistance(GNode node1, GNode node2) {
        double dx = Math.abs(node1.getX() - node2.getX());
        double dy = Math.abs(node1.getY() - node2.getY());
        return Math.sqrt(dx * dx + dy * dy);
    }

    /**
     * 獲取H值,采用歐幾里得距離
     *
     * @param currentNode：當(dāng)前節(jié)點(diǎn)
     * @param endNode：終點(diǎn)
     * @return
     */
    public double getHValue(GNode currentNode, GNode endNode) {
        return getDistance(currentNode, endNode);
    }

    /**
     * 獲取G值
     *
     * @param currentNode：當(dāng)前節(jié)點(diǎn)
     * @return
     */
    public double getGValue(GNode currentNode) {
        if (currentNode.getPNode() != null) {
            return currentNode.getGValue() + getDistance(currentNode.getPNode(), currentNode);
        }
        return currentNode.getGValue();
    }

    /**
     * 獲取F值 ： G + H
     *
     * @param currentNode
     * @return
     */
    public double getFValue(GNode currentNode) {
        return currentNode.getGValue() + currentNode.getHValue();
    }

    /**
     * 將選中節(jié)點(diǎn)周圍的節(jié)點(diǎn)添加進(jìn)“開啟列表”
     *
     * @param node
     */
    public void inOpen(GNode node, DGraph graph) {
        if (node.getCNode() != null) {
            List<GNode> neighbours = node.getCNode();
            for (int i = 0; i < neighbours.size(); i++) {
                GNode m = neighbours.get(i);
                if (!open.contains(m)) {
                    m.setPNode(node);
                    m.setHValue(getHValue(m, graph.getEndNode()));
                    m.setGValue(getGValue(m));
                    m.setFValue(getFValue(m));
                    open.add(m);
                }
            }
        }
    }

    /**
     * 將節(jié)點(diǎn)添加進(jìn)”關(guān)閉列表“
     *
     * @param node
     * @param open
     */
    public void inClose(GNode node, ArrayList<GNode> open) {
        if (open.contains(node)) {
            open.remove(node);
            close.add(node);
        }
    }

    /**
     * 使用冒泡排序?qū)㈤_啟列表中的節(jié)點(diǎn)按F值從小到大排序
     *
     * @param arr
     */
    public void sort(ArrayList<GNode> arr) {
        for (int i = 0; i < arr.size() - 1; i++) {
            for (int j = i + 1; j < arr.size(); j++) {
                if (arr.get(i).getFValue() > arr.get(j).getFValue()) {
                    GNode tmp;
                    tmp = arr.get(i);
                    arr.set(i, arr.get(j));
                    arr.set(j, tmp);
                }
            }
        }
    }

    /**
     * 將路徑標(biāo)記出來
     *
     * @param arr
     * @param graph
     */
    public void showPath(ArrayList<GNode> arr, DGraph graph) {
        if (arr.size() > 0) {
            GNode node = graph.getEndNode();
            while (!(node.getX() == graph.getStartNode().getX() && node.getY() == graph.getStartNode().getY())) {
                System.out.print(node.getValue() + "->");
                node = node.getPNode();
            }
        }
        System.out.println(graph.getStartNode().getValue());
    }

    public void search(DGraph graph) {
        //對(duì)起點(diǎn)即起點(diǎn)周圍的節(jié)點(diǎn)進(jìn)行操作
        inOpen(graph.getStartNode(), graph);
        close.add(graph.getStartNode());
        graph.getStartNode().setPNode(graph.getStartNode().getPNode());
        sort(open);
        //重復(fù)步驟
        do {
            inOpen(open.get(0), graph);
            inClose(open.get(0), open);
            sort(open);
        }
        while (!open.contains(graph.getEndNode()));
        //知道開啟列表中包含終點(diǎn)時(shí)，循環(huán)退出
        inClose(graph.getEndNode(), open);
        showPath(close, graph);
    }
}

調(diào)用A*算法即可找到最短路徑。

AStarGraph aStarGraph = new AStarGraph();
aStarGraph.search(dGraph);

展示路徑