Informatyczny kącik olimpijski

Oblodzone drogi

W tym miesiącu omówimy zadanie Icy Roads z obozu w Petrozawodsku z roku 2013.

Rys. 1 Przykładowa sieć dla $|n 3,m$ o czasach przejazdu $a 7,2,5,6$ i $b 5,3,7 .$ Optymalna trasa o czasie $| 5 2 3 3 6 19$ została przedstawiona kolorowymi strzałkami. Zauważmy, że na skrzyżowaniu $| 1,1$ wybrany został odcinek alei o czasie przejazdu 3, zamiast ulicy o czasie przejazdu 2. Algorytm zachłanny (strzałki przerywane) znalazłby trasę o czasie $|5 2 2 7 7 23$

Zadanie. Sieć drogowa w mieście składa się z $n +1$ pionowych ulic oraz $|m + 1$ poziomych alei. Chcemy jak najszybciej dostać się ze skrzyżowania $|(0,0)$ do skrzyżowania $(n, m),$ pokonując $n +m$ odcinków dróg. Niestety, drogi są oblodzone i jeździ się po nich dość wolno: przejechanie jednego odcinka $i$ -tej ulicy zajmuje czas $ai,$ zaś przejechanie jednego odcinka $j$ -tej alei zajmuje czas $b j.$ Należy wyznaczyć najszybszą trasę przejazdu.

Na rysunku 1 przedstawiono przykładową sieć i wyjaśniono, dlaczego algorytm zachłanny, który na każdym kolejnym skrzyżowaniu wybiera tę ulicę/aleję, która ma mniejszy czas przejazdu, nie jest poprawny.

Rys. 2 Ilustracja do dowodu, że przy pewnych założeniach możemy zablokować ulicę $|i$

Pomimo prostego sformułowania, zadanie jest trudne i wymaga kilku pomysłowych obserwacji. Główna idea rozwiązania będzie opierać się na sukcesywnym blokowaniu tych ulicąlei, którymi nie opłaca się jeździć. Na początek pokażemy, że jeśli jakaś ulica $i$ znajduje się pomiędzy dwiema ulicami o mniejszych czasach przejazdu, to można ją zablokować. Załóżmy, że w pewnym optymalnym rozwiązaniu przejeżdżamy odcinkami tej ulicy pomiędzy alejami $j$ oraz $j+ k$ (Rys. 2). Niech $|i− ℓ1$ oraz $i +ℓ2$ będą numerami tych niezablokowanych jeszcze ulic, pomiędzy którymi znajduje się ulica $|i$ (przy pierwszym czytaniu można przyjąć $|ℓ1 = ℓ2 = 1$ ). Zgodnie z założeniem mamy $a ⩽ a ⩾ a . i−ℓ1 i i+ℓ 2$ Czas przejazdu wynosi $|Ci = b j⋅ℓ1 + ai⋅k + b j+k ⋅ℓ2.$ Natomiast czasy przejazdu, gdybyśmy zamiast ulicy $i$ wybrali ulicę $|i− ℓ1$ lub $i +ℓ2$ wynoszą odpowiednio $|Ci−ℓ1 = ai−ℓ1⋅k+ b j+k⋅(ℓ1 + ℓ2)$ oraz $|Ci+ℓ 2 = bj ⋅(ℓ1 +ℓ2) +ai+ℓ2⋅k.$ Widać jednak, że co najmniej jedna z tych tras ma czas nie większy niż optymalny:

min(Ci−ℓ1,Ci+ℓ2)⩽ min(bj , b j+k)⋅(ℓ1+ ℓ2)+max(ai −ℓ1,ai+ℓ 2)⋅k ⩽Ci.

Powtarzając powyższe rozumowanie, możemy zablokować część ulic w mieście tak, że czasy przejazdu pozostałych będą tworzyć ciąg unimodalny (najpierw będą maleć, osiągając minimum na pewnej ulicy $|i⋆,$ a potem rosnąć). Zauważmy, że blokowanie ulic powoduje, że odległości między kolejnymi niezablokowanymi ulicami mogą się zwiększać (stąd konieczność uwzględnienia wartości $ℓ1$ i $|ℓ2$ w powyższym dowodzie). Cały argument możemy niezależnie zastosować do alei (które zatem też będą tworzyć ciąg unimodalny, osiągając minimum na pewnej alei $| j⋆$ ). Druga obserwacja jest następująca: optymalna trasa będzie przechodziła przez skrzyżowanie $|(i⋆ , j⋆)$ najtańszej ulicy z najtańszą aleją. (Jeśli tak nie jest, to rozważamy punkt przecięcia trasy z ulicą $i⋆$ oraz punkt przecięcia trasy z aleją $j⋆.$ Przejście pomiędzy tymi punktami po odcinkach ulicy $|i ⋆$ oraz alei $j ⋆$ nie pogorszy rozwiązania.) Zatem możemy nasz problem podzielić na dwa niezależne problemy szukania trasy ze skrzyżowania $|(i⋆ , j⋆)$ do skrzyżowania $|(0,0)$ oraz trasy ze skrzyżowania $|(i⋆ , j⋆)$ do skrzyżowania $|(n,m).$ Bez straty ogólności możemy więc założyć, że ciągi $a$ i $|b$ czasów przejazdu dla niezablokowanych ulic i alei są rosnące.

Pójdziemy jeszcze krok dalej i pokażemy silniejszy warunek na te ciągi, a mianowicie, że funkcje $i ( ai$ oraz $|i ( bi$ dla niezablokowanych ulicąlei są wypukłe. Przez $∆ ai$ oznaczmy średni przyrost czasu na odcinek od ulicy $|i$ do następnej niezablokowanej ulicy (analogicznie $∆ b j$ dla alei). Zatem dla rysunku 2 mamy (przy dodatkowym założeniu, że aleje $j$ i $j +k$ są sąsiednie):

ai−-ai−ℓ1- ai+ℓ2−-ai bj +k-−b j ∆ai−ℓ1 = ℓ1 , ∆ai = ℓ2 , ∆b j = k .

Ponownie rozpisując wzory na czasy przejazdu trasami $|C ,C i i−ℓ1$ i $C , i+ℓ2$ dostajemy, że

Ci−ℓ ⩽ Ci wtw.∆ b j⩽ ∆ ai−ℓ , Ci+ℓ ⩽ Ci wtw. ∆ b j⩾ ∆ai. 1 1 2

Jeśli $∆ ai−ℓ1⩾ ∆ai,$ to co najmniej jeden z powyższych warunków jest spełniony, więc $min(Ci −ℓ1,Ci+ℓ 2) ⩽ Ci$ i można zablokować $i$ -tą ulicę. Powtarzając to rozumowanie, powodujemy w końcu, że ciągi $∆ a$ oraz $|∆b$ dla niezablokowanych ulicąlei są rosnące.

Pora na ostatnią obserwację: na tak poblokowanej sieci drogowej możemy już stosować algorytm zachłanny, tzn. na każdym skrzyżowaniu wybierać tę ulicęąleję, która ma mniejszy współczynnik średniego przyrostu czasu. A konkretnie: będąc na skrzyżowaniu $i$ -tej ulicy z $j$ -tą aleją wybieramy ulicę, jeśli $∆ b ⩽ ∆a , j i$ a aleję, jeśli $∆b > ∆a . j i$ Dowód poprawności tego algorytmu przeprowadzimy przez indukcję po $|i + j.$ Dla $i + j = n+ m$ teza jest oczywista (jesteśmy na ostatnim skrzyżowaniu i nie mamy co wybierać). Załóżmy zatem, że algorytm zachłanny działa poprawnie, jeśli startujemy z dowolnego skrzyżowania $′ ′ |(i, j)$ dla którego $′ ′ |i + j > i + j.$ Ponadto załóżmy (Rys. 3), że jest spełnione $∆bj ⩽ ∆ai,$ ale w rozwiązaniu optymalnym wybieramy aleję, zatem jedziemy do skrzyżowania $(i +ℓ2, j).$ Z wypukłości mamy $|∆a < ∆ a , i i+ℓ 2$ zatem tym bardziej jest spełnione $∆ b ⩽ ∆a , j i+ℓ2$ więc z założenia indukcyjnego wynika, że w drugim ruchu wybierzemy ulicę, przesuwając się do skrzyżowania $(i + ℓ2, j+ k).$ Te dwa ruchy kosztowały nas czas $C′= b0 ⋅ℓ2 + a1⋅k.$ Jednakże rozwiązanie, w którym dostajemy się do skrzyżowania $|(i + ℓ, j + k) 2$ najpierw jadąc ulicą, a potem aleją, ma czas $|C”= a0 ⋅k+ b1⋅ℓ2.$ Nietrudno się przekonać, że warunek $∆ b j⩽ ∆ai$ jest równoważny temu, że $C ”⩽ C ′.$ To pokazuje, że istnieje optymalne rozwiązanie, w którym pierwszym ruchem jest wybór ulicy, co kończy dowód.

Myślę, że Czytelnicy, którzy przebrnęli przez powyższy opis algorytmu nie będą mieli trudności, by zaimplementować go w optymalnej złożoności czasowej $O(n +m).$