logo标签列表

有限网格中的路径规划

javarecursionpath-finding
3

我有一个 7x7 的网格（城市）。我想从起点 (x1, y1) 到达目的地 (x2, y2) 并将路径以多个由逗号分隔的 (x, y) 字符串的形式输出。我想使用递归来实现这一点，如果路径存在则输出 true，否则输出 false。
我该怎么做？我正在考虑编写四个检查四个方向的方法。任何意见都将不胜感激。

到目前为止，我只是实现了我的类的构造函数：

    map = new boolean[row][column];

    for(int i = 0; i < 7; i++)
    {
        for(int j = 0; j < 7; j++)
        { 
            map[i][j] = false; 
        }
    }
假设这个城市是一个迷宫类型的东西，你可以尝试使用这个算法：https://en.wikipedia.org/wiki/Maze_solving_algorithm - Nosrep
寻路实际上并不是一项试验性任务，但有许多不同的算法。其中之一是 A*，它是 Dijkstra's Algorithm 的变体。https://www.baeldung.com/java-a-star-pathfinding - Aman
2个回答
1
import java.io.PrintStream;

/**
 * Dev Parzival
 * Date : 27/10/2020 Time : 18:28
 * I have a confidence about my life that comes from standing tall on my own two feet.
 */

public class Path {
    static PrintStream out=System.out;
    static boolean pathfound=false;
    //////////Main/////////
    public static void main(String $[]){
        boolean arr[][]=new boolean[5][5];
        for(int i=0;i<arr.length;i++)
            for(int j=0;j<arr[0].length;j++) {
                if (i==0)
                    arr[i][j] = true;
                if(j==arr[0].length-1)
                    arr[i][j]=true;
            }
        travel(arr,0,0,arr.length-1,arr[0].length-1);
        if(pathfound)
            out.println("Path is found");
        else
            out.println("Path is not found");
    }
    
    static boolean travel(boolean a[][],int r,int c,int targetR,int targetC){
    //Target is found
    if(r==targetR && c==targetC){
        pathfound=true;
    }
    //South
    if(!pathfound && r+1<a.length)
        if(a[r+1][c]){
            a[r+1][c]=false;
            pathfound=travel(a,r+1,c,targetR,targetC);
        }
    //North
    if(!pathfound && r-1>=0)
        if(a[r-1][c]){
            a[r-1][c]=false;
            pathfound=travel(a,r-1,c,targetR,targetC);
        }
    //East
    if(!pathfound && c+1<a[0].length)
        if(a[r][c+1]){
            a[r][c+1]=false;
            pathfound=travel(a,r,c+1,targetR,targetC);
        }
    //West
    if(!pathfound && c-1>=0)
        if(a[r][c-1]){
            a[r][c-1]=false;
            pathfound=travel(a,r,c-1,targetR,targetC);
        }
        if(pathfound)
            out.println(r+" "+c);
        return pathfound;
    }
}

我建议复制原始数组，这样值就不会被修改。我已经测试过上面的代码可以正常工作。这种方法被称为“泛洪填充”。在图形中搜索更多关于“深度优先搜索”的信息。
在第一个for循环中，我正在设置路径。我选择了5x5矩阵，您可以根据需要给出任何大小。在travel函数中，第一个参数是网格，然后是起始行和列，之后是目标行和列。 - Udesh
非常感谢，我正在思考如果我要创建一个名为goSouthWest的方法，该方法仅通过递归解决向西南方向前进的问题，有任何想法都将不胜感激。 - Nzed
基本上，我旨在制作4种方法。goSouthWest，goSouthEast，goNorthWest，goNorthEast。这些方法中的每一个都可以通过一个名为givePath的方法访问，该方法基本上检查destRow或destCol是否小于、等于或大于startRow或startCol，并调用上述4种方法之一来解决问题。每个方法都以递归方式解决，并输出一个字符串，形式为**(x, y) (x, y) (x, y) ...**，其中(x, y)是路径的一步。 - Nzed
我猜你想从一个单元格向八个方向移动，包括北、南、东、西、东北、西北、东南和西南？ - Udesh
是的，这段代码基本上被分成了指令部分。 - Nzed
@Nzed，我已经修复了上面代码中的错误，并且为了实现对角线行进，我已经发布了我的源代码。希望能有所帮助。 - Udesh
0
import java.io.PrintStream;

/**
 * Dev Parzival
 * Date : 27/10/2020 Time : 18:28
 * I have a confidence about my life that comes from standing tall on my own two feet.
 */

public class Path {
    static PrintStream out=System.out;
    static boolean pathfound=false;
    //////////Main/////////
    public static void main(String $[]){
        boolean arr[][]=new boolean[5][5];
        for(int i=0;i<arr.length;i++)
            for(int j=0;j<arr[0].length;j++) {
                if (i==j)
                    arr[i][j] = true;
//                if(j==arr[0].length-1)
//                    arr[i][j]=true;
            }
        travel(arr,0,0,arr.length-1,arr[0].length-1);
        if(pathfound)
            out.println("Path is found");
        else
            out.println("Path is not found");
    }

    static boolean travel(boolean a[][],int r,int c,int targetR,int targetC){

        //Target is found
        if(r==targetR && c==targetC){
            pathfound=true;
        }
        //South
        if(!pathfound && r+1<a.length)
            if(a[r+1][c]){
                a[r+1][c]=false;
                pathfound=travel(a,r+1,c,targetR,targetC);
            }
        //North
        if(!pathfound && r-1>=0)
            if(a[r-1][c]){
                a[r-1][c]=false;
                pathfound=travel(a,r-1,c,targetR,targetC);
            }
        //East
        if(!pathfound && c+1<a[0].length)
            if(a[r][c+1]){
                a[r][c+1]=false;
                pathfound=travel(a,r,c+1,targetR,targetC);
            }
        //West
        if(!pathfound && c-1>=0)
            if(a[r][c-1]){
                a[r][c-1]=false;
                pathfound=travel(a,r,c-1,targetR,targetC);
            }
        //North-West
        if(!pathfound && c-1>=0 && r-1>=0)
            if(a[r-1][c-1]){
                a[r-1][c-1]=false;
                pathfound=travel(a,r-1,c-1,targetR,targetC);
            }
        //Noth-East
        if(!pathfound && c+1<a[0].length && r-1>=0)
            if(a[r-1][c+1]){
                a[r-1][c+1]=false;
                pathfound=travel(a,r-1,c+1,targetR,targetC);
            }
        //South-East
        if(!pathfound && c+1<a[0].length && r+1<a.length)
            if(a[r+1][c+1]){
                a[r+1][c+1]=false;
                pathfound=travel(a,r+1,c+1,targetR,targetC);
            }
        //South-West
        if(!pathfound && c-1>=0 && r+1<a.length)
            if(a[r+1][c-1]){
                a[r+1][c-1]=false;
                pathfound=travel(a,r+1,c-1,targetR,targetC);
            }
        //Print the cell position
        if(pathfound)
            out.println(r+" "+c);
        return pathfound;
    }
}

如果路径存在，上述代码将找到起始单元格和目标单元格之间的路径。

它生成的输出：

4 4
3 3
2 2
1 1
0 0
Path is found
除了水平和垂直搜索外，它还可以对角线搜索。 - Udesh
只是确认一下，你的对角线方向方法正确吗？比如“西南”，**[r+1][c-1]** 基本上是告诉我们向上移动一行，并向后退一列，这实际上就是“西北”。如果这是一个错误，那么在其他方法中也会出现。如果不是，请解释一下这里发生了什么？ - Nzed
假设你在单元格 [4,4]，目标在 [5,3]，那么 [r+1][c-1] 就是告诉你向下移动一行并向后退一列。 - Udesh
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接