Ошибки в Разреженном Алгоритме LAPJVsp и Их Устранение: Анализ и Подходы к Решению

Delphi , Синтаксис , Математика

В данной статье мы рассмотрим проблему, возникшую в алгоритме LAPJVsp, предназначенном для решения задачи линейного назначения (linear assignment problem) в случае разреженных графов. Алгоритм LAPJV, разработанный Jonkerом и Volgenантом, был адаптирован для работы с разреженными графами и представлен как 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;
     // ...
  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], и этот результат сохраняется до конца работы функции, несмотря на то, что решение явно недопустимо, так как нет ребра из третьей строки во второй столбец.

Анализ и Устранение Проблемы

Ошибка возникает из-за того, что индекс столбца со вторым по величине уменьшенным стоимостью для данной строки, то есть j1, не сбрасывается между различными строками. Чтобы устранить ошибку, необходимо явно сбросить индексы:

...
tel:=0;
repeat
   h:=1; l0:=l; l:=0;
   while h<=l0 do
   begin
      j0:=0; j1:=0;  {<-- Это новое условие}
      i:=free[h]; h:=h+1; v0:=inf; vj:=inf;
...

На этом этапе возможно, что для данной строки нет значения dj, меньше inf, что означает, что j0 остается равным нулю до моментаaugmentation. Явное проверка этого предоставляет тест на недопустимость.

Заключение

В данной статье мы рассмотрели проблему, связанную с алгоритмом LAPJVsp, и предложили способ её устранения. Важно понимать, что при работе с разреженными графами необходимо учитывать возможность отсутствия допустимого решения, и алгоритм должен быть адаптирован для корректной обработки таких случаев.

Подтвержденный ответ

Ошибка устранена путем явного сброса индексов столбцов со вторым по величине уменьшенным стоимостью, что позволяет алгоритму корректно обрабатывать ситуации, когда допустимого решения нет. Добавление проверки на недопустимость позволяет алгоритму корректно завершать работу без выдачи результатов.

Создано по материалам из источника по ссылке.

В данном описании 'Context' рассматривается проблема возникновения ошибок в алгоритме LAPJVsp для решения разреженных задач линейного назначения и предлагается подход к их устранению.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Математика ::