PALMA junior
Úloha o súboji robotov

Autorské riešenie
[stiahni]

Toto je veľmi zaujímavá úloha. Ide totiž nie len o to, aby sme ju vyriešili správne, ale aj o to, aby to bolo lepšie ako robot súpera. Môžeme vytvárať rôzne stratégie a nechať ich navzájom "súperiť". Dokonca môžeme spraviť to, že postavíme rovnaké stratégie proti sebe. Pozrime sa postupne, aké stratégie by sme mohli použiť.

Najjednoduchšou stratégiou, ak ju vôbec možno nazvať stratégiou, je nechať robota sa náhodne pohybovať po poli so zeleninou.

Tento prístup asi nie je najvhodnejší. Ak robot nájde nejakú zeleninu, je to len náhoda. Chcelo by to niečo premyslenejšie. Postupovať môžeme tak, ako začínajúci hubári. Keď nevedia kde a ako hľadať, pôjdu za nejakým skúsenejším hubárom. Ak skúsený hubár natrafí na dobré miesto bude tam prvý. Je ale šanca, že sa nám z jeho nálezu tiež niečo ujde. Nechajme teda robota v ďalšej stratégii, aby zamieril k súperovi.

Je to lepšia stratégia, ale ak by súper použil stratégiu 0 alebo 1, asi by sme sa ďaleko nedostali.

Trochu lepší prístup (pravdupovediac o dosť lepší) je, zbierať zeleninu v tom poradí, ako je uvedená v zozname súradníc. Toto je už naša stratégia a nespoliehame sa na šikovnosť súpera.

Už sme použili nejaký systematický prístup, pohyb robota nie je náhodný ale riadi sa jasnými pravidlami. Problém je v tom, že poradie sadeníc zeleniny v zozname nemusí byť najvhodnejšie. Pozrime si nasledujúci obrázok.

Robot zbytočne pobehuje z jednej strany na druhú namiesto toho, aby najskôr vyzbieral jednu stranu a potom druhú. Vylepšime teda stratégiu tak, aby robot vždy šiel k najbližšej potrave.

Prejdeme zoznamom súradníc sadeníc a pre každú sadenicu si vypočítame našu vzdialenosť od nej. Ak nájdeme nejakú bližšiu ako sme doteraz našli, zapamätáme si ju. Takto docielime to, že si nakoniec pamätáme tú, ku ktorej sme najbližšie. Robota natočíme priamo k nej.

Toto už vyzerá ako celkom dobrá stratégia. Nepočítame však s tým, že na poli je aj druhý robot.

Kým sa modrý robot dostane k 2, tak zelený robot (ak použije rovnakú stratégiu) stihne pozbierať zeleninu 2, 4 a 6. V tejto situácií je pre modrého jasné, že sa mu neoplatí ísť do pravej časti, ale rovno zamieriť vľavo. Takže ísť k najbližšej sadenici sa oplatí len vtedy, ak tam súper nebude skôr.

Nasledujúca stratégia by teda mohla byť takáto. Nájdeme si najbližšiu sadenicu a vzdialenosť od nej. Potom si vypočítame, po koľko krokoch príde k našej sadenici súperiaci robot (pozor, nemusí k nej ísť priamo). Ak tam bude skôr ako náš, nemá zmysel tam ísť. Vyberieme si druhú najbližšiu a opäť zistíme, po koľko krokoch k nej dorazí súperiaci robot. Ak by mu to trvalo dlhšie, zamierime k nej. V opačnom prípade skúsime tretiu najbližšiu sadenicu. Takto pokračujeme dovtedy, kým nenájdeme sadenicu ku ktorej sa náš robot dostane skôr ako súper. Ak táka neexistuje, nemá náš robot šancu vôbec nejakú sadenicu zobrať (ak samozrejme súperiaci robot používa stratégiu najbližšej sadenice).

Toto je už pomerne dobrá stratégia. Ale, existuje aj lepšia. Problémom tejto stratégie je to, že robot sa orientuje len na svoje najbližšie okolie. Nepozerá sa na rozmiestnenie sadeníc globálne. Zamieri teda k blízkej, osamotenej sadenici namiesto toho, aby zamieril k vzdialenejšiemu zhluku sadeníc. Túto situáciu ukazuje nasledujúci obrázok.

Robot by teda mal uvažovať nie len o sadeniciach ako takých, ale aj o skupinkách sadeníc. Navštíviť väčšiu, i keď vzdialenejšiu skupinku môže byť výhodnejšie než bližšiu a menšiu skupinku. Zároveň však musí predpokladať ako bude postupovať súperiaci robot, aby sa nestalo, že kým dorazí k veľkej skupine sadeníc, súperiaci robot ju vyzbiera. Naprogramovať túto stratégiu už vôbec nie je jednoduché. Navyše vyhodnotenie najvhodnejšieho smeru by bolo zrejme tak náročné, že by zabralo príliš veľa času.

Podobný problém (i keď bez súperiaceho robota) riešia informatici už pomerne dlho a otázkou je, či vôbec existuje nejaké šikovné riešenie. Tento problém sa nazýva "Problém obchodného cestujúceho". Cieľom obchodného cestujúceho je vybrať sa z mesta, v ktorom sa práve nachádza, navštíviť každé mesto práve raz a vrátiť sa do počiatočného mesta. Pritom sa snaží túto cestu absolvovať tak, aby precestoval čo najmenšiu vzdialenosť, zaplatil čo najmenej peňazí a podobne. Viac sa o ňom dozviete napr. tu: http://sk.wikipedia.org/wiki/Probl%C3%A9m_obchodn%C3%A9ho_cestuj%C3%BAceho.

Vaše zaujímavé riešenia a najčastejšie chyby

Viac ako polovica súťažiacich objavila stratégiu najbližšej sadenice. Táto však nijako nezohľadňuje súperiaceho robota a robot postupuje nezávisle od súperiaceho robota.

Objavil sa aj pokus využiť ťažisko sadeníc (i keď nie dotiahnutý do konca). Problémom tejto stratégie je, že v okolí ťažiska sa nemusí nachádzať žiadna sadenica (ak sú napr. sadenice rozmiestnené rovnomerne v protiľahlých rohoch poľa).

Niektorí použili vo svojom riešení nedovolené príkazy (napr. zmena pozície) alebo procedúre pridali vstupné parametre.