Es obvio que se usa en cosas como Google Maps, pero ¿cuáles son algunas aplicaciones más metafóricas en las que se minimiza el camino entre nodos (que pueden representar cualquier cosa)
Respuestas
¿Demasiados anuncios?
Jared
Puntos
3856
No estoy seguro de que esto sea "no obvio", pero se puede utilizar un algoritmo de camino más corto para resolver numéricamente cálculo de variaciones Problemas de valores límite (es decir, en los que se conocen los valores iniciales y finales). Esto puede hacerse, por ejemplo, creando una cuadrícula de puntos en 2D, por ejemplo:
La integral que se quiere minimizar es una integral de trayectoria que tiene la forma
$$ S = \int g(f, \dot{f}, t)dt $$
Se puede aproximar esta integral utilizando las aristas que conectan dos puntos de la cuadrícula. El peso de la arista es el valor aproximado de este trozo de la integral. Es decir, se estima el $\dot{f} \approx \frac{\Delta f}{\Delta t}$ y a continuación, conéctese a $g$ y aproximar la integral como $\int_t^{t + \Delta t} gdt \approx g\Delta t$ . Hay que introducir muchos nodos adicionales para crear aristas en muchas direcciones diferentes (desde cada nodo) para resolver el problema con precisión. Una vez que se tiene la configuración del grafo (los nodos y las aristas con su peso de arista), simplemente se resuelve el problema del camino más corto para encontrar la solución desde un nodo inicial hasta un nodo final (o se puede hacer un algoritmo de camino más corto de todos los pares para encontrar una solución más general).
Aquí hay un ejemplo real de cómo usar esto para encontrar un camino óptimo entre dos líneas poligonales usando algo muy similar a deformación temporal dinámica (en realidad se trata de un esquema DTW invariante). La primera solución requiere monotonicidad y la segunda no. Si no sabes nada de diagramas de espacio libre, las regiones blancas representan puntos (de ambas líneas) que están a menos de cierta distancia entre sí. Puedes ver que la solución no monótona tiende hacia el centro del espacio libre:
Si desea más información, puede leer Curve Matching, Time Warping y Light Fields: Nuevos algoritmos para calcular la similitud entre curvas (es un PDF). En él se explica todo esto con más detalle (y se presenta una medida invariante de la traslación).
Aviso:
Vale la pena señalar que este algoritmo falla para algunos problemas. En concreto, falla para los problemas en los que la solución es una sinusoide. Si se intenta aplicar este problema a un problema armónico (concretamente uno en el que la solución debería ser una sinusoide) falla estrepitosamente. En parte, esto se debe a que las soluciones periódicas no son tan fáciles de resolver en los problemas de valores límite. El problema con ellos es que los límites a menudo pueden dar lugar a muchos diferentes soluciones.
sewo
Puntos
58
El algoritmo de salto de línea en TeX funciona considerando un gráfico con cada potencial El salto de línea en un párrafo como un nodo y un borde entre dos nodos si hay una cantidad apropiada de texto (y cola, etc.) entre ellos para llenar una línea, ponderado por una puntuación de "demérito" estético para la línea potencial.
Para cada párrafo, TeX calculará el camino desde un punto de ruptura implícito al principio hasta un punto de ruptura al final del párrafo que incurra en una cantidad total mínima de "deméritos".
MJD
Puntos
37705
Una vez implementé un controlador de impresora que aceptaba diferentes formatos de entrada. La propia impresora era una Hewlett-Packard y requería la entrada en su formato propietario "PCL". El controlador de la impresora tenía un archivo de configuración que contenía líneas como ésta:
png -> pnm 0.8 pngtopnm %I > %O
Esto significa que una entrada en png puede convertirse en un formato pnm formato de entrada mediante el comando pngtopnm %I > %O y dicha conversión tiene una puntuación de calidad de 0,8.
El controlador de la impresora veía esto como una arista de longitud 0,8 en un gráfico dirigido. Dada una entrada en cualquier formato, calcularía el camino más corto hacia el pcl aplicar los comandos adecuados para convertir la entrada al formato PCL y enviar el resultado a la impresora.
naxa
Puntos
101
Este es un caso específico de la respuesta de JackofAll más arriba: Lo he visto utilizado en un contexto de diccionario de datos, donde los modelos de datos tienen un número de versión: se utilizó para encontrar el camino más corto de la versión x a la versión y, de modo que un automático script podría ser generado para agrupar los cambios del modelo de datos para mover un modelo de datos en la versión x a la versión y.
Magnus
Puntos
15064
Podemos describir de forma algo simplificada la posición de un coche de carreras en la pista como un conjunto de coordenadas 2D, una orientación y una velocidad. Estas se combinan en un vector 4D.
Dada una resolución finita para cada parámetro, podemos describir todas las posibles rutas del coche como un grafo dirigido entre dichos vectores 4D en el que cada nodo apunta hacia los nodos que son alcanzables en función de la entrada del conductor.
El El más corto en este gráfico es la ruta el más rápido ruta en la vía.
Para un uso práctico, probablemente querrás incluir más variables en la posición para describir la física con más precisión, y entonces tendrás que aplicar una fuerte optimización para conseguir un gráfico lo suficientemente pequeño para trabajar con él.
No resuelve automáticamente el problema, pero creo que sigue siendo beneficioso considerar el problema de la línea de carrera más rápida como otro problema de la ruta más corta que resulta tener lugar en un espacio vectorial de propiedades variadas.
