¿Cómo conectar dos puntos sin cruzar otra ruta?

Question

Supongamos que tengo la siguiente grilla. Tengo que conectar pares de letras. No solo se deben conectar las mismas letras, sino que también debo asegurarme de que las rutas de conexión no se crucen entre sí. ¿Cuál es el algoritmo que podría decirme si es posible conectar todos los pares sin cruzar las rutas y el camino más corto?

Me doy cuenta de que se trata de un problema de gráfico y que la parte más corta de la ruta se puede resolver con BFS. De lo que no estoy seguro es de los cruces.

+---+---+---+---+---+---+---+---+ 
    | A | | | B | | | | | 
    +-------------------------------+ 
    | | | | | | | | | 
    +-------------------------------+ 
    | | | B | | | | D | | 
    +-------------------------------+ 
    | | | | | | | | | 
    +-------------------------------+ 
    | | C | | | C | | | | 
    +-------------------------------+ 
    | | | | A | | | | | 
    +-------------------------------+ 
    | | | | | | | D | | 
    +-------------------------------+ 
    | | | | | | | | | 
    +---+---+---+---+---+---+---+---+ 

Answer 1

Este es un problema NP-completo llamado "Rutas de conexión disjuntas". Aparte de algún algoritmo súper polinomial (realmente lento), existen algunos algoritmos de aproximación (podría cometer un error o no ser óptimo).

• An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs - Jonas Kleinberg (pdf)