How to connect two points without crossing another path?

2018-06-03 03:28:06

Let's pretend I have the following grid. I have to connect pairs of letters. Not only the same letters have to be connected, but I must also make sure that the connecting paths don't cross each other. What's the algorithm that could tell me if it is possible to connect all the pairs without crossing paths and the shortest path?

I realize that this is a graph problem and the shortest path part could be solved using BFS. What I am not sure about is the crossing paths.

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

This is an NP-complete problem called "Disjoint Connecting Paths". Other than some super-polynomial algorithm (really slow), there are some approximation algorithms (might make a mistake, or is non-optimal).

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

链接地址: http://www.djcxy.com/p/10888.html

上一篇: 如何处理多个表并且不会获取重复的数据？（MySQL的/ PDO）

下一篇: 如何连接两点而不经过另一条路径？