Javaの8x8グリッドの幅優先検索

Question

私がやっていることは、最短経路を使用して目標に到達するまでの移動回数を数えることです。幅広い最初の検索を使用して行う必要があります。私は空のためにE（これらのスポットに移動できる）、Bはブロックされている（ここでは動かない）、Rはロボット（出発点）、Gは4つの文字のうちの1つで満たされた2次元配列に入れます目標のために。アルゴリズムは、上、左、右、下の順に可動スペースがないかチェックしなければなりませんでした。ノードがチェックされた後、ノードの内容は「B」に変更されます。目標に到達できない場合は、0を返す必要があります。

私はKshitijが私に語ったことを実装するためにコードを変更しました。それは美しく動作します。すべての新しいデータセットの後にキューを初期化していないことを知るにはあまりにも疲れました。助けてくれてありがとう！

public static int bfSearch(){ 
    Queue <int []> queue = new LinkedList <int []>(); 
    int [] start = {roboty,robotx,0}; 
    queue.add(start); 

    while (queue.peek() != null){ 
     int [] array = queue.remove(); 

      if(array[0]-1 >= 0 && grid[array[0]-1][array[1]] != 'B'){ 

       if (grid[array[0]-1][array[1]] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]-1][array[1]] = 'B'; 
        int [] temp = {array[0]-1, array[1], array[2]+1}; 
        queue.add(temp); 
       } 
      } 

      if(array[1]-1 >= 0 && grid[array[0]][array[1]-1] != 'B'){ 

       if (grid[array[0]][array[1]-1] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]][array[1]-1] = 'B'; 
        int [] temp = {array[0], array[1]-1, array[2]+1}; 
        queue.add(temp); 
       } 
      } 

      if(array[1]+1 <= 7 && grid[array[0]][array[1]+1] != 'B'){ 

       if (grid[array[0]][array[1]+1] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]][array[1]+1] = 'B'; 
        int [] temp = {array[0], array[1]+1, array[2]+1}; 
        queue.add(temp); 
       } 
      } 

      if(array[0]+1 <= 7 && grid[array[0]+1][array[1]] != 'B'){ 

       if (grid[array[0]+1][array[1]] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]+1][array[1]] = 'B'; 
        int [] temp = {array[0]+1, array[1], array[2]+1}; 
        queue.add(temp); 
       } 
      } 
     }   
    return 0; 
} 

Answer 1

キューに2つのものを格納する必要があります。キュー内の各アイテムをノードと呼ぶことにしましょう。

1. 位置（すでに店）
2. 数（開始位置からこの位置に到達するために必要な移動）

あなたは0にあなたの開始位置の数を割り当てることによって始めます。

アルゴリズムが動作する方法は次のとおりです。

1. あなたはキューからノードをポップ
2. ポップしたばかりのノードで指定された位置からどこに行くことができるかを決定します。つまり、これを「オンザフライでツリーを作成する」とみなした場合、キューからポップしたノードの子を決定しています。
3. これらの子をキューに追加します。

ノードの子をキューに追加するときは、このノードに追加する必要があるカウントを決定する必要があります。このカウントは単にcount of the parent node (that you popped in step 1) + 1

です。最後に、戻り値は、宛先位置を持つノードに関連付けられたカウントになります。

たとえば、位置[0,0]が開始位置で[0,3]が移動先である4x4グリッドで作業できます。

S E E B 
E B E E 
B B B E 
G E E E 

最初に、あなたのキューは次のようになります。

[{(0, 0), 0}] 

()内の値は位置であり、{}内側の第二の値は、カウントです。

キューからこのノードをポップし、位置（0,1）と（1,0）に到達できると判断した場合。したがって、項目{(0, 1), 1}と{(1, 0), 1}をキューに追加します。そう、あなたが最初の要素をポップ

[{(0, 1), 1}, {(1, 0), 1}] 

、それは実行可能な子供を持っていないことを実現：ポップノードのカウントが0だったと私たちは1であなたのキューは、今のように見えることをインクリメントするのでカウントが1であることに注意してくださいあなたは移動します。

残りの要素をポップアップし、取得できるノードが位置（2、0）にあることがわかります。ポップしたノードのカウントが1であるため、この新しい位置をcount = 1 + 1 = 2とペアにしてキューに追加します。

最終的に、あなたは、キューからゴールノードをポップだろう、それはあなたが元から宛先へのパスを取得したい場合はカウントは9

編集

になります、現在のエンコーディングはそのまま動作しません。ノード自体でエンコードするのではなく、カウントで8×8のサイズの別の2D配列を維持する必要があります。そして最終的に目的地の数を見つけると、2Dカウント配列を使って目的地から元に戻ります。本質的に、あなたが9つの移動で目的地に行くことができるならば、あなたは8つの動きでその隣り合った位置の1つに行くことができます。だから、数が8で、目的地に隣接する位置を見つけることができます。ソースに到達するまでこれを繰り返します。

ノードに余分な要素を追加する方法では機能しません。これは宿題であるので、理由を調べるためにあなたのために残しておきます:)

Answer 2

あなたのコードにの短い代替があります。まったく同じアイデアだが、各座標の有効性をチェックする非常に多くの「条件」の必要はない。これはすべて一度に行うことができます。見てみましょう。

私はできる限り説明をコメントしました。それは読んでも、誰もが、少しのアイデアはありません。私は迷路に閉じ込められた男が自分の道を見つけなければならないような、同じ（同じ？）問題の解決策を実装していたときにあなたの質問に出会ったのです。グリッドにはトラップ（B）と可動領域（E）がありました。目標は目的地に到達することでした（G）。

とにかく、ここに一般化されたコードがあります。私は行、列、そして完全なグリッドの番号を取る。私は宛先に到達することが可能であるかどうかを印刷するだけです。私はあなたのコードを理解してきたことを確認する練習としてこれを読んで誰か件まで残りを残す;）

マインド私の答えの主な目的をお見せすることであるという事実をそのあなたのBFSのサイズ機能は、を減らすことができました。私はそれを学んでいる間に苦労して以来、グリッドに適用されたBFSの全体的なアイデアを与えるために私のソリューション全体を投稿しています。うまくいけば、これは誰かが同じ状況で立ち往生するのを助けるでしょう。あなたがその場所または何かを追いかけることを望むなら、この質問の答えの指示に従ってください。それを行う自分;）アクションで

import java.util.*; 

/** 
* Created by Shreyans on 4/30/2015 at 10:27 PM using IntelliJ IDEA 
*/ 

class MAZE 
{ 
    static int r,c,s1,s2,f1,f2;//Rows, Columns, Start Coordinates, Finish Coordinates 
    static int[] dx={1,-1,0,0};//right, left, NA, NA 
    static int[] dy={0,0,1,-1};//NA, NA, bottom, top 
    static char[][] grid;//Main grid 
    public static void main(String[] args) 
    { 
     Scanner sc=new Scanner(System.in);//I suggest using faster IO if you have performance concerns. I did. Scanner is readable hence the choice 
     r=sc.nextInt(); 
     c=sc.nextInt(); 
     grid=new char[r][c]; 
     for(int i=0;i<r;i++) 
     { 
      char[] s1=sc.next().toCharArray();//Reading a line of the Grid 
      System.arraycopy(s1,0,grid[i],0,c);//Nice inbuilt function to copy contents of an array. Also doable manually 
     } 
     s1=sc.nextInt()-1; 
     s2=sc.nextInt()-1; 
     f1=sc.nextInt()-1; 
     f2=sc.nextInt()-1; 
     if(MAZEBFS()) 
     { 
      System.out.println("PATH EXISTS"); 
     } 
     else 
     { 
      System.out.println("PATH DOES NOT EXIST"); 
     } 
    } 
    private static boolean MAZEBFS() 
    { 
     if(s1==f1&&s2==f2) 
     { 
      return true;//He's already there 
     } 
     else 
     { 
      grid [f1][f2]='G';//finish 
      Queue<int[]> q=new LinkedList<int[]>(); 
      int[]start={s1,s2};//Start Coordinates 
      q.add(start);//Adding start to the queue since we're already visiting it 
      grid[s1][s2]='B'; 
      while(q.peek()!=null) 
      { 
       int[]curr=q.poll();//poll or remove. Same thing 
       for(int i=0;i<4;i++)//for each direction 
       { 
        if((curr[0]+dx[i]>=0&&curr[0]+dx[i]<r)&&(curr[1]+dy[i]>=0&&curr[1]+dy[i]<c)) 
        { 
         //Checked if x and y are correct. ALL IN 1 GO 
         int xc=curr[0]+dx[i];//Setting current x coordinate 
         int yc=curr[1]+dy[i];//Setting current y coordinate 
         if(grid[xc][yc]=='G')//Destination found 
         { 
          //System.out.println(xc+" "+yc); 
          return true; 
         } 
         else if(grid[xc][yc]=='E')//Movable. Can't return here again so setting it to 'B' now 
         { 
          //System.out.println(xc+" "+yc); 
          grid[xc][yc]='B';//now BLOCKED 
          int[]temp={xc,yc}; 
          q.add(temp);//Adding current coordinates to the queue 
         } 
        } 
       } 
      } 
      return false;//Will return false if no route possible 
     } 
    } 
} 

コード：http://ideone.com/jiZKzn

任意の提案は大歓迎。乾杯：D