depth-first-search - Java：随机化 DFS 运行以构建迷宫的麻烦

Question

我在随机访问从一个节点到它的邻居时遇到了麻烦，很少访问整个图（一个 MxN 数组，在这个测试 4x4 中），我不明白我在这里做错了什么。

import java.util.ArrayList;



class IJ {

    int i;
    int j;

    IJ (int i,int j){
        i = this.i;
        j= this.j;

    }

}


class Graph {

    int M;
    int N;

    int adjacencyMatrix[][];

    ArrayList <IJ> orderOfVisits;

    Graph(int M,int N){

        this.M=M;
        this.N=N;
        adjacencyMatrix=new int[M][N];

        for (int i=0; i<M; i++)
            for (int j=0;j<N;j++){
                    adjacencyMatrix[i][j]=-1; //mark all vertices as not visited
            }

        orderOfVisits = new ArrayList<IJ>();

    }

 String northOrEast () {

        double lottery = Math.random();

        if (lottery>0.5D) {return "north";}

        else {return "south";}


    }

 String southOrEastOrNorth() {

     double lottery=Math.random();

     if (lottery<=0.33D){
        return "south";
     }

     else if ((lottery > 0.33D) && (lottery <= 0.66D)) {
        return "east";
     }

     else if(lottery > 0.66D)
     {
        return "north";
     }

     System.out.println("method sEn has returned null ");
     return null;
 }


 String southOrEast(){

  double lottery = Math.random();

        if (lottery>0.5D) {return "south";}

        else {return "east";}


 }

String southOrEastOrWest() {

     double lottery=Math.random();

     if (lottery<=0.33D){
        return "south";
     }

     else if ((lottery > 0.33D) && (lottery <= 0.66D)) {
        return "east";
     }

     else if(lottery > 0.66D)
     {
        return "west";
     }

     System.out.println("method sEw has returned null ");
     return null;

}

String southOrWest(){

  double lottery = Math.random();

        if (lottery>0.5D) {return "south";}

        else {return "west";}


 }

String southOrNorthOrWest() {

     double lottery=Math.random();

     if (lottery<=0.33D){
        return "south";
     }

     else if ((lottery > 0.33D) && (lottery <= 0.66D)) {
        return "north";
     }

     else if(lottery > 0.66D)
     {
        return "west";
     }

     System.out.println("method sNw has returned null ");
     return null;

}

String northOrWest(){

  double lottery = Math.random();

        if (lottery>0.5D) {return "north";}

        else {return "west";}


 }

String eastOrNorthOrWest() {

     double lottery=Math.random();

     if (lottery<=0.33D){
        return "east";
     }

     else if ((lottery > 0.33D) && (lottery <= 0.66D)) {
        return "north";
     }

     else if(lottery > 0.66D)
     {
        return "west";
     }

     System.out.println("method eNw has returned null ");
     return null;

}

String any() {

     double lottery=Math.random();

     if (lottery<=0.25D){
        return "east";
     }

     else if ((lottery > 0.25D) && (lottery <= 0.50D)) {
        return "north";
     }

     else if ((lottery > 0.5D) && (lottery <= 0.75D)) {
        return "south";
     }

     else if(lottery > 0.75D)
     {
        return "west";
     }

     System.out.println("method any has returned null ");
     return null;

}



 String goWhere (boolean northValid, boolean southValid, boolean eastValid, boolean westValid, int i, int j){

   //border cases

     //left lower corner, only north and east are valid
     if ((northValid==true) && (southValid==false) &&(eastValid==true) && (westValid==false))
     {return northOrEast();}

      //left border:
     if ((northValid==true) && (southValid==true) && (eastValid==true) && (westValid==false))
     {return southOrEastOrNorth();}

     //upper left corner, only south and east are valid
     if ((northValid==false) && (southValid==true) && (eastValid==true) && (westValid==false))
     {return southOrEast();}


      //upper border
     if ((northValid==false) && (southValid==true) && (eastValid==true) && (westValid==true))
     {return southOrEastOrWest();}

      //upper right corner
     if ((northValid==false) && (southValid==true) && (eastValid==false) && (westValid==true))
     {return southOrWest();}

     //right border
     if ((northValid==true) && (southValid==true) && (eastValid==false) && (westValid==true))
     {return southOrNorthOrWest();}

     //lower right corner
     if ((northValid==true) && (southValid==false) && (eastValid==false) && (westValid==true))
     {return northOrWest();}

     //bottom border
     if ((northValid==true) && (southValid==false) && (eastValid==true) && (westValid==true))
     {return eastOrNorthOrWest();}

     //middle
     if ((northValid==true) && (southValid==true) && (eastValid==true) && (westValid==true))
     {return any();}


    System.out.println("go where a llegado a retornar null");
    return null;

 }


 void DFS(int i, int j){ // i,j identifies the vertex

     boolean northValid= false;
     boolean southValid= false;
     boolean eastValid = false;
     boolean westValid = false;


     int iNorth, jNorth;
     int iSouth, jSouth;
     int iEast, jEast;
     int iWest, jWest;

     iNorth=i-1;
     if (!(iNorth<0)) northValid=true;

     iSouth=i+1;
     if(!((iSouth)>=M)) southValid=true;

     jEast=j+1;
     if(!((jEast)>=N)) eastValid=true;

     jWest= j-1;
     if (!(jWest<0)) westValid=true;



    if (adjacencyMatrix[i][j]==-1){ //if the vertex is unvisited

        adjacencyMatrix[i][j]=0; //mark the vertex as visited
        IJ ij = new IJ(i,j);
        orderOfVisits.add(ij); //add the vertex to the visit list
        System.out.println("Visit i,j: " + i +" " +j);






//boolean wentNorth = false;
//boolean wentSouth=false;
//boolean wentEast = false;
//boolean wentWest = false;

     //  if (where!=null)
       for (int rows=i; rows<M; rows++)
           for (int cols=j; cols<N; cols++){

         //normal DFS

            String where = goWhere(northValid, southValid, eastValid, westValid, i,j);

            if (where.equals("north"))
            {
                DFS(iNorth,j);
                //wentNorth=true;
            }



            if (where.equals("south")){
                DFS(iSouth,j);
            }

            if(where.equals("east")){
                DFS(i, jEast);
            }

            if (where.equals("west")){
                DFS(i,jWest);
            }


//            if(northValid)
//            {
//                DFS(iNorth,j);
//            }
//
//            if(southValid){
//                DFS(iSouth,j);
//            }
//
//            if(eastValid){
//                DFS(i, jEast);
//            }
//
//            if(westValid){
//                DFS(i,jWest);
//            }


      }



   }






//    boolean southValid;
//    int iSouth, jSouth;
//    iSouth=i+1; jSouth=j;
//    if (iSouth>=M){
//        southValid=false;
//    }
//    else {
//        southValid=true;
//    }
//
//    boolean southUnvisited;
//    if ((southValid)&&
//         (adjacencyMatrix[iSouth][jSouth]==-1)){
//        southUnvisited=true;
//    }
//    else{
//        southUnvisited=false;
//    }
//
//
//    boolean northValid;
//    int iNorth, jNorth;
//    iNorth=i-1; jNorth=j;
//
//    if(iNorth<0){
//        northValid=false;
//    }
//
//    else{
//        northValid=true;
//     }
//
//    boolean northUnvisited;
//    if ((northValid)
//         &&(adjacencyMatrix[iNorth][jNorth]==-1)){
//        northUnvisited=true;
//    }
//    else {
//        northUnvisited=false;
//    }
//
//    boolean westValid;
//    int iWest, jWest;
//    iWest =i; jWest=j-1;
//    if (jWest<0){
//        westValid=false;
//    }
//    else {
//        westValid=true;
//    }
//
//    boolean westUnvisited;
//
//
//    if ((westValid)&&(adjacencyMatrix[iWest][jWest]==-1))
//      {
//        westUnvisited=true;
//       }
//        else {
//        westUnvisited=false;
//        }
//
//
//
//    boolean eastValid;
//    int iEast, jEast;
//    iEast=i; jEast=j+1;
//    if (jEast<0){
//        eastValid=false;
//    }
//     else{
//        eastValid=true;
//    }
//
//    boolean eastUnvisited;
//    if (eastValid&&
//       (adjacencyMatrix[iEast][jEast]==-1)){
//        eastUnvisited=true;
//    }
//    else {
//        eastUnvisited=false;
//    }
//
//    double lottery = Math.random();
//
//
//
//    boolean canVisitNorth=northUnvisited&&northValid;
//    boolean canVisitSouth=southUnvisited&&southValid;
//    boolean canVisitEast=eastUnvisited&&eastValid;
//    boolean canVisitWest=westUnvisited&&westValid;
//
//    if (lottery>0.75D)
//    {
//
//        if(canVisitNorth)
//            DFS(iNorth, jNorth);
//
//        else if(canVisitSouth)
//            DFS(iSouth, jSouth);
//
//        else if(canVisitEast)
//            DFS(iEast, jEast);
//
//        else if(canVisitWest)
//            DFS(iWest, jWest);
//
//     }
//
//     else if(lottery < 0.25D)
//     {
//
//       if(canVisitSouth)
//            DFS(iSouth, jSouth);
//
//       else if(canVisitNorth)
//            DFS(iNorth, jNorth);
//
//        else if(canVisitEast)
//            DFS(iEast, jEast);
//
//        else if(canVisitWest)
//            DFS(iWest, jWest);
//
//
//     }
//
//      else if((lottery >= 0.25D)&&
//             (lottery<0.5D))
//     {
//        if(canVisitEast)
//          DFS(iEast, jEast);
//
//         else if(canVisitSouth)
//            DFS(iSouth, jSouth);
//
//        else if(canVisitNorth)
//            DFS(iNorth, jNorth);
//
//        else if(canVisitWest)
//            DFS(iWest, jWest);
//
//
//     }
//
//    else if((lottery >= 0.5D)&&
//             (lottery<0.75D))
//     {
//
//        if(canVisitWest)
//            DFS(iWest, jWest);
//
//        else if(canVisitEast)
//          DFS(iEast, jEast);
//
//         else if(canVisitSouth)
//            DFS(iSouth, jSouth);
//
//        else if(canVisitNorth)
//            DFS(iNorth, jNorth);
//
//
//     }





} //end DFS

//
}


public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here



    Graph theGraph = new Graph(3,3);
    theGraph.DFS(0,0);



    }

}

这段代码给了我这样的输出：

Visit i,j: 0 0
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
Visit i,j: 1 0
Visit i,j: 2 0

即使我正在验证下一步的位置（通过布尔值 southValid、eastValid 等）

score 0 · Accepted Answer

我有一个改变你的goWhere方法的建议，因为在选择走哪条路时，所有方向的权重都是一样的。

String goWhere (boolean northValid, boolean southValid, boolean eastValid, boolean westValid){

    java.util.Random r = new java.util.Random();
    ArrayList<String> valids = new ArrayList<String>();
    if(northValid) { valids.add("north"); }
    if(southValid) { valids.add("south");}
    if(eastValid) { valids.add("east"); }
    if(westValid) { valids.add("west"); }

    if (valids.size() > 1) {
        int rand = r.nextInt(valids.size());
        return valids.get(rand);
    } else { return null; } 
}

我认为您可以摆脱其他测向仪方法。我认为仍然存在一些错误，其中 i 或 j 在矩阵边界之外，但我认为这种方法更改可能会消除一些复杂性。请参阅上面关于在“northOrEast”方法中返回“south”的说明。

此外，请考虑使用常量作为您的方向。这将有助于防止拼写错误，编译器会捕捉到它。

public static final int NORTH = 0;
public static final int SOUTH = 1;
public static final int EAST = 2;
public static final int WEST = 3;

然后，不要进行字符串比较，而是执行以下操作：

if (Graph.EAST == where) { ... }

我认为设置有效布尔值有问题。代替：

if (!(iNorth<0)) northValid=true;

尝试：

northValid = (iNorth >= 0);

在 North 的情况下不一定有问题，但是如果某事小于其他事，那么对于 false 的测试会有点令人困惑。

当您与 M 或 N 进行比较时，您使用 > 来表示它是无效的。我认为南方，例如，如果它 >= M 则无效。或者只是这样做：

southValid = (iSouth < M);

score 0 · Accepted Answer

添加这个方法

private boolean boundariesOK(int i, int j) {
    return i >= 0 && j >= 0 && i < this.M && j < this.N;
}

并将决定更改为

if (boundariesOK(i,j) && adjacencyMatrix[i][j] == -1) { // if the vertex is unvisited

您的代码正试图访问 Matrix 上的无效位置（没有双关语 =））。

这是第一次黑客攻击。现在计算 DFS 部分，您的代码应该能够在其中找到网格中的所有位置，而目前还没有。

depth-first-search - Java：随机化 DFS 运行以构建迷宫的麻烦

2 回答 2

Related

Reference