如何連接兩點而不穿越另一條路徑？

Question

讓我們假裝我有以下網格。我必須連接字母對。不僅必須連接相同的字母，還必須確保連接路徑不會相互交叉。有什麼算法可以告訴我，如果可以連接所有的線對而不穿越路徑和最短路徑？

我意識到這是一個圖形問題，可以使用BFS解決最短路徑部分。我不確定的是交叉路口。

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

Answer 1

這是一個名爲「Disjoint Connecting Paths」的NP完全問題。除了一些超多項式算法（真的很慢）以外，還有一些近似算法（可能會犯錯或者不是最優）。

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