二维矩阵迷宫中最便宜路径的寻路算法

Question

我必须找到矩阵成本最小的路径，并在 Java 中实现解决方案。我不确定哪种算法最能解决这个问题。

我有一个 MxN 矩阵，它可以在每个单元格中包含 0、1、2、3 或 4 作为输入，以及起始位置和目的地（例如：起始位置 (0, 0)和目的地 (5, 7)).

0 表示通过该单元格的成本为 1。

1 表示通过该单元格的成本为 2。

2 表示通过该单元格的成本为 3。

3 表示通过该单元格的成本为 4。

4表示有一堵墙，所以你不能穿过它。

你可以在任何方向上、下、左、右和垂直移动（但如果你垂直移动，通过任何单元格的成本都会翻倍）。

BFS 是一个好的算法还是它最适合二元迷宫？

Answer 1

多谢指教！我可以使用以下代码解决它（或者至少它对我有用）：

public class Pathfinder {
private static final int M = 5;
private static final int N = 5;
private static final int fila[] = {-1, 0, 0, 1, -1, -1, 1, 1};
private static final int columna[] = {0, -1, 1, 0, -1, 1, -1, 1};
private static boolean esValido(int matriz[][], boolean visitado[][], int fil, int col, int k) {
    if(k < 4)
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col]);
    else if (k == 4)
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col] && esValido(matriz, visitado, fil, col + 1, 0) && esValido(matriz, visitado, fil + 1, col, 0));
    else if (k == 5)
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col] && esValido(matriz, visitado, fil, col - 1, 0) && esValido(matriz, visitado, fil + 1, col, 0));
    else if (k == 6)
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col] && esValido(matriz, visitado, fil, col + 1, 0) && esValido(matriz, visitado, fil - 1, col, 0));
    else
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col] && esValido(matriz, visitado, fil, col - 1, 0) && esValido(matriz, visitado, fil - 1, col, 0));
}
private static int absoluto (int n) {
    return n > 0 ? n : -n;
}

public static void BFS(int matriz[][], int i, int j, int x, int y) {
    boolean [][] visitado = new boolean [M][N];
    PriorityQueue<Nodo> cola = new PriorityQueue<Nodo>();
    visitado[i][j] = true;
    cola.add(new Nodo(i, j, 0, absoluto(x - i) + absoluto(y - j)));
    int mincost = Integer.MAX_VALUE;
    int cost, aux;
    while(!cola.isEmpty()) {
        Nodo nodo = cola.poll();
        i = nodo.x;
        j = nodo.y;
        cost = nodo.cost;
        if(i == x && j == y) {
            mincost = cost;
            break;
        }
        for(int k = 0; k < 8; k++) {
            aux = 0;
            if(esValido(matriz, visitado, i + fila[k], j + columna[k], k)) {
                if(k < 4)
                    aux = 1;
                else
                    aux = 2;
                visitado[i + fila[k]][j + columna[k]] = true;
                switch(matriz[i + fila[k]][j + columna[k]]) {
                case 0:
                    cola.add(new Nodo(i + fila[k], j + columna[k], cost + aux, absoluto(x - i + fila[k]) + absoluto(y - j + columna[k])));
                case 1:
                    cola.add(new Nodo(i + fila[k], j + columna[k], cost + aux*2, absoluto(x - i + fila[k]) + absoluto(y - j + columna[k])));
                case 2:
                    cola.add(new Nodo(i + fila[k], j + columna[k], cost + aux*3, absoluto(x - i + fila[k]) + absoluto(y - j + columna[k])));
                case 3:
                    cola.add(new Nodo(i + fila[k], j + columna[k], cost + aux*4, absoluto(x - i + fila[k]) + absoluto(y - j + columna[k])));
                }   
            }
        }
    }

    if(mincost != Integer.MAX_VALUE)
        System.out.print("The path of minimum cost to the destination is " + mincost + ".");
    else
        System.out.print("Destination cannot be reached.");
}
}

我使用的节点结构如下：

public class Nodo implements Comparable<Nodo> {
public int x, y, cost, dist, total;
public Nodo(int x, int y, int cost, int dist){
    this.x = x;
    this.y = y;
    this.cost = cost;
    this.dist = dist;
    this.total = this.cost + this.dist;
}
public int compareTo(Nodo n) {
    if(this.total < n.total)
        return -1;
    else if(this.total > n.total)
        return 1;
    else
        return 0;
}
}

二维矩阵迷宫中最便宜路径的寻路算法

Pathfinding algorithm for cheapest path in 2d matrix maze

java

path-finding

maze