Числов триъгълник
Преслав Наков
Задачите за търсене на оптимален път в граф често се решават чрез техниката на динамичното оптимиране. Класически пример в това отношение е задачата за търсене на минимален път в триъгълник. Задачата е изключително популярна. Давана е на Международната олимпиада по информатика в Швеция, както и като задача 2 на българската Четиринадесета олимпиада по информатика, Март 1998.
Задача:
(Задача 2 от Четиринадесетата олимпиада по информатика, Март 1998.)Разглежда се числов триъгълник от вида:
a1 |
|||
a2 |
a3 |
||
a4 |
a5 |
a6 |
|
a7 |
a8 |
a9 |
a10 |
…………..
имащ
n реда (1£ n£ 50). Числата на числовия триъгълник са положителни, не са по-големи от 20 и се въвеждат от текстов файл с име INP2. Всеки ред от файла съдържа числата от отделен ред на числовия триъгълник. За разделител между числата има поне един интервал. Числото X от i-ти ред (1£ i£ n) и числото Y от (i+1)-ви ред се наричат съседни, ако са разположени едно под друго в числовия триъгълник или числото Y е с една позиция надясно или наляво спрямо числото X. Например съседните на числото a5 са числата a7, a8 и a9. Числото a2 има за съседни числата a4 и a5.Да се състави програма, която намира минималната сума на редица от
n числа на числовия триъгълник, удовлетворяваща едновременно свойствата:Резултатът да се извежда на екрана.
Решение:
Разглеждаме ориентирания граф G(V,E), с множество от върхове V = {a1, a2, …, an(n+1)/2} и множество от ребра E = {(ai,aj) | ai и aj са съседни}. Тогава задачата се свежда до намиране на път в G с дължина n, за който сумата от върховете е минимална. Съгласно условието произволен път с дължина n ще започва от а1 (там започват всички пътища) и ще завършва на последния ред на триъгълника, т.е. в някое от an(n+1)/2-n+1, an(n+1)/2-n+2, …, an(n+1)/2 (всеки следващ връх от пътя е едно ниво по-надолу от предходния).
Ясно е, че за да определим търсения минимален път, трябва да бъдат намерени всички минимални пътища в G, завършващи във върхове от последния ред на триъгълника. Как да намерим тези пътища? Бихме могли да приложим някакъв вид алгоритъм с изчерпване, който, построявайки всички пътища, завършващи в последния ред на триъгълника, ще построи и търсения минимален път. Тъй като при построяването на пътя на всяка стъпка имаме 2 или 3 възможности за продължение, един такъв алгоритъм би имал експоненциална сложност.
Не е трудно да се забележи обаче, че задачата може да се реши и с техниката на динамичното оптимиране. Тъй като числата от триъгълника са положителни, то добавянето на нов връх към някой частичен път ще води до строго увеличаване цената на пътя. Тогава минималният път px до произволен връх x от ниво k=2,3,…,n ще има едно особено свойство: Нека y е непосредствен предшественик на x в px. Премахвайки последния връх от px (т.е. x), получаваме път py до върха y. При това полученият път py е минимален. Действително, ако допуснем, че съществува път p¢ y, с по-ниска цена от тази на py, то добавяйки върха x към p¢ y, получаваме път p¢ x, с по-ниска цена от тази на px, което е противоречие с минималността на px.
Тогава намирането на минималния път до даден връх се свежда до намиране на минималния път до всички негови преки предшественици. За да построим минималните пътища с дължина
k трябва да знаем всички минимални пътища с дължина k-1. За да намерим тях, са ни необходими всички пътища с дължина k-2 и т. н. Така, за да решим задачата, възниква необходимостта от построяване на минималните пътища до всеки от върховете на триъгълника.На пръв поглед може да не личи, че предложеният алгоритъм е по-добър от пълното изчерпване, тъй като тук също се строят пътища до всеки връх. За разлика от пълното изчерпване обаче тук се изграждат не всевъзможните, само минималните пътища до даден връх. При това преминаването от път минимален път с дължина
k към минимален път с дължина k+1 става почти директно и е свързано с неповече от три проверки, тъй като всеки връх има два или три съседа.Въвеждаме следните означения:
v[x] — цена за преминаване през върха x (стойност на x-тото число от триъгълника);
p[x] — цена на минималния път до върха x;
pred[x] — пряк предшественик на върха x в минималния път до x.
Удобно е изграждането на минималните пътища да става по редове, като се започне от първия ред. В зависимост от начина на актуализация и изграждане на минималния път, получаваме два различни линейни алгоритъма:
Алгоритъм I — Фиксира се връх и се актуализират мин. пътища до наследниците му.
p[1] := v[1];
p[x] := +¥ , за x=2,3,…, n(n+1)/2
.p[y] := min(p[y],p[x]+v[y]).
p
red[y] := x.Алгоритъм II
— Фиксира се връх и директно се намира минималният път до него, като се използват намерените минимални пътища до неговите предшественици.p[1] := v[1];
p[x] := +¥ , за x=2,3,…, n(n+1)/2
.p[
x] := min(p[y¢ ]+v[x],p[y¢ ¢ ]+v[x],p[y¢ ¢ ¢ ]+v[x]),където
y¢ , y¢ ¢ и y¢ ¢ ¢ са съседните на x елементи от ниво k-1.Забележка:
Ако x е първият елемент от ниво k, той има само два предшественика: y¢ и y¢ ¢ .p
red[x] := y.Ясно е, че предложените алгоритми са линейни по броя на върховете
N в триъгълника. Вземайки предвид, че N=n(n+1)/2, получаваме алгоритмична сложност O(n2).Съхраняването на числата от триъгълника в матрица води до неефективно използване на паметта — почти половината елементи са неизползвани. Добре би било да се помисли за линеаризация на матрицата. Едно очевидно решение е използването на едномерен масив, в който числата се разполагат по редове последователно отляво-надясно — така както постъпват от входния файл и както ще ги обработваме.
В приложената програмна реализация не сме се придържали стриктно към условието на задачата: Входните данни се четат от файла
triangle.txt, вместо от INP2. Броят на редовете не надвишава 100, вместо 50, а числата не бива да надвишават MaxLongInt. Следва програмна реализация на Алгоритъм I:PROGRAM Triangle; CONST MAX = 100; TYPE OGR = 0..MAX*(MAX+1) div 2 - 1; DataType = 0..MaxLongInt; VAR Red : OGR; { Брой редове в триъгълника } V, { Цена за преминаване през I-ия възел } P, { Минимална цена за достигане на възел I} Pred : Array[OGR] of DataType; { Предшественик на възел I в мин. път } PROCEDURE INIT; { Прочитане на входните данни } Var F : TEXT; I,J : OGR; Begin Assign(F,'TRIANGLE.TXT'); Reset(F); Red := 0; J := 0; While not EoLn(F) do begin Inc(J,Red); Inc(Red); For I := 1 to Red do { j-тият ред съдържа точно j числа } begin Read(F,V[J+I]); P[J+I] := MaxLongInt end; ReadLn(F) end; Close(F) End; PROCEDURE Compare(Ind1,Ind2 : OGR); Begin If P[Ind1] > P[Ind2] + V[Ind1] then begin P[Ind1] := P[Ind2] + V[Ind1]; Pred[Ind1] := Ind2 end End; PROCEDURE FindMinPath; { Намира минималния път до всеки възел } Var I,J,Sum : OGR; Begin { Динамично оптимиране } P[1] := V[1]; { До първия връх се стига непосредствено } Sum := 0; For I := 1 to Red do begin For J := 1 to I do begin If J > 1 then Compare(Sum+J+I-1,Sum+J); Compare(Sum+J+I,Sum+J); Compare(Sum+J+I+1,Sum+J) end; Inc(Sum,I) end End; PROCEDURE PRINT; { Извежда триъгълника на минималните пътища на екрана } Var I,J,Sum : OGR; Begin WriteLn('Триъгълник на минималните пътища:'); Sum := 0; For I := 1 to Red do begin For J := 1 to I do Write(P[Sum+J]:8); WriteLn; Inc(Sum,I) end End; PROCEDURE WritePath(X : OGR); { Извежда минималния път до връх X } Begin WriteLn('Пътят до връх номер ',X,' е минимален: ',P[X]); Write('Пътят, изведен в обратен ред (индекси): '); While X <> 1 do begin Write(X,' '); X := Pred[X] end; WriteLn(1) End; PROCEDURE FindMinLastRow; { Намира връх от последния ред с минимален път } Var I,MinInd : OGR; Begin MinInd := Red*(Red+1) div 2 - Red + 1; For I := Red*(Red+1) div 2 - Red + 2 to Red*(Red+1) div 2 do If P[I] < P[MinInd] then MinInd := I; WritePath(MinInd) End; BEGIN INIT; FindMinPath; PRINT; FindMinLastRow END.Примерен вход:
22 33 5 6 77 8 22 7 225 177 738 737 778 39 28 9 10 11 12 13Резултат:
Триъгълник на минималните пътища: 1 23 34 28 29 111 36 50 36 336 213 774 773 814 375 241 222 783 386 387 388 Пътят до връх номер 17 е минимален: 222 Пътят, изведен в обратен ред (индекси): 17 11 7 4 2 1