Mała Delta

Architekci i algorytmy (2)

Rys. 1 Uporządkowanie generowane przez algorytm dla $n 6$ budynków o wysokościach $|b i. i$

W marcowym numerze Delty postawiliśmy następujące pytanie:

Problem. w jaki sposób uszeregować $|n$ budynków o wysokościach danych ciągiem $|b,b ,...,b , 1 2 n$ aby suma różnic wysokości sąsiadujących ze sobą budynków $Pi bi −bi+1$ była jak największa.

Przyjmijmy dla uproszczenia, że liczba budynków $|n$ jest parzysta i równa co najmniej 4. Algorytm znajdujący optymalne uszeregowanie można opisać tak:
Krok 0. Uporządkuj budynki od najniższego do najwyższego. Wysokości budynków utworzą niemalejący ciąg $b1,b2,...,b2k,$ gdzie $n = 2k.$
Krok 1. "Przełam" ciąg $(bi)$ między wyrazami $bk$ i $bk+1,$ otrzymując dwa podciągi: $b ,b ,...,b ,b 1 2 k−1 k$ oraz $b ,b ,...,b ,b . k+1 k+2 2k−1 2k$
Krok 2. "Przełóż" wyrazy podciągów naprzemiennie, tak że otrzymasz ciąg

bk+1,b1,bk+2,b2,...,b2k,bk.

Krok 3. Ustaw w dowolnej kolejności wyrazy stojące na miejscach nieparzystych (z wyjątkiem pierwszego), tj. wyrazy $|bk+2,bk+3,...,b2k.$
Krok 4. Ustaw w dowolnej kolejności wyrazy stojące na miejscach parzystych (z wyjątkiem ostatniego), tj. wyrazy $|b1,b2,...,bk−1.$

Wynik działania algorytmu dla przykładowego ciągu zilustrowano na rysunku 1. Dodajmy pewne uwagi.

Po pierwsze: instrukcja "ustaw w dowolnej kolejności" oznacza, że w wyniku wykonania algorytmu możemy uzyskać $|(k− 1)!⋅(k −1)!$ optymalnych uszeregowań. Oczywiście wygenerowane uszeregowania będą wszystkie różne tylko wówczas, gdy wszystkie wyrazy podciągów, o których mowa w krokach 3-4 algorytmu, są różne.

Po drugie: rozwiązań jest tak naprawdę dwa razy więcej (chyba że wszystkie wysokości budynków są jednakowe), gdyż po zapisaniu wyrazów ciągu, wygenerowanego przez algorytm, w odwrotnej kolejności, również otrzymamy optymalne uszeregowanie.

W efekcie zastosowania kroków $0 − 2$ dla ciągu 5, 10, 10, 15, 25, 25, 30 i 45 otrzymamy optymalny ciąg 25, 5, 25, 10, 30, 10, 45, 15. Wszystkich optymalnych rozwiązań, które uzyskujemy wykonując kroki $3− 4,$ jest w sumie 36 (dlaczego?).

Jak uzasadnić, że przedstawiony wyżej algorytm daje optymalne rozwiązanie, czyli takie uszeregowanie budynków, że suma różnic wysokości sąsiednich budynków będzie największa z możliwych?

Zauważmy, że jeśli dwa budynki $bi$ i $b j$ sąsiadują (przy czym $bi ⩾bj$ ), to ich wkład w sumę różnic wynosi $bi− b j.$ Zatem dla każdej pary wkład to różnica wysokości wyższego budynku i wysokości niższego budynku. Mamy $n − 1$ takich par, a każdy budynek (oprócz skrajnych) należy do dwóch takich par. Zatem sumę różnic można zapisać jako

n S = Q (bi⋅xi + bi⋅yi), i 1

gdzie wśród wartości $|x1,...,xn$ oraz $y1,...,yn$ dokładnie dwie są równe 0, dokładnie $|n −1$ wartości jest równych 1 i dokładnie $|n− 1$ wartości jest równych $|−1.$ Można zauważyć, że dla $|b1⩽ b2⩽ ...⩽ bn,$ suma $S$ przyjmie maksymalną wartość wtedy, gdy $|x ⩽ y ⩽ x ⩽ y ⩽... ⩽x ⩽ y . 1 1 2 2 n n$

Rys. 2 Pod budynkiem $bi$ zapisano odpowiadające mu wartości $xi$ i $yi.$

Pozostaje wykazać, że istnieje uszeregowanie, które realizuje tę sumę. Łatwo się przekonać, że jest to, na przykład, uporządkowanie uzyskane w kroku 2 algorytmu. Wówczas wartości $|xi$ i $|yi$ dla $i ⩽k − 1$ są równe $− 1,$ wartość $|xk = − 1,$ wartości $yk$ i $xk+1$ są równe 0, wartość $|y = 1 k+1$ oraz wartości $|x i$ i $|y i$ dla $i ⩾ k+ 2$ są równe 1 (Rys. 2). Tak więc

S = (bk+1−b1) +(bk+2 −b1) +(bk+2 −b2) + ... +(b2k −bk).

Zauważmy również, że permutacje, które wykonujemy w krokach $| 3− 4$ algorytmu, nie zmieniają wartości $| xi$ i $| yi$ dla indeksów $i⩽ k −1$ oraz $i ⩾k + 2,$ zatem nie psują optymalności rozwiązania.

Jako zadanie dla Czytelników pozostawiamy uzasadnienie, że algorytm generuje wszystkie możliwe optymalne uszeregowania budynków, czyli że wyrazy podciągów, o których mowa w kroku 1, muszą występować naprzemiennie. (Można tu skorzystać z obserwacji, że permutacje z kroków $| 3 − 4$ są jedynymi, które nie zmieniają wartości $xi$ i $yi,$ i popatrzeć, co się dzieje z sumą $|S,$ jeśli któreś z wartości zostaną zmienione.)

Czytelnik Wnikliwy może zapytać: a co w przypadku, gdy $n$ jest liczbą nieparzystą? Czy przedstawiony wyżej algorytm można w prosty sposób zaadaptować dla takiej sytuacji? Okazuje się, że tak! W jaki sposób to zrobić?

Gdy $n = 2k+ 1,$ dla pewnego naturalnego $k ⩾ 1,$ mamy $2k$ par sąsiadujących budynków, a każdy budynek (oprócz skrajnych) należy do dwóch takich par. Postępując jak poprzednio, sumę różnic można zapisać jako

2k+1 S = Qi 1 (bi⋅xi + bi⋅yi),

gdzie wśród wartości $x1,...,x2k+1$ oraz $y1,...,y2k+1$ dwie są równe 0, $|2k$ wartości jest równych 1, a $2k$ wartości jest równych $− 1.$ Znowu dla niemalejącego ciągu $(bi),$ suma $S$ przyjmie maksymalną wartość wtedy, gdy $|x1⩽ y1⩽ x2 ⩽y2 ⩽ ...⩽ x2k+1⩽ y2k+1.$ Można się jednak przekonać, że dla żadnego $k$ nie istnieje takie uszeregowanie, że wartości $x i$ i $y i$ dla $|i⩽ k$ są równe $|−1,$ wartości $x k+1$ i $y k+1$ są równe 0, a wartości $xi$ i $yi$ dla $|i⩾ k +2$ są równe 1, gdyż wartości 0 muszą być przypisane skrajnym, a więc różnym, budynkom (inaczej oznaczałoby to, że budynek o wysokości $bk+1$ jest skrajnym zarówno z lewej, jak i prawej strony). Kiedy zatem suma $|S$ będzie największa? Są trzy możliwości.

(1): Jeśli $bk+1− bk < bk+2− bk+1,$ to maksymalna suma będzie odpowiadać zamianie wartości $yk = 0$ i $|yk+1 = −1,$ a więc np. uszeregowaniu $b ,b ,b ,b ,b ,...,b ,b . k+1 k+2 1 k+3 2 2k+1 k$
(2): Jeśli $bk+1− bk > bk+2− bk+1,$ to maksymalna suma będzie odpowiadać zamianie wartości $|xk+1 = 1$ i $|xk+2 = 0,$ a więc np. uszeregowaniu $bk+2,b1,bk+3,b2,...,b2k+1,bk,bk+1.$
(3): Jeśli $|bk+1− bk = bk+2− bk+1,$ to oba wyżej wymienione uszeregowania będą związane z maksymalną sumą (Rys. 3).

Przeprowadzając analogiczne rozumowanie jak w przypadku $| n$ parzystego, można pokazać, że wykonując pewne permutacje, możemy otrzymać więcej optymalnych uszeregowań budynków. Gdy wszystkie wysokości budynków są różne, to ich liczba jest równa $2⋅k! ⋅(k− 1)!$ (lub jeszcze dwa razy większa, jeśli mamy do czynienia z trzecią możliwością z powyższej listy).

Przy okazji: "przełamywanie" ciągu i naprzemienne "przekładanie" wyrazów podciągów może Czytelnikowi przypominać tasowanie kart w grach karcianych. To celne spostrzeżenie! Więcej na temat teorii tasowania kart (i nie tylko) Czytelnik znajdzie w książce Iana Stewarta pt. Jak pokroić tort i inne zagadki matematyczne, wydanej w języku polskim w 2012 roku.