我有一个基于网格的图形，其中节点和边占据单元格。边可以交叉，但不能在同一方向上相互重叠。
假设我想优化图表，使边覆盖的距离最小化。 我目前正在对每个连接使用 A* 搜索，但该算法是贪婪的，没有提前计划。考虑下图，其中连接的顺序发生了变化(另请注意，任何给定边都可以有多个最短路径，请参见绿色和 紫色连接)。
我的直觉告诉我们这是 NP-Complete，需要进行详尽的搜索，随着图的大小增加，这将非常昂贵。然而，我无法证明这一点，它与通常涉及交叉最小化的其他图嵌入问题不太一样。
最佳答案
你没有真正描述你的问题，你的形象也不见了，但你的问题听起来像是最小的 T-join 问题。
最小 T 连接问题是在图 G 上定义的。给定一个偶数集 T，你试图找到该图的一个子图，其中 T 的顶点具有奇数度，而另一个顶点具有偶数度。您在边上设置了权重，并试图最小化子图中边的权重之和。
令人惊讶的是，最小 T 连接问题可以在多项式时间内解决，这要归功于与非二分匹配问题的密切联系。也就是说，如果你找到 T 的顶点之间的所有对最短路径，最小 T 连接是通过 T 中顶点的最小权重完美匹配获得的，其中两个顶点之间有一条边，其长度是最短路径的长度在 G.
最小的 T 连接将是路径的集合。如果两个不同的路径，比如 a->b 和 c->d，使用相同的边 uv，那么它们可以被替换为 a->u->c 和 b->v->d 并减少 T 的成本-加入。所以它不会两次使用相同的边缘。
关于algorithm - NP完全？具有特定约束的图的最佳图嵌入，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23961747/