Числов триъгълник

Преслав Наков

Задачите за търсене на оптимален път в граф често се решават чрез техниката на динамичното оптимиране. Класически пример в това отношение е задачата за търсене на минимален път в триъгълник. Задачата е изключително популярна. Давана е на Международната олимпиада по информатика в Швеция, както и като задача 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 — Фиксира се връх и се актуализират мин. пътища до наследниците му.

    1. Инициализация:

p[1] := v[1];

p[x] := +¥ , за x=2,3,…, n(n+1)/2.

    1. Преглеждаме последователно елементите от ниво k=1, 2,…, n-1:
    1. Нека сме намерили минималния път p[x] до даден връх x от ниво k (k<n). Тогава за минималните пътища на съседните му елементи y от ниво k+1 имаме:

p[y] := min(p[y],p[x]+v[y]).

    1. Ако на стъпка 2.1. сме актуализирали p[y], то x е непосредствен предшественик на y в минималния път до y:

pred[y] := x.

    1. Край.

Алгоритъм IIФиксира се връх и директно се намира минималният път до него, като се използват намерените минимални пътища до неговите предшественици.

    1. Инициализация:

p[1] := v[1];

p[x] := +¥ , за x=2,3,…, n(n+1)/2.

    1. Преглеждаме последователно елементите от ниво k=2,3,…, n:
    1. Нека сме намерили минималните пътища p[y] до всички върхове y от ниво k-1 (k£ n). Тогава за минималния път до произволен връх x от ниво k имаме:

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¢ ¢ .

    1. Ако на стъпка 2.1. сме актуализирали p[x] за някое yÎ {y¢ , y¢ ¢ , y¢ ¢ ¢ }, то y е непосредствен предшественик на x в минималния път до x:

pred[x] := y.

    1. Край.

Ясно е, че предложените алгоритми са линейни по броя на върховете 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