Do školy chodím dlhokánskou cestou, na ktorej sú priečne semafory. Okrem toho, že sa potrebujem dostať na druhý koniec ulice, potrebujem sa tiež dostať na druhú stranu, tj. cestu musím niekde skrížiť. Premýšľal som nad tým, ako sa oplatí čakať na semaforoch, aby som minimalizoval celkovú dobu čakania. Jedna možnosť je prísť k prvému semaforu, tam počkať na zelenú a prejsť. Ale — to isté môžem urobiť aj pri poslednom semafore, pričom naviac získam nádej, že pri niektorom zo semaforov po ceste trafím zelenú a nebudem musieť čakať vôbec. Druhá možnosť je teda proste ísť po svojej strane a prinajhoršom prejsť na poslednom semafore. Avšak ak by som pri každom semafore počkal chvíľku (pri rôznych semaforoch rôznu), tak by mi to zrejme zvýšilo šance trafiť zelenú ešte pred koncom ulice, za cenu mierneho zvýšenia strednej čakacej doby v budúcnosti.

Aká je teda doba, ktorú sa mi oplatí vyčkať pri jednotlivých semaforoch?

--

Označme si T_n stredný celkový čas čakania na sekvencii n semaforov. Tiež označme t_n čas, ktorý budeme ochotní čakať na n-tom semafore. Ďalej R nech je dĺžka trvania červenej na semafore, G dĺžka trvania zelenej¹. Potom v prípade, že prídeme k semaforu (n > 1), mohli sme sa (s rovnomerne rozdelenou pravdepodobnosťou) trafiť do jedného z troch úsekov:


• Zelenou je vyznačený úsek, kedy na semafore svieti zelená v čase príchodu k semaforu. Pravdepodobnosť tohto je G/(R+G), stredná celková doba čakania je 0.

• Doba svietenia červenej je rozdelená na dva úseky. Ak sa trafíme do červeného úseku, tak ani po vyčkaní doby t_n sa zelenej nedočkáme a budeme musieť pokračovať k ďalšiemu semaforu. Pravdepodobnosť tohoto je (R - t_n)/(R+G), stredná celková doba čakania je t_n + T_n-1.

• Ak sa trafíme do žltého úseku, síce sme prišli počas červenej, ale v rámci času t_n sa dočkáme zelenej. Pravdepodobnosť tohto prípadu je t_n/(R+G), stredná doba čakania je t_n/2.

To vedie na vzťah pre strednú dobu čakania na n-tom semafore:


Posledný člen je síce nula, ale vzťah mi s ním pripadá zrozumiteľnejší.

Zostáva to už len interpretovať ako funkciu T_n(t_n), vygrafovať, prípadne poderivovať. Na pohľad je to kvadratická funkcia so záporným znamienkom pri kvadratickom člene, takže má jedno maximum a minimá nadobúda skôr na hraniciach definičného oboru:


T₅(t₅) pri R = 120 s, G = 20 s
Sú teda tri zaujímavé voľby t_n:

• t_n = R. To zodpovedá lokálnemu minimu na pravom okraji definičného oboru, resp. ochote čakať počas celej červenej na zelenú na najbližšom semafore. V takom prípade je


čo nie je nijako prekvapivé. Proste si človek počká na zelenú (ak tam už náhodou nesvieti) a stredný čas čakania nezávisí na počte semaforov.

• t_n = R - T_n-1. To zodpovedá maximu danej paraboly a je to najhoršia voľba, akú človek môže spraviť. Stručným výpočtom (postavením T_n = T_n+1) sa dá ukázať, že so zvyšujúcim sa počtom semaforov n sa T_n blíži k:


čo trebárs v prípade [R = 120 s, G = 20 s] sa rovná 67.889, čiže je to ešte horšie než čakanie na najbližšom semafore. A konverguje to veľmi rýchlo, takže už od povedzme piateho semafora najmenej optimálna doba čakania je teda pomerne blízko


čo v spomenutom prípade je asi 52.1 sekundy.

• t_n = 0. To zodpovedá stratégii "idem po svojej strane a ak netrafím zelenú, počkám na poslednom semafore". V takom prípade stredná doba čakania na n-tom semafore (od konca ulice) je


kde stredná doba celkového čakania sa so zvyšovaním počtu semaforov blíži k nule.

--

Po prehrabaní sa v rovniciach a grafoch sa teda neukázalo nič svetoborné: na semaforoch sa neoplatí čakať vôbec, prinajhoršom to človek prejde na poslednom z nich.


¹) Prípadne R_n a G_n, ak sú tie časy medzi semaformi rôzne. Zovšeobecnenie je triviálne a tu chcem počítať len s uniformným R a G.