Ruta más corta de Java Maze 2d int array

Question

Actualmente estoy atascado en un proyecto. Mi objetivo es usar el algoritmo de Dijkstra.

Entiendo que comienzo en el punto (0,0) miro los dos nodos junto al punto de inicio y luego me muevo al más pequeño primero y miro los nodos circundantes. Mi laberinto es aleatorio, pero para que sea fácil comenzar, digamos que el siguiente es mi laberinto.

Comenzaré en (0,0) y quiero terminar en (9,9) los números son el nivel PELIGRO y apuntamos a la ruta más segura, no la más corta.

Necesito un empujón para entender cómo configurar esto. Sé que necesito una lista o un camino para estar donde estoy y dónde quiero mirar. pero no sé cómo hacer eso en 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)); 
      } 
      } 
      } 
    } 
} 

El laberinto está conectado con ninguna pared todas las cajas son habitaciones. He estado tratando de trabajar en esto por tiempo y realmente podría usar un empujón. He visto muchos videos sobre el algoritmo de dijstkra. Actualmente estoy realmente perdido.

He añadido una matriz que guardo el peligro en que se inicia al hacer cada vez nodo 100 millones, pero el nodo de inicio (0,0) es 0.

alguien me puede ayudar con los siguientes pasos entiendo que es la tarea, pero Me estoy quedando sin tiempo y realmente necesito algunos consejos.

ACTUALIZACIÓN:

OK, así que tiene que workingish. Imprime la ruta que toma, pero si encuentra una mejor ruta, imprime tanto alguien puede ayudarme a solucionar esto.

También se rompe si lo hago elemento 100X100 ¿alguien me puede decir por qué? Esta es la última de las "asignaciones de programación" reales. Como puede esperar, esto involucrará gráficos (con un giro); pero, por supuesto, también habrá problemas para resolverlos. Instrucción

---

imaginar un “juego Dungeon” donde todas las habitaciones están dispuestas en una cuadrícula perfecta con un entorno en el cuadrado. Cada habitación tiene una criatura que presenta un cierto grado de peligro que va desde 0 (inofensivo) a 9 (la evitación sería prudente). El objetivo es encontrar un camino a través de la mazmorra de principio a fin que minimice la cantidad total de peligro.

Cada habitación, a menos que esté en el límite, solo existe en las direcciones arriba, abajo, izquierda, derecha (sin diagonales). La entrada está en la esquina superior izquierda (0,0) y la salida está en la esquina inferior derecha (n-1, n-1).

Enumere todas las "habitaciones" que deben atravesarse, en forma de una ruta de coordenadas de la habitación, desde el principio hasta el final.

Por ejemplo:

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

peligro total = 11 entrada

El archivo de entrada constará de 100 filas de 100 dígitos, 0-9. (Sí, 10,000 es un montón de habitaciones, pero afortunadamente, nuestro intrépido viajero nunca se va de su casa sin una computadora portátil y una colección de Conjuntos Electrónicos de Datos para Todas las Ocasiones recibidos en el intercambio de regalos navideños del año pasado, probablemente fue regalado nuevamente.) *

* Para esta tarea, deberá generar sus propios datos de prueba. Es por eso que no voy a este tipo de fiestas ... Salida

El programa debe escribir la salida en un archivo (en el formato ilustrado arriba, incluyendo el resultado de "peligro total"). Gracias.

Update2: i encontrado un error en mi codificación tengo

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

Esto hará que sea a prueba todos los caminos que está ahí en un momento dado mi camino más corto es más grande que el otro camino ¿cómo puedo solucionar este ?

¿Qué es lo que me estoy perdiendo? ACTUALIZACIÓN Terminé esto gracias por la MUY PEQUEÑA ayuda.

Answer 1

Yo miraba a un artículo de Wikipedia sobre Dijkstra's Algorithm.

1. Asignar a cada nodo un valor de distancia tentativa: puso a cero para nuestro nodo inicial y hasta el infinito para todos los otros nodos.
2. Marque todos los nodos no visitados. Establezca el nodo inicial como actual. Cree un conjunto de nodos no visitados llamado el conjunto no visitado que consta de todos los nodos excepto el nodo inicial.
3. Para el nodo actual, considere todos sus vecinos no visitados y calcule sus distancias tentativas. Por ejemplo, si el nodo A actual está marcado con una distancia de 6, y el borde que lo conecta con un vecino B tiene longitud 2, entonces la distancia a B (a través de A) será 6 + 2 = 8. Si esta distancia es menor que la distancia previamente registrada, , sobrescriba esa distancia. Aunque un vecino ha sido examinado , no está marcado como visitado en este momento, y permanece en el conjunto no visitado.
4. Cuando terminemos de considerar todos los vecinos del nodo actual, marque el nodo actual como visitado y elimínelo del conjunto no visitado. Un nodo visitado nunca se volverá a verificar; su distancia registrada ahora es final y mínima.
5. Si el conjunto no visitado está vacío, deténgalo. El algoritmo ha terminado.
6. Establecer el nodo no visitado marcado con la distancia más pequeña tentativa como el próximo "nodo actual" y vuelva al paso 3.

Sólo acercarse ingenuamente al principio. Diablos, trátelo como "comprensión de lectura del programador". En este caso, el truco es mapear su matriz bidimensional a un conjunto de nodos gráficos. Cada nodo necesita "un valor de distancia tentativo". Ok, tus nodos están definidos por su valor i, j. Haga algo para que pueda obtener/establecer un valor_distancia_provisional dado un i y j.

Debe marcar si se visita un nodo. La misma idea.

Necesita un "nodo actual". La misma idea, pero más simple.

Sé que necesito una lista o un camino para mantener. Estoy y si quiero ver . pero no sé cómo hacer eso en Java.

Técnicamente, No necesidad de mantener una trayectoria para ejecutar el algoritmo. Tendrás que averiguar cómo construirlo a partir de los resultados del algoritmo si no lo haces, pero ciertamente es posible.

Answer 2

Una vez que entienda cómo utilizar el algoritmo de Dijkstra, se puede usar un ArrayList que contiene pares de números que indican sus posiciones anteriores:

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

A continuación, puede escribir una clase Point que simplemente se envuelve dos int primitivas, x y y.

Así que cuando usted se mueve, puede utilizar:

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

    // Move yourself to this point 
    ... 
} 

En cuanto a aprender a realidad empleo el algoritmo, creo que es un poco el punto de su tarea, y no quiero echar a perder ¡tu diversión!

El artículo de Wikipedia sobre el algoritmo es bastante útil, aunque tengo la sensación de que sus notas de clase también lo ayudarán.

Dijkstra's algorithm on Wikipedia

Answer 3

Implementé el algoritmo mencionado por ccoakley. Encuentra debajo del código parcial para ayudarle en la dirección correcta:

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: añadido las partes que faltan

Answer 4

Puede basar su solución en algoritmos que se encuentran en "Introducción a los algoritmos" por Cormen, Leiserson, Rivest y Stein, 2da Edición. En el capítulo 24 analizan el algoritmo de "rutas más cortas de fuente única" y en 24.3 tiene Dijkstra.

Usaré el pseudo-código aquí. Puede reemplazar la cola de prioridad mínima a continuación con otra estructura de datos como un mapa en Java. No será rápido, pero funcionará y podría ser un primer intento satisfactorio. También tengo una implementación de Java de una cola de prioridad mínima si lo desea.

Digamos que tiene el laberinto representado por una matriz 2D como en su código: int [M] [N] laberinto. El primer índice es el índice de fila y el segundo es el índice de columna, basado en cero. Así, yendo de 0 a M-1 para las filas y de 0 a N-1 para las columnas. El valor laberinto [fila] [columna] representa el peligro asociado a la sala en (fila, columna).Necesitamos una representación conveniente para obtener el peso entre dos habitaciones en el laberinto y saber qué habitaciones están adyacentes a una habitación específica.

La idea es aplanar la matriz y poner a cada lado de la fila al lado del otro: fila1, fila2, ..., rowM. Entonces podemos dar un índice i a cada habitación. Para poder utilizar esta idea, necesitamos convertir entre diferentes tipos de coordenadas: (fila, columna) -> i e i -> (fila, columna).

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

Say SIZE es M * N, el número total de habitaciones en el laberinto.

Ahora podemos hacer una matriz de adyacencia que represente el laberinto con los valores de peligro: int [SIZE] [SIZE] adjacency_matrix, el primer índice es el FROM, el segundo es el TO. En una celda, encontramos el costo o el peso para ir de una habitación a otra. Tenga en cuenta que, dada una habitación específica, solo hay unas pocas habitaciones adyacentes a esa habitación. Las otras habitaciones en el laberinto no son accesibles desde esa habitación. Por convención, usaremos el número entero más grande para indicar eso y usar la INFINIDAD constante. Los otros valores representan peligro y oscilan entre 0 y 9. La matriz será escasa y existen técnicas para optimizarla.

Cuando tenemos una habitación ubicada en (r, c), ¿cuáles son las habitaciones contiguas? Queremos tener un vector de índices para usar directamente en nuestro algoritmo. Si no tomamos en cuenta los bordes del laberinto, tenemos: (r-1, c-1), (r-1, c), (r-1, c + 1), (r, c-1) , (r, c + 1), (r + 1, c-1), (r + 1, c) y (r + 1, c + 1). Podríamos aplicar convert_to_index a cada uno de ellos, verificar que estén en el rango 0..SIZE-1 e inicializar la matriz con eso. Por lo tanto, por ejemplo, ir de (r, c) a (r-1, c-1) tiene un costo o peligro de laberinto [r-1, c-1] y pasar de (r-1, c-1) a (r, c) tiene un costo de laberinto [r, c]. Pero pasar de (r, c) a otra habitación distante tiene un costo de 10, es inalcanzable y el inverso es verdadero.

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 

siguiente que necesitamos un vector estimaciones de estimaciones de la ruta más corta (CFR libro página 585.) Y un vector predecesores (Cfr libro de la página 584.).

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

ir desde el principio a los costes de puesta en 0.

estimates[0] := 0 

conjunto de inicialización de vértices que pertenecen al MST (árbol de expansión mínima)

mst := empty set 

La cola min prioridad q se inicializa

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 

El trabajo está hecho. Tenemos nuestro camino en predecessors con los costos en estimates.

Esto podría ser excesivo y A * podría ser mejor. Pero supongo que usar Dijkstra era un requisito de tu tarea. Si desea explorar A *, le sugiero que eche un vistazo a A* Pathfinding for Beginners y Amit’s A* Pages.