Przeskocz do treści

Delta mi!

Loading

Informatyczny kącik olimpijski

Oblodzone drogi

Tomasz Idziaszek

o artykule ...

  • Publikacja w Delcie: sierpień 2016
  • Publikacja elektroniczna: 31 lipca 2016
  • Wersja do druku [application/pdf]: (61 KB)

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

obrazek

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

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.

obrazek

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

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.

obrazek

Rys. 3 Ilustracja działania algorytmu zachłannego

Rys. 3 Ilustracja działania algorytmu zachłannego

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