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 и т. Д.)

Jason · Answer 1 · 29 апреля 2011

У меня есть предложение изменить метод 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 находятся за пределами матрицы, но я думаю, что это изменение метода может устранить некоторые сложности.См. Мое примечание выше о возврате «south» в вашем методе «northOrEast».

Также рассмотрите возможность использования констант для ваших указаний.Это поможет предотвратить опечатки, и компилятор поймает их.

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);

В случае с севером проблема не обязательно, но это немного сбивает с толку проверку на ложь, если что-то меньше, чем что-то еще.

Когда вы сравниваете с M или N, вы используете>, чтобы указать, что он недействителен.Я думаю, что Юг, например, если недействителен, если это> = M. Или просто сделайте:

southValid = (iSouth < M);

Niloct · Answer 2 · 29 апреля 2011

Добавьте этот метод

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

Ваш код пытается посетить недопустимую позицию в Матрице (без каламбура =)).

Это первый взлом.Теперь рассмотрим часть DFS, где ваш код должен найти все позиции в сетке, чего в настоящее время нет.

Java: проблема рандомизации DFS для запуска лабиринта

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Java: проблема рандомизации DFS для запуска лабиринта

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы