¿Qué algoritmo usaría para encontrar la ruta más corta de un gráfico, que está incrustado en un plano euclidiano, de modo que la ruta no contenga ninguna intersección propia (en la incrustación)?
Por ejemplo, en el gráfico a continuación, desea pasar de . Normalmente, un algoritmo como el algoritmo de Dijkstra produciría una secuencia como:
Gráfico completo:
Camino más corto:
La ruta no corta más corta:
Sin embargo, esta ruta se cruza en el plano euclidiano, por lo tanto, quiero un algoritmo que me dé la secuencia más corta que no se cruza, en este caso:
Esta ruta es más larga que la ruta más corta, pero es la ruta más corta sin intersección.
¿Existe un algoritmo (eficiente) que pueda hacer esto?
Fuentes TikZ
algorithms
graphs
shortest-path
graph-traversal
weighted-graphs
Ensalada Realz
fuente
fuente
Respuestas:
Es NP-complete incluso decidir si existe alguna ruta.
Es claramente posible verificar que cualquier ruta dada sea una ruta válida en el gráfico dado. Por lo tanto, el problema de longitud limitada está en NP, y también su subconjunto, el problema de cualquier ruta.
Ahora, para probar la dureza NP del problema de cualquier ruta (y, por lo tanto, del problema de longitud limitada), reduzcamos el SAT-CNF a este problema:
La estructura global es una cuadrícula de piezas de alambre unidas por una columna de piezas de cláusula. La fórmula lógica es satisfactoria si existe una ruta no intersectada a través del gráfico.
Es imposible cruzar dos partes del camino, pero es necesario cruzar dos cables lógicos. Más bien, el flujo de ruta está estrictamente dado: un punto de conexión está dado por dos nodos. La secuencia obliga a los puntos de cable a través de los cuales pasa el camino. La lógica está representada por el nodo elegido. Se puede elegir cualquier ruta siempre que pase por todos los puntos de conexión.
En este diagrama, la ruta está representada por la curva roja y el flujo lógico está representado por los cables negros:
Ahora construyamos cada componente.
El cableado utiliza tres mosaicos: el cruce, el punto de ramificación y el cable vertical. Comencemos con el más difícil:
La idea básica detrás del cruce es preparar un camino para cada par de puntos de cable y doblar los caminos posibles lo suficiente para que todos los pares, excepto los que codifican la misma lógica (caminos compatibles) se crucen entre sí. Por supuesto, no podemos decir que dos bordes paralelos se cruzan, sino que podemos introducir nodos adicionales de orden 2 para hacer que dos caminos se crucen.
Suponiendo que los caminos vienen de norte a oeste y de sur a este, podemos: recoger cada camino del norte con su camino compatible desde el este en una línea (algunos caminos incompatibles se cruzarán entre sí); cruzar cada par entre sí invirtiendo el orden de los pares; distribuir los caminos a sus puntos finales sur y oeste. Esto se explica mejor con un diagrama. Aquí, cada par de nodos representa un punto de conexión. Las rutas con el mismo código de color (que llevan la misma lógica) no se cruzan, las rutas con un código de color diferente sí:
El punto de ramificación y el cable vertical funcionan igual, pero hay menos caminos para correlacionar:
Es posible generalizar esta reducción para codificar un árbol arbitrario de compuertas AND y OR ramificando el cable de lectura de manera diferente. En particular, SAT-CNF y SAT-DNF son posibles de reducir al problema de la ruta de no intersección de la manera descrita anteriormente.
fuente
<sub>)?El problema parece fecharse en Turan 1944. Esto parece un buen estudio de teoría y algoritmos, el número cruzado de gráficos: teoría y computación de Mutzel. Wikipedia tiene alguna información debajo del número cruzado de gráficos
fuente