通过障碍和空间约束最小化总路径成本

Question

我有一个节点网络排列在一个2D Grid.我想连接具有连接的节点对,然后占用2D网格上的物理空间.现在这些连接本身就是障碍,未来的连接将不得不走一条避免相交的路径.

我目前正在使用A* algorithm并逐步建立连接.虽然它找到从开始到结束节点的最短路径,但它不考虑需要进行的其他连接,因此连接所有对之后的总路径成本不是最佳的.

有谁知道是否有一种算法可以解决这个问题,或者这是一个NP完全问题？关于相关材料的任何指示也将受到赞赏.

Answer 1

看来您正在尝试找到 最小属图嵌入，其中您的节点是图顶点，所需的连接是其边。在您的情况下，最小属可以解释为所需的边交叉数量最少。寻找最小长度的连接变得更加困难（或者是吗？）

最小图属本身是 NP 完全的（特别是它的决策版本 - 一个图是否可以嵌入到小于 的属面中k）。因此，如果任务是找到一条交叉次数最少的路径，那么你的问题也将是 NP 困难的。

然而，如果您只考虑平面图，那么找到平面嵌入可以在线性时间内完成。