Geek Answers Handbook

How to connect two points without crossing another path?

Suppose I have the following grid. I need to combine pairs of letters. It is necessary to connect not only the same letters, but I also need to make sure that the connecting paths do not intersect with each other. Which algorithm could tell me if all pairs without intersecting paths and the shortest path can be connected?

I understand that this is a graph problem, and the shortest part of the path can be solved using BFS. What I'm not sure about is intersecting paths.

+---+---+---+---+---+---+---+---+ | A | | | B | | | | | +-------------------------------+ | | | | | | | | | +-------------------------------+ | | | B | | | | D | | +-------------------------------+ | | | | | | | | | +-------------------------------+ | | C | | | C | | | | +-------------------------------+ | | | | A | | | | | +-------------------------------+ | | | | | | | D | | +-------------------------------+ | | | | | | | | | +---+---+---+---+---+---+---+---+
+7
source share
1 answer

This is an NP-complete problem called Non-Crossing Connecting Paths. In addition to some super-polynomial algorithm (very slow), there are some approximation algorithms (may be an error or non-optimal).

+3
source

More articles:


All Articles