Si me preguntaras dónde comenzó mi obsesión por los viajes por carretera, tendría que decir que probablemente comenzó poco después de que mi esposa y yo condujéramos la I-40 desde Blacksburg, VA, hasta Albuquerque, NM, para comenzar mi primer trabajo después de graduarme. escuela. Quizás hubo algo en ver el paisaje cambiante y visitar nuevos lugares que encontré emocionantes. Aunque, para ser honesto, probablemente se deba a la compulsión de "terminar la ruta" y conducir el resto de la I-40 en ambos extremos. Me comprometeré y diré que fue un poco de ambos.
Inicialmente, mi fetiche de viajes por carretera se centró principalmente en viajar por las principales autopistas interestatales de EE. UU. (aquellas que terminaron en 0 o 5), ya que casi había terminado una. Sin embargo, mientras leía varios libros de viajes, descubrí que la comunidad de viajes por carretera tendía a descartar las carreteras interestatales como avenidas para el comercio y el "ajetreo" general, prefiriendo en cambio el ritmo más tranquilo y un poco más lento de las otras carreteras principales de Estados Unidos: la autopista de EE. UU. sistema. Trazar varias de estas carreteras desencadenó la emoción de nuevos lugares y paisajes. Mi nuevo sueño era viajar por todas las autopistas principales de EE. UU., es decir, todas aquellas con designaciones de dos dígitos que todavía estaban activas, con la única excepción de la autopista 101 en California.
The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)De lo que están hechos los sueños... (imagen de Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)
Desde que comencé mi puesto recientemente como probador estadístico de investigación en JMP , he aprendido más sobre el software de lo que nunca pensé posible. Me sorprendió lo rápido que aprendí JMP Scripting Language (aunque ciertamente todavía estoy aprendiendo JSL), lo que me abrió aún más posibilidades. Pero, una vez que descubrí que el arrastrar y soltar Generador de gráficos tenía la capacidad de trazar mapas?! Bueno, probablemente puedas adivinar a dónde va esto (si el título no fuera un claro indicio).
Después de superar mi entusiasmo inicial, hubo un momento de escepticismo. ¿Podría realmente trazar un viaje por carretera con Graph Builder? Sabía que podía trazar regiones, pero ¿qué pasa con las líneas y las carreteras? Bueno, estoy feliz de decir que, después de pasar quizás más tiempo del que quisiera admitir, ¡la respuesta es SÍ! No es Google Maps o AAA Trip Tik, pero creo que definitivamente vale la pena echarle un vistazo.
Establecer un camino
Entonces, la primera pregunta a responder fue ¿qué tipo de viaje por carretera iba a ser este? Bueno, mi sueño era viajar por todas las autopistas de los EE. UU., así que ¿por qué no hacer un viaje que hiciera precisamente eso? En concreto, el objetivo sería el siguiente:
Encuentre un camino a través del sistema de autopistas de EE. UU. que conecte todas las autopistas principales activas de EE. UU.
Si bien mi completista interno se resistiría a la posibilidad de no recorrer cada milla de pavimento que formaba una carretera en particular, se tuvo que hacer algún compromiso, y esto seguiría siendo un gran desafío en cualquier caso. Pero primero, algunas reglas básicas:
- El objetivo es viajar solo en las autopistas de EE. UU. tanto como sea posible. Es decir, me gustaría ir directamente de una autopista a otra sin tener que tomar una carretera que no sea una autopista en el medio cuando sea posible.
- La autopista debe estar actualmente activa (perdón, Route 66ers) y servir como miembro principal del sistema de autopistas (designación de dos dígitos, excepto 101)
- Cada carretera se recorrería una sola vez.
Parece bastante sencillo, ¿verdad? El primer paso fue compilar una base de datos de intersecciones de carreteras, mostrando qué carreteras se conectaban con otras carreteras y las ubicaciones de estas intersecciones. Pasé mucho tiempo tratando de encontrar una base de datos lista para usar, pero no tuve tanta suerte. Así que decidí hacer el mío en una tabla de datos.
Example of the process I used to get the coordinates for each intersection. A true labor of love.Example of the process I used to get the coordinates for each intersection. A true labor of love.Example of the process I used to get the coordinates for each intersection. A true labor of love.Example of the process I used to get the coordinates for each intersection. A true labor of love.Ejemplo del proceso que utilicé para obtener las coordenadas de cada intersección. Un verdadero trabajo de amor.
Vale la pena mencionar que muchas veces las carreteras se cruzan entre sí varias veces o incluso corren al mismo tiempo. Solo registré la primera intersección que ocurrió al seguir una carretera de norte o este a sur u oeste, dotando a mi red de un sesgo direccional inherente. De hecho, eso es exactamente lo que estaba construyendo: una red de "nodos" de autopistas de EE. UU. basada en sus "bordes" de intersección. Una vez que esta red estuviera completa, el objetivo sería encontrar un camino a través de la red que conectara cada nodo sin que ningún nodo se repitiera en el camino (si es posible).
Para aquellos familiarizados con la teoría de grafos, esto puede sonar como si estuviera trabajando con el famoso "problema del vendedor ambulante". Y casi tendrías razón. El viajante de comercio es en realidad un caso especial de lo que se conoce como camino hamiltoniano , que es una ruta que conecta todos los nodos sin repeticiones (que no debe confundirse con un camino euleriano , que es un camino que usa cada borde de la red sin repetición y está asociado con el famoso Problema del puente de Koenigsburg ). Lo que hace que el viajante de comercio sea un caso especial es el hecho de que los bordes tienen pesos (digamos, tiempo o distancia), por lo que existe la condición adicional de que el camino debe minimizar el peso total. Dato curioso: el camino hamiltoniano recibe su nombre de William Rowan Hamilton, quien estaba trabajando para encontrar un camino que conectara todos los vértices de un dodecaedro. En un momento, fingió que los vértices eran ciudades famosas y buscaba una “gira mundial”. Tengo la sensación de que nos hubiéramos llevado bastante bien.
Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Ejemplo tradicional de un camino hamiltoniano en un dodecaedro (imagen de Christoph Sommer publicada en Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)
¡Este camino hamiltoniano es exactamente lo que estaba buscando! Dado que era un objeto muy conocido, debería haber un algoritmo eficiente para encontrarlo, ¿verdad? Bueno, no tan rápido. Verá, el problema de encontrar un camino hamiltoniano a través de un gráfico arbitrario es lo que se llama un problema NP-difícil. Este es solo un término elegante para decir que es muy fácil verificar si una ruta es hamiltoniana, pero bastante difícil encontrar tal ruta para todas las excepciones. En otras palabras, no existe un algoritmo rápido general para encontrar un camino hamiltoniano para cada situación. Entonces, una vez más, me puse en marcha por mi cuenta para ver si podía desarrollar un algoritmo para mi caso.
Primero comencé por convirtiendo mi red en una matriz asociativa en JSL y luego investigué un algoritmo simple para encontrar un camino en una pequeña red escrito por un colega . Este algoritmo utiliza una búsqueda primero en profundidad, que implica comenzar en un nodo en la red y seguir la primera conexión que encuentre para cada nodo a partir de entonces hasta que se quede sin conexiones, momento en el que regresa a otro nodo que no se conecta y sigue adelante. Si bien este algoritmo no garantizaba una ruta hamiltoniana, descubrí que aún podía usarlo para tratar de acercarme. El algoritmo que derivé adaptando este enfoque es el siguiente:
Buscador de rutas casi hamiltonianas
- Proporcione un nodo inicial.
- Para cada nodo de conexión, ejecute una búsqueda en profundidad de un solo paso (es decir, no vuelva a subir una vez que se quede sin conexiones, incluso si se saltó algunas) y vea qué nodo tiene la ruta más larga.
- Agregue ese nodo de conexión a la ruta.
- Repita los pasos 2 y 3 hasta que no haya más nodos disponibles para agregar a la ruta.
La idea detrás de este algoritmo es que agregar nodos con la ruta potencial más larga debería, en teoría, acercarlo mucho más a una ruta general en toda la red al reducir el riesgo de que una ruta termine antes de tiempo.
Llenando los huecos
Ahora que puedo obtener una ruta inicial, el siguiente paso fue determinar cómo "injertar" los nodos faltantes que quedaron fuera de la ejecución inicial. Se me ocurrieron tres métodos posibles:
- Elija el primer nodo faltante, oblíguelo a conectarse a su conexión más temprana posible en la ruta actual y reinicie la búsqueda desde allí: Por supuesto, no tiene que elegir el primer nodo faltante (de hecho, puede que no haya necesariamente un "primer" nodo faltante), pero la idea sería la misma. Esencialmente, este enfoque "injerta" un nodo faltante en la ruta y luego finge que llegó a este punto durante la ejecución del algoritmo (la parte de reinicio). El único riesgo de este enfoque es que puede encontrarse atrapado en un bucle sin fin; Debido a las limitaciones del algoritmo de búsqueda básico, es posible que nunca llegue a una ruta que incorpore todos los nodos. Puede ajustar este enfoque al tratar de incluir más selecciones aleatorias en la búsqueda de ruta, pero aún no hay garantía de encontrar una ruta más rápido.
- Si solo falta un nodo, explore todas las combinaciones posibles para encajarlo en la ruta actual y devuelva el que lo hace con éxito: En esencia, este enfoque simplemente equivale a una búsqueda exhaustiva en todas las rutas posibles que incluyen el nodo que falta dado el diseño de la ruta actual. El único riesgo de este enfoque es que el nodo que falta tenga muchas conexiones; el número de posibilidades puede superar rápidamente los límites computacionales de su máquina. Es por eso que solo lo usé si el nodo faltante tenía menos de 10 conexiones. Por supuesto, también podría usar este enfoque si hay más de un nodo, pero cada uno tiene muy pocas conexiones.
- Use un poco de esfuerzo e ingrese manualmente los nodos que faltan en la ruta: Esto puede parecer una evasión, pero puede ser necesario y no necesariamente tan difícil si el algoritmo tiene dificultades para encontrar un camino. También es una buena manera de incorporar el juicio de expertos en el camino; tal vez se podría encontrar un camino más escénico con un poco de aporte humano que una solución puramente basada en computadora. El ejemplo perfecto del hombre y la máquina trabajando en armonía hacia un objetivo común.
Al buscar mi camino hamiltoniano, terminé usando cada uno de estos enfoques al menos una vez. En la próxima publicación , puedes ver los frutos de mi trabajo.
