La ruta más corta entre nodos en un gráfico se puede encontrar mediante varios algoritmos (Dikstra, A-star, etc.).¿Cuáles son las aplicaciones del algoritmo de ruta más corta?
Pero, ¿qué aplicaciones tiene este problema? (Ya sé bastantes, pero me gustaría ver muchos más ejemplos).
Por favor, solo conceda una solicitud/respuesta. Explique la aplicación y cómo se puede transformar en un problema de ruta más corta.
Dada una red de ordenadores (por ejemplo, una aplicación peer-to-peer), encontrar el camino más corto desde la máquina de A a B. máquina
SLaks, pero ¿por qué necesitaría una ruta más corta en una aplicación de igual a igual? – skanatek
En una aplicación peer-to-peer, las dos máquinas no están necesariamente conectadas usando una sola conexión. Todas las conexiones pasan por una puerta de enlace inicial y luego a través de muchos enrutadores intermedios o conmutadores, formando esencialmente una red. Aquí es donde viene el camino más corto algo. –
Dado un número de ciudades con las carreteras de conectarlos, encontrar el camino más corto de Nueva York a Chicago.
El tráfico y la longitud de las autopistas son ponderaciones de ruta.
Esto también se puede usar para varios juegos de computadora. – SLaks
En los videojuegos, estos algoritmos se utilizan con frecuencia para encontrar la ruta más corta entre dos puntos en un mapa. El "pathfinding", como se lo llama en este contexto, puede ser utilizado por AI para trazar rutas, o por el motor del juego para ayudar a los usuarios a trazar rutas.
Un ejemplo que puedo ver que probablemente se usa es en dispositivos de puntos preestablecidos que necesitan viajar a través de ciertos puntos con una cantidad específica de carga de la batería o combustible.
En el ejército tenemos ciertos vehículos/dispositivos aéreos no tripulados pequeños que tienen algún punto preestablecido que necesita explorar, y dado que debe viajar distancias muy grandes, en un dispositivo pequeño como ese sería demasiado costoso intentarlo para controlarlo por satélite, y el control de radio se deterioraría antes de llegar al punto más alejado. Ahí es donde el algoritmo entra en juego.
Simplemente configure algún punto que desee que lo explore y suéltelo. Permitiéndole encontrar el camino más corto recorrido para cubrir todos los puntos. No requiere herramientas importantes, por lo tanto, es más asequible y portátil.
Eso es un vendedor ambulante, no el camino más corto. – SLaks
ts es un problema de clase sp aunque –
¿Qué es un "problema de clase sp"? –
Red Social ... encontrar el camino más corto entre dos personas (grado de separación)
¡Esto suena muy interesante! Pero, ¿a qué se puede usar esto? – BlackBear
Usted sabe en linkedIn, ellos proveen que alguna persona es su 2nd Connection o 3rd Connection, there 2 es la ruta más corta entre usted y esa persona. –
Se muestra que cada pueblo en América está relacionado entre sí con 6 relación :) –
problema del camino más corto formar el fundamento de toda una clase de problemas de optimización que puede resolverse mediante una técnica llamada generación de columna. Los ejemplos incluyen problemas de enrutamiento de vehículos, problemas de diseño de redes de supervivencia, entre otros. En tales problemas hay un problema principal (generalmente un programa lineal) en el que cada columna representa una ruta (piense en una ruta en un problema de ruta del vehículo como una ruta candidata que un vehículo puede tomar, piense en una ruta en una red problema de diseño como una ruta posible a través de la cual un producto puede enviarse entre una fuente y un destino). El problema principal se resuelve repetidamente. Cada vez, utilizando las métricas de la solución, se resuelve un problema separado (llamado subproblema de generación de columnas). Este problema resulta ser un problema de ruta más corta (generalmente con restricciones laterales o longitudes de arco negativas que representan el problema NP-Hard). Si se obtiene una nueva ruta útil, se agrega al problema maestro original que ahora se vuelve a resolver en un subconjunto más grande de rutas que conduce a soluciones cada vez mejores (generalmente de costo más bajo).
Gracias, busqué en Google "generación de columnas" y encontré un libro sobre el tema ... – ragnarius
Los algoritmos de ruta más cortos se pueden usar para resolver word ladder puzzles.
Por ejemplo, cambiar la palabra "gato" en la palabra "perro" cambiando una letra a la vez - "gato", "bat", "bolsa", "pantano", "perro"
Hay una aplicación interesante, no directamente obvia, de los algoritmos de ruta más cortos que probablemente se usa con bastante frecuencia en el comercio algorítmico y en el sector financiero que trata de activos y bienes comerciales.
Imagine que puede convertir 1000 USD a 950 EUR y luego 950 EUR a 1020 CAD que convierte de nuevo a 1007 USD :) Simplemente convirtiendo de moneda a moneda puede ganar dinero.
Esta situación se denomina oportunidad de arbitraje. Esto se puede hacer con cualquier activo y entre diferentes mercados.
En este caso, las relaciones entre los activos se modelan como gráficos dirigidos ponderados y encontrar los llamados ciclos negativos en el gráfico es, de hecho, encontrar estas oportunidades de arbitraje.
se puede ver más detalles con buena explicación y ejemplos aquí: http://algs4.cs.princeton.edu/44sp/
El camino más corto es de uso frecuente en SNA (análisis de redes sociales) para calcular centralidad de intermediación entre otros. Por lo general, las personas con los enlaces más fuertes tienden a comunicarse a través del camino más corto. Saber en un gráfico el camino más corto entre las personas (nodos) puede hacerle saber enlaces fuertes ocultos. Puede descubrir muchas cosas interesantes en un gráfico simplemente calculando algunas métricas.
Puede encontrar su camino a casa con menos barras, y evitarlo. –