Làm thế nào để kết nối hai điểm mà không vượt qua một con đường khác?

Question

Giả sử tôi có lưới sau đây. Tôi phải kết nối các cặp chữ cái. Không chỉ các chữ cái giống nhau phải được kết nối, nhưng tôi cũng phải đảm bảo rằng các đường dẫn kết nối không giao nhau. Thuật toán nào có thể cho tôi biết nếu nó có thể kết nối tất cả các cặp mà không qua đường dẫn và đường đi ngắn nhất?

Tôi nhận thấy rằng đây là vấn đề về đồ thị và phần đường ngắn nhất có thể được giải quyết bằng BFS. Những gì tôi không chắc chắn về là những con đường băng qua.

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

Answer 1

Đây là sự cố NP-complete được gọi là "Đường dẫn kết nối rời rạc". Ngoài một số thuật toán siêu đa thức (thực sự chậm), có một số thuật toán xấp xỉ (có thể mắc lỗi hoặc không tối ưu).

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