Задача 1. Задано дві скінчені множини J і K з однаковою кількістю елементів і матрицю A, елементи якої мають індекси з J і K. Потрібно знайти взаємно однозначну відповідність f: J → K, при якій сума емементів aj f ( j ) за всіма j з J найменша.
Зауваження 1. Зауважимо таке.
Розв'язок, тобто відображення f , зберігається при додаванні довільної сталої до всіх елементів будь-якого рядка чи стовпчика матриці A .
Розглянемо випадок, коли всі елементи матриці A невід'ємні. Побудуємо дводольний граф (J, K, E0) , у якому вершини j та k сполучено ребром тоді й лише тоді, коли ajk = 0. Якщо у побудованому графі є повна сполука пар, то вона задає розв'язок задачі про призначення.
Автор і походження назви. Американський математик Х.Кун (Harold D. Kuhn) вперше запропонував так званий угорський метод розв'язання цієї задачі. Він використовував теорію сполук пар, відому йому з робіт угорських учених Д.Кеніґа та Е.Еґеварі, тому й назвав метод угорським.
Угорський алгоритм Куна (Kuhn)
Зведення рядків матриці. Для кожного рядка матриці A:
визначаємо найменший елемент у вибраному рядку;
кожний елемент вибраного рядка зменшуємо на знайдений найменший елемент рядка.
Перетворена таким чином матриця міститиме нуль (можливо, не один) у кожному рядку.
Зведення стовпчиків матриці. Для кожного стовпчика матриці A:
визначаємо найменший елемент у вибраному стовпчику;
кожний елемент вибраного стовпчика зменшуємо на знайдений найменший елемент стовпчика.
Перетворена таким чином матриця міститиме нуль (можливо, не один) у кожному стовпчику.
Побудова максимальної сполуки пар дводольного графа (J, K, E), у якому вершини j та k сполучено ребром тоді й лише тоді, коли ajk = 0.
Знаходимо 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 \ K2 | K2 | |
|---|---|---|
| J2 | – amin | |
| J \ J2 | + amin |
Ліворуч вказано область значень індексу j з множини J;
Вгорі вказано область значень індексу k з множини K;
Світлосірим тлом позначено додатні елементи матриці, серед яких вибирають найменший елемент amin ( j ∈ J2, k ∈ K \ K2). Внаслідок зменшення на amin хоча б один з них перетворюють на 0.
Білим тлом позначено елементи матриці, які можуть дорівнювати нулю і які залишають тими самими при перетворенні:
або з ними нічого не роблять взагалі (лівий нижній кут, j ∈ J \ J2, k ∈ K \ K2);
або їх збільшують, а потім зменшують на amin (правий верхній кут, j ∈ J2, k ∈ K2).
Темносірим тлом позначено додатні елементи матриці, які збільшують на 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.