Jak połączyć dwa punkty bez przekraczania innej ścieżki?

Question

Udawajmy, że mam następującą siatkę. Muszę połączyć pary liter. Nie tylko te same litery muszą być połączone, ale muszę też upewnić się, że ścieżki łączące się nie krzyżują. Jaki algorytm może mi powiedzieć, czy możliwe jest połączenie wszystkich par bez przecinania ścieżek i najkrótszej ścieżki?

Zdaję sobie sprawę, że jest to problem graficzny, a najkrótsza część ścieżki może zostać rozwiązana za pomocą BFS. Nie jestem pewien, co to są ścieżki skrzyżowania.

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

Answer 1

Jest to problem NP-zupełny o nazwie "Rozłączne ścieżki łączące". Oprócz jakiegoś super-wielomianowego algorytmu (naprawdę wolnego), istnieją pewne algorytmy aproksymacyjne (mogą być błędne lub nieoptymalne).

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