Java迷宫最短路径二维int数组

Question

我目前陷入一个项目中。 我的目标是使用 Dijkstra 算法。

我知道我从点 (0,0) 开始，查看起点旁边的两个节点，然后首先移动到最小的节点，然后查看周围的节点。我的迷宫是随机的，但为了方便开始，可以说以下是我的迷宫。

我将从 (0,0) 开始，并希望在 (9,9) 结束，这些数字是危险级别，我们的目标是最安全的路径，而不是最短的路径。

我需要推动才能理解如何设置它。 我知道我需要一个列表或一条路径来保持我所在的位置和我想要查看的位置。但我不知道如何在java中做到这一点。

import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class solver {

    /**
     * @param args
     */
    public static int[][]maze;
    public static int[][]openlist;
    public static int[][]closed;
    public static int[][]copy;
    public static int danger;
    public static int size=100;
    static int Max=9;
    static int Min=0;
    public static List path = new ArrayList();
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        maze = new int[size][size];
        openlist = new int[size][size];
        closed = new int[size][size];
        copy = new int[size][size];
        filler(maze);
        copy=dijstkra();
        printer(maze);
        //printer(copy);
        EDSfAO(maze,0,0);
        printer(openlist);
        printer(copy);
    }
    private static Boolean notwall(int i, int j){

        if((i>maze.length-1)||(j>maze.length-1)||(i<0)||(j<0))
        {return false;}

        return true;}
    private static int[][] dijstkra(){


        for(int i=0;i<maze.length;i++){
            for(int j=0;j<maze.length;j++){
                copy[i][j]=100000000;
            }}
        copy[0][0]=0;
        return copy;
        }

    private static void EDSfAO(int[][] maze,int i,int j){
        int min=100000000;
        int holdx = 0;  
        int holdy = 0;
        openlist[i][j]=1;
        danger=copy[i][j];
        if(i==maze.length-1&&j==maze.length-1){

            printer(copy);
            for(holdx=0;holdx<path.size();holdx++){

                System.out.print(path.get(holdx));

            }


        }
        else{
        if(notwall(i+1,j)&&openlist[i+1][j]!=1){
            copy[i+1][j]=danger+maze[i+1][j];
        } if(notwall(i,j+1)&&openlist[i][j+1]!=1){
            copy[i][j+1]=danger+maze[i][j+1];
        } if(notwall(i,j-1)&&openlist[i][j-1]!=1){
            copy[i][j-1]=danger+maze[i][j-1];
        } if(notwall(i-1,j)&&openlist[i-1][j]!=1){
            copy[i-1][j]=danger+maze[i-1][j];
        }
        for(int x=0;x<maze.length;x++){
            for(int y=0;y<maze.length;y++){

            if(openlist[x][y]!=1){

                if(min>copy[x][y]){
                min=copy[x][y];
                holdx=x;    
                holdy=y;
                }

            }


        }}
        moveToPosition(holdx,holdy);
        }
    }


    private static void moveToPosition(int x, int y) {

            openlist[x][y]=1;
            path.add("("+x+","+y+")");
            openlist[x][y]=1;
            EDSfAO(maze,x,y);
    }

private static void printer(int[][] maze) {
        // TODO Auto-generated method stub
    for(int i=0;i<maze.length;i++){
        for(int j=0;j<maze.length;j++){
        System.out.print("["+maze[i][j]+"]");                       
        }
        System.out.println();
        }

    }

public static void filler(int[][] maze){

        for(int i=0;i<maze.length;i++){

            for(int j=0;j<maze.length;j++){
            //If i=0 AND j=0 then maze[0][0]= 0(start) OR i= maze.length-1 AND j= maze.length-1 then maze[maze.length][maze.length]=0
            if((i==0 && j==0) || (i==maze.length-1 && j==maze.length-1)){

                maze[i][j]=0;   

            }else{
                maze[i][j]=Min + (int)(Math.random() * ((Max - Min) + 1));
            }
            }
            }
    }
}

迷宫没有墙壁相连，所有的盒子都是房间。 我一直在努力解决这个问题，而且我确实需要推动。 我看过很多关于 dijstkra 算法的视频，但我现在真的迷失了。

我添加了一个数组，我通过将节点设为 100000000 来保持其中的危险，但起始节点 (0,0) 为 0。

有人可以帮助我完成后续步骤吗？我知道这是作业，但我已经没时间了，真的需要一些指点。

更新：

好的，我已经可以正常工作了。它打印它所采用的路径，但如果它找到更好的路径，它会打印两者，有人可以帮助我解决这个问题。

如果我使用 100X100 元素，它也会崩溃，有人能告诉我为什么吗？ 这是最后一个真正的“编程作业”。正如您所料，这将涉及图表（有一些变化）；但当然，也会涉及一些问题的解决。 说明

---

想象一个“地下城游戏”，其中所有房间都布置在正方形环境中的完美网格中。每个房间都有一个生物，会造成一定程度的危险，范围从 0（无害）到 9（谨慎的做法是避免）。目标是找到一条从头到尾穿过地牢的路径，从而最大限度地减少总体危险。

每个房间，除非在边界处，仅存在于上、下、左、右方向（无对角线）。入口在左上角 (0,0)，出口在右下角 (n-1, n-1)。

以房间坐标路径的形式列出从开始到结束必须遍历的所有“房间”。

例如：

(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (3,3) (4,3) (4,4)

总危险 = 11 输入

输入文件将由 100 行 100 个数字（0-9）组成。 （是的，10,000 间房间已经很多了，但幸运的是，我们勇敢的旅行者每次出门都会带上去年节日礼物交换中收到的便携式计算机和一套适用于各种场合的电子数据集；它可能是重新赠送的。 )*

*对于此作业，您必须生成自己的测试数据。这就是我不参加这种聚会的原因... 输出

程序应将输出写入文件（采用上面所示的格式，包括“总危险”输出）。 谢谢。

UPDATE2：我在编码中发现了一个错误，

if(min>copy[x][y]){
                min=copy[x][y];
                holdx=x;    
                holdy=y;
                }

这将使它测试给定点上的每条路径，我的最短路径比其他路径大，我该如何解决这个问题？

我缺少什么？ 更新我完成了这篇文章，感谢您提供的帮助很少。

Answer 1

一旦您了解了如何使用 Dijkstra 算法，您就可以使用包含指示您之前位置的数字对的 ArrayList：

List<Point> path = new ArrayList<Point>();

然后您可以编写一个 Point 类来简单地包装两个 < code>int 基元、x 和 y。

因此，当您移动时，您可以使用：

private void moveToPosition(int x, int y) {
    path.add(new Point(x, y));

    // Move yourself to this point
    ...
}

至于学习如何实际使用算法，我认为这在某种程度上是您家庭作业的重点，我们不想破坏您的乐趣！

维基百科关于算法的文章相当有用，尽管我感觉你的课堂笔记也会有所帮助。

维基百科上的 Dijkstra 算法

Answer 2

我刚刚查看了关于 Dijkstra 算法 的维基百科文章。

1. 为每个节点分配一个暂定距离值：将初始节点设置为零，将所有其他节点设置为无穷大。
2. 将所有节点标记为未访问。将初始节点设置为当前节点。创建一组未访问过的节点，称为未访问集
   由除初始节点之外的所有节点组成。
3. 对于当前节点，考虑其所有未访问的邻居并计算它们的暂定距离。例如，如果当前
   节点A标记距离为6，与它连接的边
   邻居 B 的长度为 2，那么到 B（通过 A）的距离将是
   6+2=8。如果这个距离小于之前记录的距离，
   然后覆盖该距离。尽管邻居已经
   检查后，此时尚未将其标记为已访问，并且仍保留在
   未访问过的集合。
4. 当我们考虑完当前节点的所有邻居后，将当前节点标记为已访问并将其从
   未访问集。访问过的节点将永远不会被再次检查；它是
   现在记录的距离是最终的、最小的。
5. 如果未访问集为空，则停止。算法已经完成。
6. 将暂定距离最小的未访问节点设置为下一个“当前节点”，并返回步骤3。

一开始就天真地接近它。哎呀，把它当作“程序员的阅读理解”吧。在这种情况下，技巧是将二维数组映射到一组图节点。每个节点都需要“一个暂定距离值”。好吧，你的节点是由它们的 i,j 值定义的。做一些事情，这样你就可以在给定 i 和 j 的情况下获取/设置 tentative_distance_value 。

您需要标记节点是否被访问。同样的想法。

您需要一个“当前节点”。相同的想法，但更简单。

我知道我需要一个列表或路径来保存。我现在和过去都是我想要的
看。但我不知道如何在java中做到这一点。

从技术上讲，您不需要维护运行算法的路径。如果你不这样做，你就必须弄清楚如何根据算法的结果构建它，但这当然是可能的。

Answer 3

您的解决方案可以基于 Cormen、Leiserson、Rivest 和 Stein 所著的“算法简介”第二版中找到的算法。在第 24 章中，他们分析了“单源最短路径”算法，在 24.3 中，您有 Dijkstra。

我将在这里使用伪代码。您可以将下面的最小优先级队列替换为其他数据结构，例如 Java 中的映射。它不会很快，但会起作用，这可能是令人满意的第一次尝试。如果您愿意的话，我还有一个最小优先级队列的 Java 实现。

假设您有一个由二维数组表示的迷宫，如代码中所示：int[M][N] maze。第一个索引是行索引，第二个索引是列索引，从零开始。因此，行从 0 到 M-1，列从 0 到 N-1。值 maze[row][column] 表示与（行，列）处的房间相关的危险。我们需要一种方便的表示方法来获取迷宫中两个房间之间的权重，并了解哪些房间与特定房间相邻。

这个想法是压平数组并将每一行并排放置：row1、row2、...、rowM。然后我们可以给每个房间一个索引i。为了能够使用这个想法，我们需要在不同类型的坐标之间进行转换：（行，列）->我和我-> （行、列）。

convert_to_index(row, column) ::= row * N + column
convert_to_pair(i) ::= (i div N, i modulo N)

假设 SIZE 是 M*N，即迷宫中的房间总数。

现在我们可以用危险值制作一个代表迷宫的邻接矩阵：int[SIZE][SIZE] adjacency_matrix，第一个索引是FROM，第二个索引是TO。在单元格中，我们找到从一个房间到另一个房间的成本或重量。请注意，给定一个特定的房间，只有几个房间与该房间相邻。从该房间无法到达迷宫中的其他房间。按照惯例，我们将使用最大的整数来表示，并使用常量 INFINITY。其他值代表危险，范围从 0 到 9。矩阵将是稀疏的，并且有一些技术可以对其进行优化。

当我们有一个房间位于 (r, c) 时，与它相邻的房间是什么？我们希望有一个索引向量可以直接在我们的算法中使用。如果我们不考虑迷宫边界，我们有：(r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1) 、(r,c+1)、(r+1,c-1)、(r+1,c)和(r+1,c+1)。然后我们可以将 Convert_to_index 应用于每个，检查它们是否在 0..SIZE-1 范围内，并用它初始化矩阵。因此，例如，从 (r, c) 到 (r-1, c-1) 具有迷宫[r-1, c-1] 的成本或危险，并且从 (r-1, c-1) 到(r, c) 的成本为 maze[r, c]。但从 (r, c) 到另一个遥远的房间的成本为 10，它是不可到达的，反之亦然。

adjacent_rooms(r, c) ::=
    Given the vector [(r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1,c+1)]
    Filter it by deleting pairs whose row is not in 0..M-1 or whose column is not in 0..N-1
    Then apply the function convert_to_index to each resulting pair (map operation)
    Return the result

for i in 0..SIZE-1 loop
    for j in 0..SIZE-1 loop
        adjacency_matrix[i, j] := -1
    end loop
end loop

for i in 0..SIZE-1 loop
    (current_r, current_c) := convert_to_pair(i)
    adjacent_room_indexes := adjacent_rooms(current_r, current_c)
    for j in 0..SIZE-1 loop
        if adjacency_matrix[i, j] == -1 then
            (r, c) := convert_to_pair(j)
            if i == j then adjacency_matrix[i, j] := 0
            elsif j in adjacent_room_indexes then adjacency_matrix[i, j] := maze[r, c]; adjacency_matrix[j, i] := maze[current_r, current_c]
            else adjacency_matrix[i, j] := INFINITY
        end if
    end loop
end loop

接下来，我们需要最短路径估计的向量估计（参见书第 585 页）和前驱向量（参见书第 584 页）。

for i in 0..SIZE-1 loop
    predecessors[i] := NONE
    estimates[i] := INFINITY
end loop

从起始点到起始点的成本为 0。

estimates[0] := 0

初始化属于 MST（最小生成树）的顶点集

mst := empty set

最小优先级队列 q 已初始化

for i in 0..SIZE-1 loop
    q.add(i, estimates[i])
end loop

until q.empty? loop
    u, u_d = q.delete_min
    mst.add(u)
    (current_r, current_c) := convert_to_pair(i)
    adjacent_room_indexes := adjacent_rooms(current_r, current_c)
    for i in 0..adjacent_room_indexes.length-1 loop
        v := adjacent_room_indexes[i]
        cost = adjacency_matrix[u, v]
        if cost < q[v]
          predecessors[v] = u
          estimates[v] = c
          q[v] = c
        end
    end loop
end loop

作业已完成。我们在前辈中找到了我们的路径，在估计中找到了成本。

这可能有点过分了，A* 可能会更好。但我想使用 Dijkstra 是你作业的要求。如果你想探索 A*，我建议你看看 A* 初学者寻路 和 阿米特的 A* 页面。

Answer 4

我继续实现了 ccoakley 提到的算法。在下面找到部分代码，以帮助您找到正确的方向：

import java.util.HashSet;
import java.util.Set;

// 1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
// 2. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
// 3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
// 4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
// 5. If the unvisited set is empty, then stop. The algorithm has finished.
// 6. Set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.
public class Dijkstra {

    class Node {
        String name;
        Integer distance = Integer.MAX_VALUE;
        boolean visited;
        Set<Edge> edges = new HashSet<Edge>();

        Node(String name) {
            this.name = name;
        }

        Edge connect(Node destination, int length) {
            Edge edge = new Edge();
            edge.length = length;
            edge.from = this;
            edge.to = destination;
            edges.add(edge);
            destination.edges.add(edge);
            return edge;
        }

        @Override
        public String toString() {
            return name;
        }
    }

    class Edge {
        int length;
        Node from;
        Node to;

        Node getNeighbor(Node origin) {
            if (from == origin) {
                return to;
            }
            else if (to == origin) {
                return from;
            }
            else {
                throw new IllegalArgumentException("This edge is not connected to node " + origin);
            }

        }

        @Override
        public String toString() {
            return String.format("%s-%s", from, to);
        }
    }

    /**
     * <pre>
     * a - b - c
     * |   |   
     * d - e   |
     * |
     * f - g - h
     * </pre>
     * 
     * @return
     */
    private Set<Node> initialize() {
        Node a = new Node("a");
        Node b = new Node("b");
        Node c = new Node("c");
        Node d = new Node("d");
        Node e = new Node("e");
        Node f = new Node("f");
        Node g = new Node("g");
        Node h = new Node("h");

        a.connect(b, 4);
        a.connect(d, 8);
        b.connect(c, 6);
        b.connect(e, 1);
        c.connect(h, 7);
        d.connect(e, 2);
        d.connect(f, 5);
        f.connect(g, 3);
        g.connect(h, 1);

        a.distance = 0;

        Set<Node> unvisited = new HashSet<Dijkstra.Node>();
        unvisited.add(a);
        unvisited.add(b);
        unvisited.add(c);
        unvisited.add(d);
        unvisited.add(e);
        unvisited.add(f);
        unvisited.add(g);
        unvisited.add(h);

        return unvisited;
    }

    private Set<Node> solve(Set<Node> unvisited) {

        Set<Node> visited = new HashSet<Node>();

        while (!unvisited.isEmpty()) {

            System.out.println(String.format("Unvisited nodes:%s", unvisited.size()));
            print(unvisited);
            Node current = findNodeWithSmallestDistance(unvisited);
            System.out.println(String.format("Current node:%s", current));
            updateNeighbors(current);
            current.visited = true;
            unvisited.remove(current);
            visited.add(current);
        }

        return visited;
    }   

    private void updateNeighbors(Node current) {

        for (Edge edge : current.edges) {    
            Node neighbor = edge.getNeighbor(current);
            if (!neighbor.visited) {
                int tentativeNeighborDistance = current.distance + edge.length;
                if (tentativeNeighborDistance < neighbor.distance) {
                    neighbor.distance = tentativeNeighborDistance;
                    System.out.println(String.format("Neighbor:%s distance:%s", neighbor, neighbor.distance));
                }
                else {
                    System.out.println(String.format("Neighbor:%s no shorter path     found", neighbor));
                }
            }
            else {
                System.out.println(String.format("Neighbor:%s already visited",     neighbor));
            }
        }
    }

    private Node findNodeWithSmallestDistance(Set<Node> nodes) {
        Node smallest = null;
        for (Node node : nodes) {
            if (smallest == null || node.distance < smallest.distance) {
                smallest = node;
            }
        }
        return smallest;
    }

    private void print(Set<Node> visited) {
        for (Node node : visited) {
            System.out.println(String.format("Node:%s has distance:%s", node, node.distance));
        }
    }

    public static void main(String[] args) {
        Dijkstra edsger = new Dijkstra();
        Set<Node> unvisited = edsger.initialize();
        Set<Node> visited = edsger.solve(unvisited);
        edsger.print(visited);
    }
}

编辑：添加了缺失的位