КАЛГОРИТМ 276 Распределение [Н]

Процедура assign .находит Уйкую перестановку х целых чисел 1, 2,.. .,п, для которых минимальна сумма (по 2,...,п) элементов d. гяатрицы d порядка п2.

Для получения более полной информации .смотрите статью Р. Силвера «Алгоритм для задачи распределе-ния» *.

procedure assign (d,n) result: (х);

value n; integer n; array d; integer array x; begin real min.total; integer flag, cbp,cp,cpO,i,j,k,p,rp,rs,s; integer array c,cb,lambda,mu,r,y(l:n]; switch sw:=next,pl,nextl,mark; total:=0; ;

for i: = 1 step 1 until n do begin min: = d[i, 1];

for j:= 2 step 1 until n do

if d[i, j]<min then min: = dO,j]; for ]:= 1 step 1 until n do di[i,j]: = d[i,j]-min end i; total:=total + min; for j:= 1 step 1 until n do begin min: = dp,j]; for i:= 2 step 1 until n do

if d[i,j]<min then min: = d(i,j]; for i: = l step 1 until n do d[i,j]: = d[i,j]-min end i; total:=total+min;

for i:=: 1 step 1 until n do x[i]:=y[i]: = 0; for i:=: 1 step 1 until n do for j:= 1 step 1 until n do if d[i,j]=OAx[i]==OAy[Jl=0 then begin x[i]:=j; y[j]: = i end; comment Начальная разметка; start: rp: = cp:=0; rs:=:l; flag:=n;

for i:= 1 step 1 until n do

* Перевод этой статьи помещен ниже, за «Подтверждением К алгоритму 27» А. Ньюхауза. {Прим. ред.)

begin mu[i]: = lambda[i]:=0;

if х{[]фО thm go to 11; rp:=rp + l; r[rp]: = i; mu[i]:=-1; flag:=flag-1; il: end i;

if flag=n tfien go to fin; comment Разметка и развертка;

label: i: = rlrs]; rs:=:rs + l;

for j:= 1 step 1 until n do

if d{i,3]==0 Л lambdaO]=0 then begin lambda [j]: = i; cp: = cp + l; pj:=j;

yl]] = 0 then go to mark; rp: = rp + l; rlrp]:=y[j]; muty{j]]:=i end j;

if rsrp then go to label; comment Ренормализация; s: = l; cpO:=cp; cbp:=0;

for ]:= 1 step 1 until n do if iambdaj[j]=0 then begin cbp: = cbp + l; cb[cbp]:=j end; min: = dr[l],cbll]]; for k:= 1 step 1 until rp do for p:= 1 step 1 until cbp do if d{r[k],cb[pl]min then min: = d[r[k],cb[p]]; total:=totaI + (rp + cbp-n) Xmin; for i:= 1 step 1 until n do if mu{i]==0 then begin

for p:= 1 step 1 until cpO do d[i.cpll: == Ф.ф]]+min end else

for p: = 1 step 1 until cbp do begin d[i,cbtp]]: = d[i,cb[p]]-min; go to sw[s];

next: if d.[i,cbIp]]=?fcOV Iambdalcb[p]]70 then

goto pi;

lambda[cblp3]:=i;

if y[cb[p]]=0 then begin j:=cb[p]; s:=2 end else begin cp:=cp + l; фр]:=сЬ[р];

rp: = rp +1; г;[гр]: =y[cb.[p]] ;

end ify;

ol- endp; ;

go to swIs+2];

nextl: if cpO=cp then go to label;

for i: = cpO+l step 1 until cp do mulylcli]]]: = cli];

go to label;

comment. Отметка нового столбца и перестановка;

mark: ylj]: = i: = lambda [j]; if xCi]=0 then begin x{i]:=:j;

for i: = 1 step 1 until n do , .

if xi[i]=0 then go to start; go to fin end; k:=j; j:=}i[i]; x[i]:=k; go to mark; fin: end assign;

Свидетельство к алгоритму 276

Алгоритм 276 получен в результате внесения в алгоритм 27а второй из трех поправок, цредложенных Р. Уитти в его «Подтверждении к алгрритму 27», перевод .которого .приведен ниже.

Алгоритм 276 был транслирован на машине М-220 в системе ТА-1М с входной матрицей d, указанной Р. Уитти, и дал правильный результат.

t Свидетельство к алгоритму 27а

Алгоритм 27а получен в результате исправлений и ординарной .переработки алгоритма 27 i( Silver R. «САСМ», 1960, № 11).

Подтверждение к алгоритму 27

А. Ньюхаус (Newhous А. «САСМ», 1963, № 10) Алгоритм «Распределение» был переведен на язык

MAD и успешно .пропущен на машине IBM 709/7094

После следующих исправлений... *.

* Указываются 12 исправлений к алгоритму 27, учтенных в алгоритме 27а. (Прим. ред.)