Náš pes Alino má veľmi rád návštevy, no ešte radšej má piškóty. Keď príde návšteva, existuje len jediný spôsob ako sa ho aspoň na čas zbaviť: rozhádzať mu po zemi piškóty a kým ich všetky nepožerie, je od neho pokoj.Avšak piškóty nám už zostali iba tri. Ako ich máme rozložiť do štvorcovej miestnosti s rohmi ABCD, aby trvalo Alinovi čo najdlhšie, kým ich všetky zožerie? Predpokladáme, že Alino začína svoju mlsnú prechádzku pri nás v rohu A a kráča konštantným tempom vždy priamou cestou k najbližšej piškóte. Ak sú dve piškóty rovnako vzdialené, vyberie si Alino úplne náhodne, za ktorou z nich sa vyberie. Zožratie piškóty mu trvá, samozrejme, zanedbateľne krátky čas. Keď už nie je čo jesť, vráti sa naspäť do rohu A, aby nás mohol opäť obšťastňovať.
Možno mi neuveríte, ale moji rodičia majú naozaj psa s menom Alino (bordeauxka doga na obrázkoch) a metódu rozhadzovania piškót skutočne občas používajú. Jedná sa teda o problém aplikovanej matematiky. :-)
3 komentáre:
Nech ma miestnost jednotkovy rozmer. Zrejme ak dame piskoty do rohov B,C,D, pes prebehne vzdialenost 4. Skusal som najst lepsie riesenie, ale takto neskoro v noci ma rychlo presla trpezlivost a ako nadejny aplikovany matematik som skusil riesit ulohu numericky :)
Pri maximalizacii simulovanym zihanim (klasicka metoda mi stale nachadzala iba riesenie v rohoch) som dospel k rieseniu:
P1: (0.73205, 0)
P2: (1, 1)
P3: (0, 0.73205)
Zaujimave na tomto rieseni je, ze piskoty tvoria rovnostranny trojuholnik a teda su rozne pripustne cesty ktorymi sa moze pes pustit (podla toho ktoru piskotu si vyberie ako druhu v poradi), s roznymi dlzkami (program nasiel tu vacsiu):
A -> P1 -> P3 -> P2 -> A 4.2168
A -> P1 -> P2 -> P3 -> A 3.5347
Ivan: Super! Skutočne je to tak; riešenie som načrtol na tomto obrázku.
Aby sme boli presní, je treba povedať, že ak by boli piškóty tak ako je naznačené na obrázku, tak si pes môže náhodne vybrať aj kratšiu trasu (približne 3.534654) ako si napísal. Prvú piškótu teda musíme posunúť o máličko (o ľubovoľnú nenulovú vzdialenosť) bližšie k bodu A.
Prísne vzaté, úloha nemá optimálne riešenie, pretože čím bližšie je prvá piškóta ku kritickému bodu, tým je dĺžka Alinovej prechádzky väčšia, no v kritickom bode už dĺžka (presnejšie jej stredná hodnota) skočí nadol.
Formálne povedané, to číslo uvedené hore na obrázku je supremum všetkých možných dĺžok Alinovych prechádzok, ktoré sa však na množine prípustných riešení nedosahuje.
Inak tento problém bude veľmi ťažký pre optimlizačné procedúry a nečudujem sa, že pomohlo len "robustné" simulované žíhanie. Účelová funkcia totiž nieleže má viacero lokálnych maxím (napríklad poloha piškót vo vrcholoch štvorca), ale dokonca je nespojitá!
chcel by som len poznamenat, pre tu malu skupinku, ktorej to mozno nahodou uniklo, ze jeden z prvych ludi, co publikovali o simulovanom zihani je Vladimir Cerny - katedra teoretickej fyziky na matfyze - odkaz na ten clanok je aj na wikipedii na ktoru odkazal Rado. Co do poctu citacii, je to jeden z najvacssich slovenskych uspechov poslednych cias 579 citacii na Web of Knowledge
Zverejnenie komentára