Percorso minimo labirinto Java 2d int array

Question

Attualmente sono bloccato su un progetto. Il mio obiettivo è usare l'algoritmo di Dijkstra.

Capisco che parto dal punto (0,0). Guardo i due nodi vicino al punto di partenza e poi mi muovo verso il più piccolo e guardo i nodi circostanti. Il mio labirinto è casuale, ma per rendere più facile l'inizio, lascia che il seguente sia il mio labirinto.

Inizio a (0,0) e voglio terminare a (9,9) i numeri sono il livello PERICOLO e miriamo al percorso più sicuro non proprio il più breve.

Ho bisogno di una spinta per capire come impostare questo. So che ho bisogno di una lista o di un percorso per mantenere dove sono e dove voglio guardare. ma non so come farlo in 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)); 
      } 
      } 
      } 
    } 
} 

Il labirinto è collegato senza pareti tutte le scatole sono stanze. Ho cercato di lavorare su questo per tempo e potrei davvero usare una spinta. Ho visto molti video sull'algoritmo di dijstkra che attualmente mi sto davvero perdendo.

ho aggiunto un array che io continuo il pericolo in esso inizia facendo mai nodo 100000000 ma il nodo di partenza (0,0) è 0.

Qualcuno mi può aiutare con i prossimi passi Capisco che è compiti a casa, ma Sto esaurendo il tempo e ho davvero bisogno di alcuni suggerimenti.

UPDATE:

OK così ce l'ho workingish. Stampa il percorso necessario ma, se trova un percorso migliore, stampa entrambi, qualcuno può aiutarmi a risolvere questo problema.

Inoltre si rompe se faccio 100X100 elemento qualcuno può dirmi perché? Questo è l'ultimo dei veri "incarichi di programmazione". Come ci si potrebbe aspettare, questo coinvolgerà i grafici (con una svolta); ma naturalmente ci saranno anche dei problemi di risoluzione dei problemi. istruzioni

---

immaginare un “gioco Dungeon” dove tutte le camere sono disposte in una griglia perfetta con in un ambiente quadrato. Ogni stanza ha una creatura che presenta un certo grado di pericolo che va da 0 (innocuo) a 9 (evitare sarebbe prudente). L'obiettivo è quello di trovare un percorso attraverso il dungeon dall'inizio alla fine che riduca al minimo la quantità complessiva di pericolo.

Ogni stanza, a meno che non vi sia un limite, esiste solo nelle direzioni su, giù, sinistra, destra (nessuna diagonale). L'ingresso è in alto a sinistra (0,0) e l'uscita è in basso a destra (n-1, n-1).

Elenca tutte le "stanze" che devono essere attraversate, sotto forma di un percorso di coordinate stanza, dall'inizio alla fine.

Ad esempio:

(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (3, 3) (4,3) (4,4)

pericolo totale = 11 ingresso

Il file di input sarà composto da 100 righe di 100 cifre, 0-9. (Sì, 10.000 sono un sacco di stanze, ma fortunatamente il nostro intrepido viaggiatore non esce mai di casa senza un computer portatile e una raccolta di set di dati elettronici per tutte le occasioni ricevute nello scambio di regali per le vacanze dello scorso anno, probabilmente riconfermato.) *

* Per questo compito, è necessario generare i propri dati di test. Questo è il motivo per cui non vado a questi tipi di feste ... Uscita

Il programma dovrebbe scrivere l'output in un file (nel formato illustrato sopra, incluso l'output "pericolo totale"). Grazie.

UPDATE2: Ho trovato un errore nel mio codice ho

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

In questo modo sarà verificare ogni percorso che è lì in un determinato punto il mio percorso più breve è più grande, allora l'altro percorso come posso risolvere questo ?

Cosa mi manca? AGGIORNAMENTO Ho finito questo grazie per l'aiuto MOLTO PICCOLO.

Answer 1

Ho appena guardato alle voci di Wikipedia Dijkstra's Algorithm.

1. Assegnare ad ogni nodo un valore provvisorio distanza: impostato a zero per il nostro nodo iniziale e all'infinito per tutti gli altri nodi.
2. Contrassegna tutti i nodi non visitati. Imposta il nodo iniziale come corrente. Crea un insieme di nodi non visitati chiamato il set non visitato composto da tutti i nodi eccetto il nodo iniziale.
3. Per il nodo corrente, considerare tutti i suoi vicini non visitati e calcolare le loro distanze provvisorie. Ad esempio, se il nodo A corrente è contrassegnato con una distanza di 6 e il bordo che lo collega a un vicino B ha lunghezza 2, allora la distanza da B (a A) sarà 6 + 2 = 8. Se questa distanza è inferiore alla distanza precedentemente registrata, quindi sovrascrive quella distanza. Anche se un vicino è stato esaminato, , non è contrassegnato come visitato in questo momento e rimane in il set non visitato.
4. Quando abbiamo finito di considerare tutti i vicini del nodo corrente, contrassegnare il nodo corrente come visitato e rimuoverlo dal set non visitato . Un nodo visitato non verrà mai più controllato; la sua distanza ora registrata è definitiva e minima.
5. Se il set non visitato è vuoto, quindi fermarsi. L'algoritmo è finito.
6. impostare il nodo non visitato segnato con la più piccola distanza tentativo come il prossimo "nodo corrente" e tornare al punto 3.

Basta avvicinarsi ingenuamente in un primo momento. Diamine, trattalo come "la comprensione della lettura del programmatore". In questo caso, il trucco è la mappatura della matrice bidimensionale su una serie di nodi grafici. Ogni nodo ha bisogno di "un valore di distanza provvisorio". Ok, i tuoi nodi sono definiti dal loro valore i, j. Crea qualcosa in modo che tu possa ottenere/impostare un valore tentative_distance dato un i e j.

È necessario contrassegnare se un nodo è visitato. Stessa idea

È necessario un "nodo corrente". Stessa idea, ma più semplice.

So che ho bisogno di una lista o di un percorso per mantenere erano. Sono e volevo vedere . ma non so come farlo in Java.

Tecnicamente, si non lo fanno necessità di mantenere un percorso per eseguire l'algoritmo. Dovrai capire come costruirlo dai risultati dell'algoritmo se non lo fai, ma è certamente possibile.

Answer 2

Una volta capito come utilizzare l'algoritmo di Dijkstra, è possibile utilizzare un ArrayList contenente coppie di numeri che indicano le vostre posizioni precedenti:

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

è quindi possibile scrivere una classe Point che avvolge semplicemente due int primitive, x e .

Quindi, quando si sposta, è possibile utilizzare:

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

    // Move yourself to this point 
    ... 
} 

quanto per imparare a realtà impiegare l'algoritmo, penso che sia un po 'il punto di vostro lavoro, e non voglio rovinare il tuo divertimento!

L'articolo di Wikipedia sull'algoritmo è abbastanza utile, anche se ho la sensazione che anche le note di classe aiuteranno.

Dijkstra's algorithm on Wikipedia

Answer 3

Sono andato avanti e implementato l'algoritmo come citato da ccoakley. Seguito troverete il codice parziale, per aiutarvi nella giusta direzione:

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: aggiunto i bit mancanti

Answer 4

È possibile basare la vostra soluzione su algoritmi si trovano in "Introduzione agli algoritmi" di Cormen, Leiserson, Rivest e Stein, 2a edizione. Nel capitolo 24 analizzano l'algoritmo "percorsi a sorgente singola" e in 24.3 avete Dijkstra.

Utilizzerò qui lo pseudo-codice. È possibile sostituire la coda con priorità minima in basso con un'altra struttura dati come una mappa in Java. Non sarà veloce ma funzionerà e potrebbe essere un primo tentativo soddisfacente. Ho anche un'implementazione Java di una coda con priorità minima, se vuoi.

Supponi di avere il labirinto rappresentato da un array 2D come nel tuo codice: int [M] [N] labirinto. Il primo indice è l'indice di riga e il secondo è l'indice di colonna, a base zero. Passando quindi da 0 a M-1 per le righe e da 0 a N-1 per le colonne. Il valore labirinto [riga] [colonna] rappresenta il pericolo associato alla stanza in (riga, colonna).Abbiamo bisogno di una rappresentazione conveniente per ottenere il peso tra due stanze nel labirinto e sapere quali stanze sono adiacenti ad una stanza specifica.

L'idea è di appiattire l'array e di mettere ogni riga una accanto all'altra: riga1, riga2, ..., rigaM. Quindi possiamo dare un indice a ogni stanza. Per essere in grado di utilizzare questa idea, è necessario convertire tra diversi tipi di coordinate: (riga, colonna) -> i e i -> (riga, colonna).

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

Dire SIZE è M * N, il numero totale di stanze nel labirinto.

Ora possiamo creare una matrice di adiacenza che rappresenta il labirinto con i valori di pericolo: int [SIZE] [SIZE] adjacency_matrix, il primo indice è il FROM, il secondo è il TO. In una cella troviamo il costo o il peso per passare da una stanza all'altra. Nota che data una stanza specifica, ci sono solo alcune stanze adiacenti a quella stanza. Le altre stanze nel labirinto non sono raggiungibili da quella stanza. Per convenzione, useremo il più grande numero intero per indicare questo e usare la costante INFINITY. Gli altri valori rappresentano il pericolo e vanno da 0 a 9. La matrice sarà sparsa e ci sono tecniche per ottimizzarlo.

Quando abbiamo una stanza situata in (r, c), quali sono le stanze adiacenti? Vogliamo avere un vettore di indici da utilizzare direttamente nel nostro algoritmo. Se non teniamo conto dei confini del labirinto, abbiamo: (r-1, c-1), (r-1, c), (r-1, c + 1), (r, c-1) , (r, c + 1), (r + 1, c-1), (r + 1, c) e (r + 1, c + 1). Potremmo quindi applicare convert_to_index a ciascuno di essi, verificare che siano compresi nell'intervallo 0..SIZE-1 e inizializzare la matrice con quello. Quindi, ad esempio, passare da (r, c) a (r-1, c-1) ha un costo o un pericolo di labirinto [r-1, c-1] e va da (r-1, c-1) a (r, c) ha un costo di labirinto [r, c]. Ma andare da (r, c) ad un'altra stanza distante ha un costo di 10, è irraggiungibile e l'inverso è vero.

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 

successivo abbiamo bisogno di un vettore stime di stime cammini minimi (cfr. Libro pagina 585) e un vettore predecessori (Cfr. Pag 584 del libro).

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

Andando fin dall'inizio ai costi di start 0.

estimates[0] := 0 

Initialize insieme di vertici che appartengono al MST (minimo spanning tree)

mst := empty set 

La coda di min-priorità q è inizializzato

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 

Il lavoro è finito. Abbiamo il nostro percorso in predecessors con i costi in estimates.

Questo potrebbe essere eccessivo e A * potrebbe essere migliore. Ma immagino che usare Dijkstra fosse un requisito per i tuoi compiti. Se vuoi esplorare A *, ti suggerisco di dare un'occhiata a A* Pathfinding for Beginners e Amit’s A* Pages.