2

是否有一种多项式算法可以找到无向网格图的生成树，从而最小化树中的匝数？转弯是当有两条边连接到一个顶点时，它们具有垂直的方向。

在这个问题中，我们在网格中有任意一组单元格，它们形成了一个连通图（不仅考虑了矩形）。

例如，给定一个 4 x 4 的网格图（见下图），我们希望在右侧（有 6 圈）而不是在左侧（有 14 圈）找到一棵生成树：

例子

关于近似算法的想法也可能有用。

4

1 回答 1

1

我会尝试整数编程（将下面的约束和目标转换为像GLPK这样的求解器接受的格式，让 GLPK 找出最佳解决方案）。

对于图的每个顶点v，最多有 15 个 0-1 变量

         x(v, ╵), x(v, ╶), x(v, └),

x(v, ╷), x(v, │), x(v, ┌), x(v, ├),

x(v, ╴), x(v, ┘), x(v, ─), x(v, ┴),

x(v, ┐), x(v, ┤), x(v, ┬), x(v, ┼),

如果每个变量描述v生成树中的连接，则每个变量为 1，否则为零。对于每条边vw，我们有一个 0-1 变量y(vw)，如果边存在则为 1。

目标是最小化

sum_{vertices v} (  x(v, └) +   x(v, ┌) +   x(v, ┘) +   x(v, ┐) +
                  2 x(v, ├) + 2 x(v, ┴) + 2 x(v, ┤) + 2 x(v, ┬) +
                  4 x(v, ┼)).

对于每个顶点v，我们都有一个约束

sum_{connections c} x(v, c) = 1,

因为只有一组连接。对于每条边vw，我们都有约束

sum_{connections c around v with vw} x(v, c) = y(vw),
sum_{connections c around w with vw} x(w, c) = y(vw),

编码两组变量之间的对应关系。

困难的约束是连通性约束。理论上，我们把它写成

for every subset S of vertices,
    sum_{edges vw such that v in S and w not in S} y(vw) >= 1,

即，每个切口至少有一个边缘穿过它，但实际上有很多这样的边缘，这是不好的。我可以想到解决这个问题的三种方法。从最简单到最难，

  1. 仅从上述约束开始，将实例求解到最优。检查解决方案是否与深度优先搜索相关。如果不是，添加相应的约束（例如，S是访问顶点的集合），并解决。

  2. n - 1通过添加表示任意顶点生成树的每条边的端点之间存在容量相关单元流的变量来制定连通性约束。如果你想试试这个，我可以详细说明。

  3. 与解决方案 1 类似，但我们在求解器内部找到了线性规划松弛的切口。这需要实现最大流（因为边缘变量可以具有介于 0 和 1 之间的任何浮点值）来找到最小切割的容量以及与 IP 求解器的挂钩。

我们不需要无周期约束。如果一个解包含一个环，那么我们总是可以通过删除一个环边来消除一个角，所以最优解是没有环的。

于 2018-08-03T13:01:51.537 回答