Java Maze最短パス2d int配列

Question

現在、私はプロジェクトに取り残されています。 私の目的は、ダイクストラのアルゴリズムを使用することです。

私はポイント（0,0）から開始することを理解しています。私は開始ポイントの隣にある2つのノードを見て、次に最小のものに移動して周囲のノードを見ます。私の迷路はランダムですが、始めるのが簡単にできるようにするには、次のことが私の迷路です。

私は（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桁、0-9の100行からなります。 （はい、10,000部屋がたくさんあることですが、幸運にも、私たちの勇敢な旅行者は、すべての行事のために、携帯型コンピュータや電子データ・セットの集合せずに家を離れることはありません昨年のクリスマスプレゼント交換で受信し、それはおそらく、再才能ました。 ）*

*この割り当てのために、独自のテストデータを生成する必要があります。これが私がこの種のパーティーに行かない理由です... 出力

プログラムは出力をファイルに書き込む必要があります（前述の "危険度"の出力を含む）。おかげさまで

アップデート2：私は私の私はこれはそれが私の最短経路は、私はこの問題を解決しますどのように他のパスその後、大きい与えられた点であり、すべてのパスをテストするようになります

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

を持つコーディングでエラーを検出しました？

私は私が何をしないのですか？ 更新非常に軽いヘルプでこの感謝を終えました。

Answer 1

私はちょうどDijkstra's Algorithm上のWikipediaの記事を見ました。

1. 割り当てあらゆるノード仮距離値：我々の最初のノードのためにゼロに設定し、他のすべてのノードのために無限に。
2. マークのすべてのノード未訪問。初期ノードを最新のノードに設定します。最初のノードを除くすべてのノードからなる未訪問のセット と呼ばれる未訪問ノードのセットを作成します。
3. 現在のノードでは、未訪問のネイバをすべて考慮して仮の距離を計算します。例えば、現在の ノードAが6の距離でマークされ、 隣接ノードBと接続するエッジが長さ2の場合、Bまでの距離（Aを通る）は 6 + 2 = 8になります。この距離が以前に記録された距離よりも小さい場合、 はその距離を上書きします。隣人は検査された でしたが、現時点で訪問されたとはマークされておらず、未訪問のセット にとどまります。
4. 現在のノードのすべての近隣ノードを検討したら、現在のノードを訪問済みとしてマークし、 未訪問セットから削除します。訪問先ノードは決して再度チェックされません。現在 の距離が最後に記録されています。
5. 未訪問のセットが空の場合は、停止します。アルゴリズムは終了しました。
6. ただ、最初は単純にそれに近づく次の「現在のノード」として、最小仮距離でマークされた未訪問のノードを設定し、3

に戻ってください。ヘック、それを「プログラマーの読解力」と見なしてください。この場合、このトリックは、2次元配列をグラフノードのセットにマッピングします。すべてのノードは「一時的な距離値」を必要とします。あなたのノードはi、jの値で定義されています。何かを作って、iとjが与えられたtentative_distance_valueを取得/設定できるようにします。

ノードにアクセスした場合は、マークする必要があります。同じ考え。

「現在のノード」が必要です。同じアイデアだが、単純だ。

私には、リストまたはパスを保持する必要があることがわかります。私は 見たいと思いました。しかし、私はjavaでそれを行う方法を知らない。

は技術的には、あなたがいないアルゴリズムを実行するためのパスを維持する必要があります。アルゴリズムの結果からそれを構築する方法を理解しなければなりませんが、確かに可能です。

Answer 2

あなたはダイクストラのアルゴリズムを使用する方法を理解したら、あなたはあなたの前の位置を示す数字のArrayList含むペア使用することができます。

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

をあなたは、単に2つのintプリミティブ、xをラップPointクラスを記述することができますおよびy。

だから、あなたが移動すると、あなたが使用することができます。

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

    // Move yourself to this point 
    ... 
} 

をどのように実際に採用アルゴリズムに学習するためとして、私はそれが多少宿題のポイントだと思う、と私たちは台無しにしたくありませんあなたの楽しみ！

私はあなたのクラスのノートにも役立ちます感じているものの、アルゴリズム上のWikipediaの記事は、かなり便利です。

Dijkstra's algorithm on Wikipedia

Answer 3

私は先に進み、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); 
    } 
} 

EDIT：追加行方不明ビット

Answer 4

あなたはCormen、Leiserson、リベストによって「アルゴリズム入門」で見つかったアルゴリズムにあなたのソリューションをベースにすることができますとスタイン、第2版。 24章では、「単一ソースの最短経路」アルゴリズムを分析し、24.3でDijkstraを使用します。

ここでは擬似コードを使用します。下の最小優先順位のキューをJavaのマップのような別のデータ構造に置き換えることができます。それは速くはないが、それは動作し、それは満足のいく最初の試行になる可能性があります。必要に応じて、最小優先度キューのJava実装もあります。

あなたのコードに次のような2次元配列で表される迷路があるとします：int [M] [N] maze。最初のインデックスは行インデックスで、2番目のインデックスは0から始まる列インデックスです。したがって、行は0からM-1に、列は0からN-1になります。値maze [row] [column]は、（row、column）の部屋に関連する危険を表します。迷路の2つの部屋の間の重量を取得し、どの部屋が特定の部屋に隣接しているかを知るのに便利な表現が必要です。

考え方は、配列を平坦化し、すべての行を並べて並べることです：row1、row2、...、rowM。次に、各部屋にインデックスiを付けることができます。この考え方を使うには、（行、列） - > iとi - >（行、列）の異なるタイプの座標間で変換する必要があります。

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

と言って、SIZEはM * Nで、迷路内の部屋の総数です。

危険度の値を持つ迷路を表す隣接行列を作ることができます：int [SIZE] adjacency_matrix、最初のインデックスはFROM、2番目はTOです。セルでは、ある部屋から別の部屋に行くためのコストや重量がわかります。特定の部屋がある場合、その部屋に隣接する部屋はごくわずかです。迷路の他の部屋は、その部屋から到達できません。慣習上、最大の整数を使用して定数INFINITYを使用します。他の値は危険度と0〜9の範囲を表します。行列は疎であり、最適化するテクニックがあります。

（r、c）に部屋がある場合、それに隣接する部屋は何ですか？私たちはアルゴリズムで直接使用されるインデックスのベクトルを持ちたいと思っています。迷路境界を考慮しなければ、（r-1、c-1）、（r-1、c）、（r-1、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）は迷路[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 

次は、我々は最短パス推定値（CFR。ブックページ585）と前任者のベクトル（CFR。ブックページ584）のベクトル推定値を必要とします。開始費用に最初から行く

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

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 

ジョブが完了しました。我々はのコストでpredecessorsに私たちのパスを持っています。

これは過度の可能性があり、A *が優れている可能性があります。しかし、私はダイクストラを使用することはあなたの宿題の要件であったと思います。 A *を探索したい場合は、A* Pathfinding for BeginnersとAmit’s A* Pagesをご覧ください。