Astart算法之迷宫最短路径

1491204654

A-star算法描述：
A算法，启发式算法，A（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。

公式表示为： f(n)=g(n)+h(n),

其中 f(n) 是从初始状态经由状态n到目标状态的代价估计，

g(n) 是在状态空间中从初始状态到状态n的实际代价，

h(n) 是从状态n到目标状态的最佳路径的估计代价。

（对于路径搜索问题，状态就是图中的节点，代价就是距离）

这几篇博客对A启发式算法介绍的很详细 堪称最好的A*算法 启发式搜索技术A

之前就有了解过A算法解决八数码问题，也用过BFS广度优先搜索走迷宫，说说我对A算法的理解吧，A算法类似BFS，但是A算法的重点在于设计权重判断函数，选择最佳的走法，而且是有目标性的走，不像BFS是盲目的走法，例如在 9 * 9方格中，可以上下左右跟斜线行走，当然9 * 9的方格是正方形，所以横着走跟竖着走权重设为1，那么斜着走就是根号2，大概的比例是 1 : 1.414 ，约等于 10 ：14，那么 我们就可以选择这个权重来进行估值，每次选择权重最小的一个方向走。

Java代码实现
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class A {

class Node {
    int x, y;
    int g, h, f;
    Node parentNode;

    public Node() {
    }

    public int compareTo(Node node) {
        return this.f - node.f;
    }

    public Node(int x, int y, Node parentNode) {
        super();
        this.x = x;
        this.y = y;
        this.parentNode = parentNode;
    }

}

static List<Node> openList = new ArrayList<Node>();
static List<Node> closeList = new ArrayList<Node>();
static int COST_ROW, COST_COL, COST_X;
// 1为可通行，0为障碍物，不可通行
static int[][] map = new int[][] { 
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1 }, 
    { 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 }, 
    { 1, 1, 1, 1, 0, 0, 1, 1, 1, 1 }, 
    { 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 }, 
    { 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 },
    { 1, 1, 1, 1, 0, 0, 0, 0, 0, 1 }, 
    { 1, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };

public static void main(String[] args) {

    int row = map.length;
    int col = map[0].length;

    // 权重
    COST_ROW = 10;
    COST_COL = 10;
    COST_X = 14;

    boolean flag = astar(map, new A().new Node(4, 2, null), new A().new Node(4, col - 2, null), row, col);
    if(flag)
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.print("\n");
        }
    else
        System.out.println("Not Found");

}

static boolean astar(int[][] map, Node startNode, Node endNode, int row,
        int col) {
    Node curNode = startNode;
    // 将开始节点添加到搜索list
    openList.add(startNode);
    while (!openList.isEmpty() && !openList.contains(endNode)) {
        // 找到当前权值最小的节点
        curNode = findMinWeight(openList);
        // 找到最短路径
        if (curNode.x == endNode.x && curNode.y == endNode.y
                || openList.contains(endNode)) {
            while (!(curNode.x == startNode.x && curNode.y == startNode.y)) {
                map[curNode.x][curNode.y] = 2;
                if (curNode.parentNode != null) {
                    curNode = curNode.parentNode;
                }
            }
            map[startNode.x][startNode.y] = 2;
            return true;
        }


        // 上下左右
        if (curNode.y - 1 >= 0)
            check(curNode.x, curNode.y - 1, curNode, endNode, COST_COL);
        if (curNode.y + 1 < col)
            check(curNode.x, curNode.y + 1, curNode, endNode, COST_COL);
        if (curNode.x - 1 >= 0)
            check(curNode.x - 1, curNode.y, curNode, endNode, COST_ROW);
        if (curNode.x + 1 < row)
            check(curNode.x + 1, curNode.y, curNode, endNode, COST_ROW);

        // 斜
        if (curNode.x - 1 >= 0 && curNode.y - 1 >= 0)
            check(curNode.x - 1, curNode.y - 1, curNode, endNode, COST_X);
        if (curNode.x - 1 >= 0 && curNode.y + 1 < col)
            check(curNode.x - 1, curNode.y + 1, curNode, endNode, COST_X);
        if (curNode.x + 1 < row && curNode.y - 1 >= 0)
            check(curNode.x + 1, curNode.y - 1, curNode, endNode, COST_X);
        if (curNode.x + 1 < row && curNode.y + 1 < col)
            check(curNode.x + 1, curNode.y + 1, curNode, endNode, COST_X);

        openList.remove(curNode);
        closeList.add(curNode);
    }
    return false;
}

static boolean check(int x, int y, Node curNode, Node endNode, int cost) {
    Node node = new A().new Node(x, y, curNode);
    if (map[x][y] == 0) {
        closeList.add(node);
        return false;
    }

    if (isHave(closeList, x, y) != -1)
        return false;

    // 查找开启列表中是否存在
    int index = -1;
    if ((index = isHave(openList, x, y)) != -1) {// 存在
        // G值是否更小，是则更新
        if ((curNode.g + cost) < openList.get(index).g) {
             countG(node, cost);
             countF(node);
            openList.set(index, node);
        }
    } else {
        // 不存在，添加到开启列表中
        node.parentNode = curNode;
        count(node, endNode, cost);
        openList.add(node);
    }
    return true;
}

static void count(Node curNode, Node endNode, int cost) {
    countG(curNode, cost);
    countH(curNode, endNode);
    countF(curNode);
}

/**
 * 计算G消耗
 * @param curNode
 * @param endNode
 * @param cost
 */
static void countG(Node curNode, int cost) {
    if (curNode.parentNode == null)
        curNode.g = cost;
    else
        curNode.g = curNode.parentNode.g + cost;
}

/**
 * 计算H估值
 * @param curNode
 * @param endNode
 */
static void countH(Node curNode, Node endNode){
    curNode.h = (Math.abs(curNode.x - endNode.x)
            + Math.abs(curNode.y - endNode.y)) * COST_COL;
}

/**
 * 计算F权值
 * @param curNode
 */
static void countF(Node curNode) {
    curNode.f = curNode.g + curNode.h;
}

/**
 * 是否存在某个节点
 * 
 * @param list
 * @param x
 * @param y
 * @return
 */
static int isHave(List<Node> list, int x, int y) {
    int length = list.size();
    for (int i = 0; i < length; i++) {
        Node node = list.get(i);
        if (node.x == x && node.y == y)
            return i;
    }
    return -1;
}

/**
 * 找最小权值的节点
 * 
 * @param list
 * @return
 */
static Node findMinWeight(List<Node> list) {
    Iterator<Node> iterable = list.iterator();
    Node now = iterable.next();
    while (iterable.hasNext()) {
        Node next = iterable.next();
        if (next.compareTo(now) < 0)
            now = next;
    }
    return now;
}

}
运行结果
1 2 2 2 2 2 1 1 1 1
2 0 0 0 0 0 2 0 0 1
1 2 1 1 0 0 0 2 1 1
1 1 2 1 0 0 1 1 2 1
1 1 2 1 0 0 0 1 2 1
1 1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1
值为2的一条线路为最短路径