思路

  1. 最低成本
  2. BFS 廣度優先搜尋 Breadth-First Search (最佳解)

實作

測試方法

public static void main(String[] args) {

    Integer[][] maze = new Integer[][] {
            {1,3,1,2,9},
            {7,3,4,9,9},
            {1,7,5,5,3},
            {2,3,4,2,5},
    };

    Greedy_Maze_Cost_A gmc = new Greedy_Maze_Cost_A(maze);

    int row_start = 0; int col_start = 0; //起始位置
    int row_target = 3; int col_target = 4; //目標位置

    int cost_min = gmc.go_maze(row_start, col_start, row_target, col_target);

    System.out.println();
}

public class Greedy_Maze_Cost_A {

    Integer[][] maze;           // cost lookup table
    PriorityQueue<Node> pq;     // explored nodes (sort by cost)
    Integer[][] maze_best;      // unexplored nodes (null) + confirmed nodes


    // 節點初始化 row欄, col列, cost
    static class Node {
        Integer row;
        Integer col;
        Integer cost;

        public Node(Integer row, Integer col) {
            this.row = row;
            this.col = col;
        }
    }

    // 實作比較器
    static class MyComp implements Comparator<Node> {

        @Override
        public int compare(Node node1, Node node2) {
            return node1.cost.compareTo(node2.cost); // low -> high
        }
    }

    //初始化迷宮
    public Greedy_Maze_Cost_A(Integer[][] maze) {
        this.maze = maze; // 收進迷宮
        this.pq = new PriorityQueue<>(20, new MyComp()); // 使用 pq 做排序, 20 = 長度
        // new Integer[4][5] = 4欄5列
        this.maze_best = new Integer[this.maze.length][this.maze[0].length];
    }

具體

// 開頭迷宮
public int go_maze(int row_start, int col_start, int row_target, int col_target) {
    Node start = new Node(row_start, col_start); // 初始化節點
    start.cost = this.maze[row_start][col_start]; // 成本 this.maze[0][0]
    Node target = new Node(row_target, col_target); // 初始化目標節點

    return go_maze(start, target); //(0, 0), (3, 4)
}

public int go_maze(Node start, Node target) {

    /** initialization **/
    pq.add(start); // 加入到 pq (0, 0)

    while(true) {
        if (pq.size() == 0) break; // 執行完畢

        /** pick the node with lowest cost **/
        Node now = pq.poll(); // 取出 pq 最低值

        // 代表曾經有最低成本走過
        if (this.maze_best[now.row][now.col] != null) continue;

        /** confirm its min cost **/
        this.maze_best[now.row][now.col] = now.cost;

        /** explore next node **/
        if (now.row - 1 >= 0) { // 檢查往上沒有超界
            Node up = new Node(now.row - 1, now.col);
            up.cost = now.cost + this.maze[up.row][up.col]; //當前cost + 往上查找的 cost
            pq.add(up);
        }
        if (now.row + 1 < maze.length) { // 檢查往上沒有超界
            Node down = new Node(now.row + 1, now.col);
            down.cost = now.cost + this.maze[down.row][down.col];
            pq.add(down);
        }
        if (now.col - 1 >= 0) { //往左走一格沒有超界
            Node left = new Node(now.row, now.col - 1);
            left.cost = now.cost + this.maze[left.row][left.col];
            pq.add(left);
        }
        if (now.col + 1 < maze[0].length) { //往右沒有超界
            Node right = new Node(now.row, now.col + 1);
            right.cost = now.cost + this.maze[right.row][right.col];
            pq.add(right);
        }

    }

    return this.maze_best[target.row][target.col];
}