LAPJVsp дает невероятные результаты при увеличении сокращения ряда - PullRequest
Новая
       130

LAPJVsp дает невероятные результаты при увеличении сокращения ряда

0 голосов
/ 13 июля 2020

В R. Jonker и A. Volgenant, Кратчайший алгоритм увеличения пути для плотных и разреженных задач линейного присваивания (doi: 10.1007 / BF02278710), авторы показывают, что реализация их алгоритма LAPJV, адаптированная для разреженных графиков и называемый LAPJVsp, хорошо справляется с различными проблемами.

A Pascal реализация LAPJVsp в настоящее время доступна здесь . Шаг сокращения увеличивающейся строки алгоритма в основном не изменился и отличается от кода, представленного в опубликованной статье, только использованием сжатого разреженного представления строки матрицы двойного сопряжения графа, индексы строк, индексы столбцов и веса которого относятся к как 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], и это также становится конечным результатом функции. , даже несмотря на то, что решение явно неосуществимо, так как нет края от третьей строки до второго столбца.

Это приводит к нескольким вопросам: Это хорошо известная ошибка? Можно ли доверять алгоритму в предоставлении правильных результатов при условии, что существует возможное решение, чтобы можно было просто предположить выполнимость и утверждать, что это не ошибка? Можно ли спасти шаг сокращения строки и либо обеспечить правильные результаты, либо выявить невозможность?

1 Ответ

1 голос
/ 13 июля 2020

Это происходит потому, что индекс столбца со второй по величине приведенной стоимостью для данной строки, то есть 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 остается нулевым вплоть до увеличения. Явная проверка этого обеспечивает тест на невозможность.

...