java - programacion - Algoritmo eficiente para encontrar todos los caminos de la A a la Z?

libro de programacion en java netbeans pdf

Question

Con un conjunto de entradas aleatorias como esta (20k líneas):

A B
U Z
B A
A C
Z A
K Z
A Q
D A
U K
P U
U P
B Y
Y R
Y U
C R
R Q
A D
Q Z

Encuentra todos los caminos de la A a la Z.

1. A - B - Y - R - Q - Z
2. A - B - Y - U - Z
3. A - C - R - Q - Z
4. A - Q - Z
5. A - B - Y - U - K - Z

Una ubicación no puede aparecer más de una vez en la ruta, por lo tanto, A - B - Y - U - P - U - Z no es válida.

Las ubicaciones se denominan AAA a ZZZ (presentadas aquí como A - Z por simplicidad) y la entrada es aleatoria de tal manera que puede haber o no una ubicación ABC, todas las ubicaciones pueden ser XXX (poco probable) o no puede haber Un posible camino en todos los lugares está "aislado".

Inicialmente, pensé que esta es una variación del problema de la ruta más corta no ponderada, pero me parece bastante diferente y no estoy seguro de cómo se aplica el algoritmo aquí.

Mi solución actual es la siguiente:

1. Preprocese la lista de manera que tengamos un mapa hash que apunta una ubicación (izquierda) a una lista de ubicaciones (derecha)

2. Cree un mapa de hash para realizar un seguimiento de las "ubicaciones visitadas". Crear una lista para almacenar "rutas encontradas".

3. Almacene X (ubicación de inicio) en el hashmap "ubicaciones visitadas".

4. Busque X en el primer mapa hash, (la ubicación A nos dará (B, C, Q) en O (1) tiempo).

5. Para cada ubicación encontrada (B, C, Q), verifique si es el destino final (Z). Si es así, guárdelo en la lista de "rutas encontradas". De lo contrario, si no existe en el hashmap de "ubicaciones visitadas", vuelva al paso 3 ahora con esa ubicación como "X". (código real abajo)

Con esta solución actual, se tarda una eternidad en asignar todas las rutas posibles (no las más cortas) desde "BKI" a "SIN" para estos datos proporcionados .

Me preguntaba si hay una forma más efectiva (en el tiempo) de hacerlo. ¿Alguien sabe de un mejor algoritmo para encontrar todos los caminos desde una posición arbitraria A a una posición arbitraria Z?

Código actual para la solución actual:

import java.util.*;
import java.io.*;

public class Test {
    private static HashMap<String, List<String>> left_map_rights;

    public static void main(String args[]) throws Exception {
        left_map_rights = new HashMap<>();
        BufferedReader r = new BufferedReader(new FileReader("routes.text"));
        String line;
        HashMap<String, Void> lines = new HashMap<>();
        while ((line = r.readLine()) != null) {
            if (lines.containsKey(line)) { // ensure no duplicate lines
                continue;
            }
            lines.put(line, null);
            int space_location = line.indexOf('' '');
            String left = line.substring(0, space_location);
            String right = line.substring(space_location + 1);
            if(left.equals(right)){ // rejects entries whereby left = right
                continue;
            }
            List<String> rights = left_map_rights.get(left);
            if (rights == null) {
                rights = new ArrayList<String>();
                left_map_rights.put(left, rights);
            }
            rights.add(right);
        }
        r.close();
        System.out.println("start");
        List<List<String>> routes = GetAllRoutes("BKI", "SIN");
        System.out.println("end");
        for (List<String> route : routes) {
            System.out.println(route);
        }
    }

    public static List<List<String>> GetAllRoutes(String start, String end) {
        List<List<String>> routes = new ArrayList<>();
        List<String> rights = left_map_rights.get(start);
        if (rights != null) {
            for (String right : rights) {
                List<String> route = new ArrayList<>();
                route.add(start);
                route.add(right);
                Chain(routes, route, right, end);
            }
        }
        return routes;
    }

    public static void Chain(List<List<String>> routes, List<String> route, String right_most_currently, String end) {
        if (right_most_currently.equals(end)) {
            routes.add(route);
            return;
        }
        List<String> rights = left_map_rights.get(right_most_currently);
        if (rights != null) {
            for (String right : rights) {
                if (!route.contains(right)) {
                    List<String> new_route = new ArrayList<String>(route);
                    new_route.add(right);
                    Chain(routes, new_route, right, end);
                }
            }
        }
    }
}

Answer 1

Como entiendo su pregunta, el algoritmo Dijkstras no se puede aplicar tal como está, ya que el problema de la ruta más corta por definición encuentra una ruta única en un conjunto de todas las rutas posibles. Su tarea es encontrar todos los caminos per se.

Muchas optimizaciones en el algoritmo de Dijkstras implican cortar árboles de búsqueda con costos más altos. No podrá cortar esas partes en su búsqueda, ya que necesita todos los resultados.

Y supongo que te refieres a todos los caminos excluyendo círculos .

Algoritmo:

• Bombee la red en una matriz 2dim 26x26 de boolean / integer. fromTo [i, j]. Establecer un 1 / verdadero para un enlace existente.

• A partir del primer nodo, rastree todos los nodos siguientes (los enlaces de búsqueda para 1 / true).

• Mantener los nodos visitados en alguna estructura (matriz / lista). Como la profundidad máxima parece ser 26, esto debería ser posible a través de la recursión.

• Y como @soulcheck ha escrito a continuación, puede pensar en cortar los caminos que ya ha visitado. Puede mantener una lista de rutas hacia el destino en cada elemento de la matriz. Ajuste la condición de ruptura en consecuencia.

• Romper cuando

  • visitando el nodo final (almacenar el resultado)
  • al visitar un nodo que ha sido visitado antes (círculo)
  • visitando un nodo para el que ya ha encontrado todas las rutas al destino y fusione su ruta actual con todas las existentes desde ese nodo.

En cuanto al rendimiento, votaría en contra de usar hashmaps y listas y preferiría las estructuras estáticas.

Hmm, mientras releía la pregunta, me di cuenta de que el nombre de los nodos no se puede limitar a AZ. Está escribiendo algo sobre 20k líneas, con 26 letras, una red AZ completamente conectada requeriría muchos menos enlaces. Tal vez te saltes la recursión y las estructuras estáticas :)

Ok, con nombres válidos de AAA a ZZZ, una matriz sería demasiado grande. Así que mejor creas también una estructura dinámica para la red. Pregunta contraria: con respecto al rendimiento, ¿cuál es la mejor estructura de datos para una matriz menos popuplate como lo requeriría mi algoritmo? Yo voto por una ArrayList 2 dim. ¿Nadie?

Answer 2

Continuaría de forma recursiva donde construiría una lista de todas las rutas posibles entre todos los pares de nodos.

Comenzaría por construir, para todos los pares (X, Y), la lista L_2 (X, Y) que es la lista de rutas de longitud 2 que van de X a Y; es trivial de construir ya que esa es la lista de entrada que se te da.

Luego construiría las listas L_3 (X, Y), recursivamente, utilizando las listas conocidas L_2 (X, Z) y L_2 (Z, Y), repitiendo en Z. Por ejemplo, para (C, Q), tiene que intente todo Z en L_2 (C, Z) y L_2 (Z, Q) y en este caso Z solo puede ser R y obtiene L_3 (C, Q) = {C -> R -> Q}. Para otros pares, puede tener un L_3 vacío (X, Y), o puede haber muchos caminos de longitud 3 de X a Y. Sin embargo, debe tener cuidado al construir los caminos aquí, ya que algunos de ellos deben rechazarse porque ellos tienen ciclos Si una ruta tiene dos veces el mismo nodo, se rechaza.

Luego compila L_4 (X, Y) para todos los pares combinando todas las rutas L_2 (X, Z) y L_3 (Z, Y) mientras recorre todos los valores posibles para Z. Aún se eliminan las rutas con ciclos.

Y así sucesivamente ... hasta llegar a L_17576 (X, Y).

Una preocupación con este método es que puede quedarse sin memoria para almacenar esas listas. Sin embargo, tenga en cuenta que después de haber calculado las L_4, puede deshacerse de las L_3, etc. Por supuesto, no desea eliminar L_3 (A, Z), ya que esas rutas son rutas válidas de la A a la Z.

Detalle de la implementación: podría colocar L_3 (X, Y) en una matriz de 17576 x 17576, donde el elemento en (X, Y) es una estructura que almacena todas las rutas entre (X, Y). Sin embargo, si la mayoría de los elementos están vacíos (no hay rutas), en su lugar podría usar un HashMap<Pair, Set<Path>> , donde Pair es solo un objeto que almacena (X, Y). No me queda claro si la mayoría de los elementos de L_3 (X, Y) están vacíos, y si es así, si es también el caso de L_4334 (X, Y).

Gracias a @Lie Ryan por señalar esta question idéntica en mathoverflow. Mi solución es básicamente la de MRA; Huang afirma que no es válido, pero al eliminar las rutas con nodos duplicados, creo que mi solución está bien.

Supongo que mi solución necesita menos cálculos que el enfoque de fuerza bruta, sin embargo, requiere más memoria. Tanto que ni siquiera estoy seguro de que sea posible en una computadora con una cantidad razonable de memoria.

Answer 3

Lo que estás proponiendo es un esquema para DFS, solo con retroceso. Es correcto, a menos que quieras permitir rutas cíclicas (no especificaste si lo hiciste).

Sin embargo, hay dos trampas.

1. Debe vigilar los nodos que ya visitó en la ruta actual (para eliminar ciclos)
2. Debe saber cómo seleccionar el siguiente nodo cuando retroceda, para no descender en el mismo subárbol del gráfico cuando ya lo visitó en la ruta actual.

El pseudocódigo es más o menos como sigue:

getPaths(A, current_path) :
    if (A is destination node): return [current_path]
    for B = next-not-visited-neighbor(A) : 
        if (not B already on current path) 
            result = result + getPaths(B, current_path + B)
    return result 

 list_of_paths =  getPaths(A, [A])

que es casi lo que dijiste.

Sin embargo, tenga cuidado, ya que encontrar todas las rutas en una gráfica completa consume bastante tiempo y memoria.

Para aclarar, el algoritmo tiene una complejidad de tiempo de Ω (n!) en el peor de los casos, ya que tiene que enumerar todas las rutas de un vértice a otro en una gráfica completa de tamaño n, ¡y hay al menos (n-2)! rutas de la forma <A, permutaciones de todos los nodos excepto A y Z, Z>. No hay forma de hacerlo mejor si solo enumerar el resultado tomaría tanto.

Answer 4

Sus datos son esencialmente una lista de adyacencia que le permite construir un árbol arraigado en el nodo correspondiente a A. Para obtener todas las rutas entre A y Z, puede ejecutar cualquier algoritmo de recorrido de árbol.

Por supuesto, cuando estás construyendo el árbol tienes que asegurarte de no introducir ciclos.