INFOMAN брой 4
{ This is the input data: N; P[1] P[2] ... P[N].
9
2 5 3 8 7 4 6 9 1
ОПРОВОДЯВАНЕ НА ПЛАТКА
----------------------
В две срещуположни страни на правоъгълна платка са разположени симетрично
един срещу друг N (N<1000) накрайника, ноимерирани последователно с числата
от 1 до N. Дадена е и пермутацията P[1..N] на числата от 1 до N. Необходимо
е да се свърже с проводник всеки накрайник i от едната страна на платката с
съответния му накрайник P[i] от другата страна. Проводниците са прави и не
трябва никои два да се пресичат. Да се намери максималният брой непресичащи
се проводници, с които могат да се свържат съответните двойки накрайници.
РЕШЕНИЕ: Първо да разгледаме схемата на проводниците. Например (N=9):
i = 1 2 3 4 5 6 7 8 9
* * * * * * * * *
* * * * * * * * *
P(i) = 2 5 3 8 7 4 6 9 1
Ще дефинираме следните формули, по които можем да решим задачата с динами-
чно оптимиране. Нека F(Poz1,Poz2) е максималнияt брой непресичащи се провод-
ници, които могат да се прокарат в частта от платката, включваща накрайници-
те от Poz1 до N в горната част и от Poz2 до N в долната част. Тогава са ва-
лидни следните зависимости:
F(Poz1,Poz2) = 0 при Poz1 > N или Poz2 > N
F(Poz1,Poz2) = max ( 0 , ) за i î [Poz1..N]
( 1 + F(i+1,P[i]+1) ) и P[i] ò Poz2
Търсеният максимален брой проводници е F(1,1). Понеже всички възможности за
Poz1 и Poz2 са точно Ný и за намиране на F(Poz1,Poz2) се прилагат най-много
N операции, то можем да направим алгоритъм, който решава задачата за време
N*N*N и с разход на памет N*N. Това става като си наравим една табличка, ко-
ято съдържа е елемента си [i,j] F(i,j) или безкрайност ако все още не е из-
числен. Така с една рекурсивна процедура можем да изчислим функцията. Ако е
необходимо да намерим не само максималният брой проводници, а и самите тях,
можем да си направим още една табличка, където да пазим това i, което дава
максималния брой проводници във всяка ситуация [i,j].
Дали обаче няма и по ефективен алгоритъм?Нека да разгледаме и следната де-
финиция на функцията F:
F(Poz1,Poz2) = 0 при Poz1 > N или Poz2 > N
F(Poz1,Poz2) = max ( 1 + F(Poz1+1,P[Poz1]+1 )
( 0 + F(Poz+1,Poz2), ) при P[Poz1] ò Poz2
С други думи това е очевидната формула за динамично оптимиране - взимаме по-
добрата от двете възможности - да свържем накрайника Poz1 със съответния му
накрайник P[Poz1] ако може или да пропуснем да свържем накрайника Poz1 и да
опитаме следващия - Poz1+1. Ясно е, че с тази формула можем да решим задача-
та за време N*N и памет N*N. Дали обаче не можем и с по-малко памет?Забеляз-
ва се, че рекурентната зависимост относно параметъра Poz1 е много проста -
Елементите F(Poz1,1..N) зависят само от елементите F(Poz1+1,1..N), което ни
дава основание да помислим за алгоритъм с линейна памет. Алгоритъмът е след-
ният: Нека означим с F(x) максималния брой непресичащи се кабели, които мо-
гат да се прокарат между накрайниците от x до N.Понеже в по-горната формула
от F(Poz+1,1..N) получаваме F(Poz,1..N),тук започваме да търсим стойностите
на F(x) от N-тата към първата чрез следния алгоритъм:
F[1..N]:= 1;
for x:= N downto 1 do
for i:= x+1 to N do
if P[x] < P[i] then
F[x]:= Max( F[x], 1+F[i] );
С други думи ако кабелите x-P[x] и i-P[i] не се пресичат, то можем да подоб-
рим максималната за момента сума за F[x], която в началото е 0, като опита-
ме да прокараме кабела x-P[x] и добавим към сумата броя кабели от i нататък
- F[i]. Търсената оптимална стойност накрая е Max(F[i]) за i î 1..N. Ако ще
ни трябва освен максималният брой кабели и конкретно кои накрайници трябва
да се свържат, можем да въведем един масив Next[1..N], който да ни показва
в Next[i] следващия проводник на текущия i - този, при който се е получила
максималната стойност на F[i] или 0 ако няма следващ.
}
CONST MaxN = 1000;
InFileName = 'platka.pas';
VAR P,F,Next: array[1..MaxN] of integer;
N: integer;
Procedure ReadData;
Var F: Text;
i,j: integer;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,N);
for i:= 1 to N do
begin Read(F,j); P[j]:=i; end;
Close(F);
End;
Procedure FindMaximalWires;
Var x,i: integer;
Begin
for i:= 1 to N do F[i]:=1;
FillChar(Next,SizeOf(Next),0);
for x:= N downto 1 do
for i:= x+1 to N do
if P[x] < P[i] then
if 1 + F[i] > F[x] then
begin
F[x]:= 1+F[i];
Next[x]:= i;
end;
End;
Procedure PrintWires;
Var i,M,Index: integer;
Begin
M:=0;
for i:= 1 to N do
if F[i] > M then
begin M:=F[i]; Index:=i; end;
WriteLn('Maximal wires = ',M);
repeat
Write(Index,' '); Index:= Next[Index];
until Index = 0;
WriteLn;
End;
BEGIN
ReadData;
FindMaximalWires;
PrintWires;
END.