Java迷宮最短路徑2d int數組

Question

我目前被困在一個項目中。 我的目標是使用Dijkstra的算法。

我知道我從點（0,0）開始，看着起點旁邊的兩個節點，然後我移動到最小的第一個點，看看周圍的節點。我的迷宮是隨機的，但讓它容易開始讓我們說以下是我的迷宮。

我將從（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算法的視頻，我現在真的很失落。

我添加了一個數組，我把危險在它開始通過使以往節點億，但起始節點（0,0）爲0

有人可以幫助我的下一個步驟，我知道這是作業，但我沒有時間，真的需要一些指針。

UPDATE：

行，所以我把它workingish。它會打印它所需的路徑，但是如果它找到了更好的路徑，它會同時打印兩個人是否可以幫助我修復此問題

它也打破了，如果我做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行的100個位數，0-9。 （是的，10,000是很多房間，但幸運的是，我們無畏的旅行者在去年的節日禮物交換中沒有收到便攜式計算機和所有場合收集的電子數據集合，都不會離開家;它可能會重新獲得天賦。 ）*

*對於此作業，您必須生成您自己的測試數據。這就是爲什麼我不去這些派對...... 輸出

程序應該將輸出寫入文件（以上述格式，包括「全部危險」輸出）。 謝謝。

UPDATE2：我發現在我的編碼錯誤我有

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

這將使測試每一個路徑是有在給定的點我的最短路徑是更大然後是其他路徑我怎麼解決這個問題？

我錯過了什麼？ 更新我完成了這個感謝非常小的幫助。

Answer 1

我只是看着就Dijkstra's Algorithm維基百科的文章。

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

一旦你瞭解如何使用Dijkstra算法，可以使用包含數字的雙指示你以前的職務的ArrayList：

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

然後，您可以編寫一個Point類，只是封裝2 int元，x和y。

所以，當你移動時，你可以使用：

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

    // Move yourself to this point 
    ... 
} 

至於學習如何實際聘請的算法，我認爲這是屬於你的家庭作業的點，我們並不想破壞你的樂趣！

關於算法的維基百科文章是相當有用的，雖然我有一種感覺你的課堂筆記也會有所幫助。

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

編輯：添加的失位

Answer 4

您可以通過Cormen，Leiserson，維斯特基礎你在「算法導論」發現算法解決方案和Stein，第2版。在第24章中他們分析了「單源最短路徑」算法，24.3中有Dijkstra算法。

我會在這裏使用僞代碼。您可以用另一個數據結構（如Java中的映射）替換下面的最小優先級隊列。它不會很快，但它會工作，這可能是一個令人滿意的第一次嘗試。如果需要，我還有一個最小優先級隊列的Java實現。假設你有一個二維數組所表示的迷宮，如你的代碼：int [M] [N]迷宮。第一個索引是行索引，第二個索引是列索引，從零開始。因此，對於行從0到M-1以及對於列從0到N-1。值迷宮[行] [列]代表與（行，列）房間相關的危險。我們需要一個方便的代表來獲得迷宮中兩個房間之間的重量，並知道哪些房間與特定房間相鄰。

這個想法是壓扁數組並將每一行並排放置：row1，row2，...，rowM。然後我們可以給每個房間一個索引。爲了能夠使用這個想法，我們需要在不同類型的座標之間進行轉換：（行，列） - >我和我 - >（行，列）。

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

說SIZE是M * N，迷宮中的房間總數。

現在我們可以用一個危險值表示迷宮的鄰接矩陣：int [SIZE] [SIZE] adjacency_matrix，第一個索引是FROM，第二個是TO。在一個單元中，我們發現從一個房間到另一個房間的成本或重量。請注意，給定一個特定的房間，只有幾個房間毗鄰該房間。迷宮中的其他房間無法從該房間抵達。按照慣例，我們將使用最大的整數來表示並使用常數INFINITY。其他值表示危險，範圍從0到9.矩陣將是稀疏的，並有技術來優化。

當我們有一個房間位於（r，c）時，與它相鄰的房間是什麼？我們想要在我們的算法中直接使用索引向量。如果我們不考慮迷宮邊界，我們有：（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）。然後，我們可以將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 

從開始要起動成本0

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有我們的路徑，成本在estimates。

這可能是矯枉過正，A *可能會更好。但我想使用Dijkstra是你功課的要求。如果你想探索A *，我建議你看看A* Pathfinding for Beginners和Amit’s A* Pages。