Олександр Рудик

Розв'язання задачі про призначення

Задача 1. Задано дві скінчені множини J і K з однаковою кількістю елементів і матрицю A, елементи якої мають індекси з J і K. Потрібно знайти взаємно однозначну відповідність fJ → K, при якій сума емементів aj f ( j ) за всіма j з J найменша.

Зауваження 1. Зауважимо таке.

  1. При відображенні g : K → J , оберненому до f , вказана в умові задачі сума дорівнює сумі за всіма k з K елементів ag(kk .

  2. Розв'язок, тобто відображення f , зберігається при додаванні довільної сталої до всіх елементів будь-якого рядка чи стовпчика матриці A .

  3. Розглянемо випадок, коли всі елементи матриці A невід'ємні. Побудуємо дводольний граф (J, K, E0) , у якому вершини j та k сполучено ребром тоді й лише тоді, коли ajk = 0. Якщо у побудованому графі є повна сполука пар, то вона задає розв'язок задачі про призначення.

Автор і походження назви. Американський математик Х.Кун (Harold D. Kuhn) вперше запропонував так званий угорський метод розв'язання цієї задачі. Він використовував теорію сполук пар, відому йому з робіт угорських учених Д.Кеніґа та Е.Еґеварі, тому й назвав метод угорським.

Угорський алгоритм Куна (Kuhn)

  1. Зведення рядків матриці. Для кожного рядка матриці A:

    • визначаємо найменший елемент у вибраному рядку;

    • кожний елемент вибраного рядка зменшуємо на знайдений найменший елемент рядка.

    Перетворена таким чином матриця міститиме нуль (можливо, не один) у кожному рядку.

  2. Зведення стовпчиків матриці. Для кожного стовпчика матриці A:

    • визначаємо найменший елемент у вибраному стовпчику;

    • кожний елемент вибраного стовпчика зменшуємо на знайдений найменший елемент стовпчика.

    Перетворена таким чином матриця міститиме нуль (можливо, не один) у кожному стовпчику.

  3. Побудова максимальної сполуки пар дводольного графа (J, K, E), у якому вершини j та k сполучено ребром тоді й лише тоді, коли ajk = 0.

  4. Знаходимо J1 та K1 — відповідно множини усіх вершин з J та K, що ненасичені сполукою пар, побудованою на попередньому кроці. Якщо ці множини непорожні, тобто побудована сполука пар неповна, то робимо таке збільшення кількості нулів матриці:

    • дводольний граф (J, K, E) перетворимо на орієнтований, спрямувавши дугу з K до J, якщо її кінці є елементами однієї пари, і спрямувавши дугу з J до K в іншому випадку;

    • знайдемо вершини, досяжні у побудованому орієнтованому графі з множини J1. Ці вершини належать до однієї з двох множин J2 та K2, що є відповідно підмножинами J та K. Маємо:

      • J1 — підмножина J2, бо її досягають за нуль кроків, рухаючись дугами орієнтованого графа;

      • K2 — підмножина K \ K1, інакше в орієнтованому графі існує маршрут непарної довжини, у якому:

        • на непарних місцях розташовано дуги, побудовані за ребрами, що не належать до сполуки пар;

        • на парних місцях розташовані дуги, побудовані за ребрами, що належать до сполуки пар;

        • початкова й кінцева вершини не насичені сполукою пар.

        У цьому випадку кількість ребер сполуки пар можна збільшити щонайменше на 1, що суперечить твердженню про її максимальність;

      • K1 — підмножина K \ K2 (наслідок попереднього зауваження);

      • якщо ajk = 0, то j належить до J \ J2 або k належить до K2, причому вказані дві умови несумісні;

      • якщо j належить до J2 і k належить до K \ K2, то ajk > 0;

    • знаходимо додатне число amin — найменший елемент ajk при:

      • j з J2 (остання множина непорожня, бо містить непорожню J1 як підмножину);

      • k з K \ K2 (остання множина непорожня, бо містить непорожню К1 як підмножину);

    • до всіх елементів стовпчиків k з K2 додаємо amin;

    • від усіх елементів рядків j з J2 віднімаємо amin;

    • після збільшення кількості нульових елементів матриці внаслідок виконання двох останніх кроків (нулі матриці, що існували до виконання двох останніх кроків, залишаються нулями, але з'явиться щонайменше один новий нуль) переходимо до виконання пункту 3 даного алгоритму.

Необмежуючи загальності міркувань (інакше потрібно перенумерувати елементи J і K відповідним чином), можна вважати, що перші | J2 | елементів множини J належать до J2, а останні | K2 | елементів множини K належать до K2.
      Унаочнимо крок збільшення кількості нульових елементів матриці у цьому випадку такою таблицею.

Таблиця 1
Збільшення кількості нульових елементів матриці

K \ K2K2
J2amin
J \ J2 + amin
Коментар до Таблиці 1

  1. Ліворуч вказано область значень індексу j з множини J;

  2. Вгорі вказано область значень індексу k з множини K;

  3. Світлосірим тлом позначено додатні елементи матриці, серед яких вибирають найменший елемент aminj ∈ J2, k ∈ K \ K2). Внаслідок зменшення на amin хоча б один з них перетворюють на 0.

  4. Білим тлом позначено елементи матриці, які можуть дорівнювати нулю і які залишають тими самими при перетворенні:

    • або з ними нічого не роблять взагалі (лівий нижній кут, j ∈ J \ J2, k ∈ K \ K2);

    • або їх збільшують, а потім зменшують на amin (правий верхній кут, j ∈ J2, k ∈ K2).

  5. Темносірим тлом позначено додатні елементи матриці, які збільшують на amin ( j ∈ J \ J2, k ∈ K2).

Подамо приклад програми мовою Turbo Pascal 7.0, що використовує описаний алгоритм для невід'ємних цілих чисел у межах базового типу змінних word.

{$N+}
const
  filein ='HUNGAR.DAT';  {Вхiдний файл}
  fileout='HUNGAR.RES'; {Вихiдний файл}
    n_max=205; {Верхня межа розмiру матрицi}
type  num=word;      {Тип елементiв матрицi}
    linen=array[1..n_max] of num;
    linew=array[0..n_max] of word;
   plinen=^linen;
   plinew=^linew;
  matrixn=array[1..n_max] of plinen;
  matrixw=array[1..n_max] of plinew;
   labels=array[0..n_max] of boolean;
    chain=array[0..n_max*2] of word;
var a:^matrixn;                 {Матриця A}
   k0,            {Данi про нулi матрицi A:
    k0[j.0] - кiлькiсть елементiв a[j,k]=0;
    k0[j.k] при k=1, 2, ... , k0[j.0] -
           номери вiдповiдних стовпчикiв k}
   j0:^matrixw;   {Данi про нулi матрицi A:
    j0[k.0] - кiлькiсть елементiв a[j,k]=0;
    j0[k.j] при j=1, 2, ... , j0[k.0] -
                 номери вiдповiдних рядкiв}
    c,            {Граф M-змiнних ланцюгiв}
   nc,     {Вказiвник на масив даних с про
      граф найкоротших М-чергових ланцюгiв}
 newc:^chain;            {M-змiнний ланцюг}
   jp,      {Номер вiдповiдного елемента J}
   kp:^linew;                          { K
               для побудованої сполуки пар.
       0, якщо елемент вiдповiдно з K чи J
                 не входить до сполуки пар}
j2,k2,         {Належнiсть до множин J2,K2}
        {При побудовi М-чергового ланцюга:}
usedj,              {використано вершину J}
usedk,              {використано вершину K}
stop:^labels;                             {
stop[k] -iснування М-чергового ланцюга:
      при k = 0 - взагалi;
      при k > 0 - з кiнцем у вершинi k з K}

 done: boolean;     {Побудовано М-черговий
                    з вибраним закiнченням}
  min: num;             {Найменший елемент}
    n,     {Кiлькiсть: рядкiв (стовпчикiв)}
    np,                     {пар у сполуцi}
    j,                       {Номер: рядка}
    k,                          {стовпчика}
    nm,  {Максимальна кiлькiсть М-чергових
               ланцюгiв без спiльних точок}
    i,    {Збiльшений на 1 рiвень побудови
     графа найкоротший М-чергових ланцюгiв}
    im,     {Кiлькicnm вершин найкоротшого
                       М-чергового ланцюга}
    ip,{На скiльки збiльшено кiлькiсть пар}
    l,m: word;                 {Лiчильники}
    o: text;                   {Файл даних}
  sum: extended;     {Шукана найменша сума}

 {Побудова найкоротшого М-чергового ланцюга}
procedure getchain (i,l : word);
             var m,ii,ll: word;       BEGIN
case i mod 2 of
     0: if usedk^[c^[l]] then exit;
     1: if usedj^[c^[l]] then exit end;
newc^[i]:=c^[l];
if i=1 then                           begin
        {Збiльшення кiлькостi пар на 1}
  for m:=1 to im do case m mod 2 of 0:begin
       usedk^[newc^[m]]:=true;
          jp^[newc^[m]]:=newc^[m-1]     end;
                                    1:begin
       usedj^[newc^[m]]:=true;
          kp^[newc^[m]]:=newc^[m+1] end end;
  done:=true;  inc(np);  inc(ip)        end
  else{Пошук невiдомого кiнця ланцюга}begin
  ii:=i-1;
  ll:=nc^[ii-1];
  repeat inc(ll); case i mod 2 of
   0: if a^[c^[ll]]^[c^[l]]=0
                   then getchain(ii,ll);
   1: if a^[c^[l]]^[c^[ll]]=0
                   then getchain(ii,ll) end;
   until done or (ll=nc^[ii])       end END;
                                      BEGIN
new(c);   new(nc);  new(newc);   new(stop);
new(j0);  new(jp);  new(usedj);  new(j2);
new(k0);  new(kp);  new(usedk);  new(k2);
new(a);           {Зчитування вхiдних даних}
assign(o,filein);   reset(o);    read(o,n);
                     for j:=1 to n do begin
     new(a^[j]);  new(j0^[j]);  new(k0^[j]);
     for k:=1 to n do read(o,a^[j]^[k]) end;
close(o);
nc^[0]:=0;
                {1. Зведення рядкiв матрицi}
for j:=1 to n do                      begin
  min:=a^[j]^[1];
  for k:=2 to n do if   min >a^[j]^[k]
                   then min:=a^[j]^[k];
  if min>0 then for k:=1 to n do
               a^[j]^[k]:=a^[j]^[k]-min end;

            {2. Зведення стовпчикiв матрицi}
for k:=1 to n do                      begin
  min:=a^[1]^[k];
  for j:=2 to n do if   min > a^[j]^[k]
                   then min :=a^[j]^[k];
  if min>0 then for j:=1 to n do
               a^[j]^[k]:=a^[j]^[k]-min end;

      {3. Побудова максимальної сполуки пар}

REPEAT      {Визначення нульових елемментiв}
                     for j:=1 to n do
                     for k:=0 to n do begin
                          j0^[j]^[k]:=0;
                          k0^[j]^[k]:=0 end;
for j:=1 to n do
for k:=1 to n do if a^[j]^[k]=0 then  begin
inc(j0^[k]^[0]); j0^[k]^[j0^[k]^[0]]:=j;
inc(k0^[j]^[0]); k0^[j]^[k0^[j]^[0]]:=k end;

                      {Побудова сполуки пар}
np:=0;               for j:=1 to n do begin
                              jp^[j]:=0;
                              kp^[j]:=0 end;
for k:=1 to n do
if (j0^[k]^[0]>0) and (jp^[k]=0) then begin
 l:=0;
 repeat inc(l);
  until (kp^[j0^[k]^[l]]=0)or(l=j0^[k]^[0]);
     if (kp^[j0^[k]^[l]]=0) then      begin
                        jp^[k] :=j0^[k]^[l];
                    kp^[jp^[k]]:=k;
                        inc(np)     end end;

  {Власне побудова максимальної сполуки пар
           за допомогою М-чергових ланцюгiв}
repeat               for l:=0 to n do begin
                        stop^[l]:=false;
                       usedj^[l]:=false;
                       usedk^[l]:=false end;
                {Побудова графа найкоротших}
  i :=1;               {М-чергових ланцюгiв}
  ip:=0;
  nc^[1]:=0;               {Нульовий рiвень}
  for j:=1 to n do
  if (kp^[j]=0)and(k0^[j]^[0]>0) then begin
                         inc(nc^[1]);
                          c^[nc^[1]]:=j end;
  repeat
    inc(i);                {Непарний рiвень}
    nc^[i]:=nc^[i-1];
    for  m:=nc^[i-2]+1 to nc^[i-1] do begin
    j:=c^[m];
    for l:=1 to k0^[j]^[0] do
     if kp^[j]<>k0^[j]^[l] then       begin
     inc(nc^[i]);
      c^[nc^[i]]:=k0^[j]^[l];
     stop^[k0^[j]^[l]]:=
     stop^[k0^[j]^[l]]or(jp^[k0^[j]^[l]]=0);
     stop^[0]:=stop^[0] or stop^[k0^[j]^[l]]
                                    end end;
    if not stop^[0] and (nc^[i-1] < nc^[i])
                                 then begin
      inc(i);                {Парний рiвень}
      nc^[i]:=nc^[i-1];
      for m:=nc^[i-2]+1 to nc^[i-1] do
      if jp^[c^[m]]>0 then            begin
            inc(nc^[i]);
             c^[nc^[i]]:=jp^[c^[m]] end end
  until stop^[0] or (nc^[i]=nc^[i-1]);

  if stop^[0] and (i>=4) then         begin
  {Збiльшення кiлькостi пар з використанням
                        М-чергових ланцюгiв}
  im:=i;
  for m:=nc^[im-1]+1 to nc^[im] do
                 if stop^[c^[m]] then begin
                      done:=false;
                      getchain(i,m) end end
until (ip=0) or (np=n);

     {4. Збiльшення кiлькостi нулiв матрицi}
if np < n                        then BEGIN
                     for j:=1 to n do begin
                          j2^[j]:=false;
                          k2^[j]:=false end;
nc^[1]:=0;  i:=1;
for j:=1 to n do    {Знаходження множини J1}
if (k0^[j]^[0]=0) or
   (k0^[j]^[0]>0) and (kp^[j]=0) then begin
                          inc(nc^[i]);
                           c^[nc^[i]]:=j;
                           j2^[j]:=true end;
repeat
   inc(i);        {Знаходження пiдмножини K2}
   nc^[i]:=nc^[i-1];
   for  l:=nc^[i-2]+1 to nc^[i-1] do
         if 0 < k0^[c^[l]]^[0] then
   for m:=1 to  k0^[c^[l]]^[0] do
   if  not  k2^[k0^[c^[l]]^[m]] and
   (kp^[c^[l]]<glt;k0^[c^[l]]^[m])  then begin
                inc(nc^[i]);
                 c^[nc^[i]]:=k0^[c^[l]]^[m];
             k2^[c^[nc^[i]]]:=true      end;
   if nc^[i]>nc^[i-1]            then begin
       inc(i);   {Знаходження пiдмножини J2}
       nc^[i]:=nc^[i-1];
       for l :=nc^[i-2]+1 to nc^[i-1] do
       if     (jp^[c^[l]]>0) and
       not j2^[jp^[c^[l]]]       then begin
                 inc(nc^[i]);
                  c^[nc^[i]]:=jp^[c^[l]];
              j2^[c^[nc^[i]]]:=true end end
until nc^[i]=nc^[i-1];
min:=0;
for j:=1 to n do if     j2^[j] then
for k:=1 to n do if not k2^[k] then
if  (min=0) or (min>a^[j]^[k])
then min:=a^[j]^[k];
for k:=1 to n do if k2^[k] then
for j:=1 to n do a^[j]^[k]:=a^[j]^[k]+min;
for j:=1 to n do if j2^[j] then
for k:=1 to n do a^[j]^[k]:=a^[j]^[k]-min
                                        END;
UNTIL np=n;
assign(o,filein);  reset(o);  read(o,n);
for j:=1 to n do
for k:=1 to n do read(o,a^[j]^[k]);
close(o);
sum:=0;
for j:=1 to n do sum:=sum+a^[j]^[kp^[j]];
                           {Запис вiдповiдi}
assign(o,fileout);  rewrite(o);
writeln(o,sum:0:0);
for j:=1 to n-1 do write  (o,kp^[j],' ');
                   writeln(o,kp^[n]);
close(o);              {Вивiльнення пам'ятi}
for j:=1 to n do begin
dispose( a^[j]);
dispose(j0^[j]);
dispose(k0^[j])    end;
dispose(a);  dispose(j0);    dispose(k0);
dispose(c);  dispose(nc);    dispose(newc);
dispose(jp); dispose(usedj); dispose(j2);
dispose(kp); dispose(usedk); dispose(k2);
dispose(stop)                           END.