1

我正在解决一个问题，它有一个加权完全二分图（X，Y，XxY），其中 X 有 n 个节点，Y 有 m 个节点，n 小于 m。我想要一个完美的无交叉匹配图，这样在匹配集合 X 到集合 Y 时没有两条边交叉，并且 X 中的所有节点都在最后取。结果图的权重总和应该是最小的，我需要设计一个动态规划算法。我是这样想的：

X 和 Y 中的节点排列为 x0，xi 可以与 Y0、Yi 等具有水平边缘，但 Y 的节点比 X 多。对于 X (i) 中的每个节点，我考虑两个选项，即水平邻居，即 j in设置 Y 或对角线邻居 (i, j-1), (i,j+1) 并选择最小化成本的边。我跟踪 X 和 Y 中已经采用的节点。时间复杂度 O(纳米）

有没有更好的方法可以实现这一点。任何帮助表示赞赏。这是我在期中考试时遇到的一个问题，但我把它留给了选择。

4

1 回答 1

0

令为in和in 的w(x, y)节点之间的边权重，令为顶点和的解（最小交叉自由匹配图） ，其中和。xXyYM(i, j){x_0, x_1, ..., x_i} subset X{y_0, y_1, ..., y_j} subset Yi < |X|j < |Y|

例如M(0, j) = min( w(x_0, y_a) ) for 0 <= a <= j。M(i, i-1) = infinity因为当“正确”集较小时没有匹配。

因为i, j有两种可能：x_i连接y_j或不连接。由于该递归成立：

M(i, j) = min( w(i,j) + M(i-1, j-1), M(i, j-1) )
于 2014-03-06T11:00:55.187 回答