有效地解决有约束的分配问题

Question

我有一个变化的https://en.wikipedia.org/wiki/Assignment_problem#Unbalanced_assignment:

• 顶点集A和T的二部图，
• 边缘的非负成本，
• A和T中的所有顶点在匹配中最多只能出现一次。

但有以下修改:

1. 匹配中的边不能相交，即当a中的顶点a_i和T中的顶点t_j在图的两边按某指标值排序时，当a_(i_2)和t_(j_1)与i_1 &lt同时存在时，匹配中a_(i_1)和t_(j_2)不能连通;I_2和j_1 <j_2。>
2. 同样，对于较小的二部图顶点集，不需要分配所有顶点，即最优匹配可能只包含1条边，当它具有极端代价时。
3. 我们没有为查找匹配的大小提供常数s。
4. 想要最大化分配的边成本总和。

如何最有效地解决这个问题?

线性规划似乎效率不高。

该问题也可以表述为具有顶点v_(i,j)的最短路径问题，当a_i和t_j在原始二部图中连接时，附加源和汇，以及上述修改1 &2人满意。这个还有|A|!*|T|!这也会导致高运行时间。从v(i_1,j_1)到v(i_2,j_2)这条边的代价应该被设为减去原始二部图中从a_(i_2)到t(j_2)这条边的代价，所以我们复制了很多次代价值。

是否存在更有效的最短路径变体，其代价是在顶点上而不是在边上?

或者https://en.wikipedia.org/wiki/Hungarian_algorithm是否可以根据上述修改1进行修改?对于修改2和3，我看到了一个简单的方法，通过添加值为0的行和列来获得平衡分配问题，修改4应该只是负成本函数。

Answer 1

根据@MattTimmermans的提示，我最终采用了以下动态规划方法(这是对二部图和动态规划的修改):

设w(a, t)为A中节点a和T中节点t之间的边权值，设M(i, j)为顶点{a_0, a_1, ..., a_(i-1)} subset A和{t_0, t_1, ..., t_(j-1)} subset T的解(无相交边的最大代价匹配图)，其中0 <= i < |A|和0 <= j < |T|。对于i = 0和j = 0，顶点子集为空，即在矩阵M前面加1行1列。

for i in 0...|A|
for j in 0...|T|
if (i == 0 and j == 0)
M(i,j) = {cost: 0, step_type: null}
else
candidates = []
if (i >= 1 and j >= 1)
// subtract indexes in w(...) because of prepended artificial row and column in M
candidates.add({cost: M(i-1, j-1)[:cost] + w(i-1,j-1), step_type: 'right-down'})
end
if (i >= 1)
candidates.add({cost: M(i-1, j)[:cost], step_type: 'down'})
end
if j >= 1
candidates.add({cost: M(i, j-1)[:cost], step_type: 'right'})
end
M(i,j) = candidates.argmax(|map| map[:cost])
end
end
end

然后每一步根据step_type从M(|A|,|T|)往回走，直到我们到达M(0,0)。这给出了一个最佳匹配边的列表(以相反的顺序)。