LAPJVsp在扩充行缩减过程中产生不可行的结果

Question

在R.Jonker和A.Volgenant的《稠密和稀疏线性分配问题的最短增广路径算法》(doi:10.1007/BF022787710(中，作者证明了他们的LAPJV算法的实现，适用于稀疏图，称为LAPJVsp，在各种问题上都表现良好。

LAPJVsp的Pascal实现目前在这里可用。该算法的扩充行缩减步骤基本上没有变化，与已发表论文中提供的代码的不同之处仅在于使用图的双邻接矩阵的压缩稀疏行表示，其行索引、列索引和权重分别称为first、kk和cc：

tel:=0;
repeat
h:=1; l0:=l; l:=0;
while h<=l0 do
begin
i:=free[h]; h:=h+1; v0:=inf; vj:=inf;
for t:=first[i] to first[i+1]-1 do
begin
j:=kk[t]; dj:=cc[t]-v[j];
if dj<vj then if dj>=v0 then begin vj:=dj; j1:=j end
else begin vj:=v0; v0:=dj; j1:=j0; j0:=j end;
end;
i0:=y[j0]; u[i]:=vj;
if v0<vj then v[j0]:=v[j0]-vj+v0
else if i0>0 then begin j0:=j1; i0:=y[j0] end;
x[i]:=j0; y[j0]:=i;
if i0>0 then
if v0<vj then begin h:=h-1; free[h]:=i0 end
else begin l:=l+1; free[l]:=i0 end
end;
tel:=tel+1
until tel=2;

现在，对于稀疏输入，无法保证线性分配问题的可行解存在，在许多情况下，这种不可行性可以在过程中被发现，但上面给出的行缩减步骤忽略了这个问题，在某些情况下输出不可行的结果，然后一直存在到函数的末尾。

例如，考虑双邻接矩阵为[[1, 1, 1], [*, *, 1], [*, *, 1]]的二分图，其中*表示缺失边。这可以通过Pascal实现来运行，如下所示：

n:=3;
first[1]:=1; first[2]:=4; first[3]:=5; first[4]:=6;
kk[1]:=1; kk[2]:=2; kk[3]:=3; kk[4]:=3; kk[5]:=3;
cc[1]:=1; cc[2]:=1; cc[3]:=1; cc[4]:=1; cc[5]:=1;
zlap:=lap(x, y, u, v);

行缩减后，列分配x变为[1, 3, 2]，这也最终成为函数的最终结果，尽管该解决方案显然不可行，因为从第三行到第二列没有边。

这就引出了几个问题：这是一个众所周知的bug吗？假设存在可行的解决方案，那么算法是否可以提供正确的结果，这样人们就可以假设可行性并辩称这不是错误？行缩减步骤是否可以挽救并提供正确的结果，或检测不可行性？

Answer 1

之所以会发生这种情况，是因为给定行的降低成本第二高的列的索引，即j1，在不同的行之间永远不会取消设置。我们通过显式取消设置索引来消除错误：

...
tel:=0;
repeat
h:=1; l0:=l; l:=0;
while h<=l0 do
begin
j0:=0; j1:=0;  {<-- This is new}
i:=free[h]; h:=h+1; v0:=inf; vj:=inf;
...

在这一点上，有可能(正如原始文章中给出的例子的情况一样(给定行的dj的值都不小于inf，这意味着j0在增加之前保持为零。对此进行显式检查提供了一个不可行性测试。