我有一个布置在2D Grid. 我想用连接将节点对连接起来，然后占用 2D 网格上的物理空间。这些连接现在本身就是障碍，未来的连接将不得不采取避免与它们相交的路径。
我目前正在使用A* algorithm并逐渐建立连接。虽然它找到了从开始到结束节点的最短路径，但它没有考虑需要建立的其他连接，因此连接所有对后的总路径成本不是最优的。
有谁知道是否有一种算法可以解决这个问题，或者这是一个 NP 完全问题？任何有关相关材料的指导也将不胜感激。
问问题
196 次
1 回答
0
似乎您正在尝试找到 最小属图嵌入，其中您的节点是图顶点，所需的连接是它的边。在您的情况下，最小的属可以解释为所需的最小数量的边缘交叉。寻找最小长度的连接变得更加困难（或者是吗？）
最小图属本身是 NP 完全的（特别是它的决策版本 - 是否可以将图嵌入到小于 的属的表面中k）。因此，如果任务是找到这样一条具有最少交叉点的路径，那么您的问题也将是 NP 难的。
但是，如果您只考虑平面图，则可以在线性时间内找到平面嵌入。
于 2014-02-06T23:16:03.157 回答