06 novembra 2009

Ako navigovať robota II

Predchádzajúca úloha sa ukázala byť celkom úspešná; viacerí z Vás našli pekné riešenia logickou úvahou a Rori dokonca našiel riešenie optimálne v tom zmysle, že je najkratšie možné. Pomocou peknej myšlienky Rori tiež vygeneroval množstvo "ťažkých" diagramov, ktoré som si trochu poprezeral a jeden z nich som modifikoval do nasledovnej podoby:


Tak ako v predchádzajúcej úlohe, cieľom je nájsť postupnosť príkazov M/C, ktorá dovedie robota do miestnosti A z akejkoľvek inej* miestnosti.


Kto nájde optimálne riešenie len v hlave, je génius. A kto nájde riešenie pomocou počítača, je schopný programátor. Možno keby som bol zamestnávateľ a chcel by som zistiť, či vie niekto naozaj programovať a algoritmicky myslieť (čo si dnes o sebe myslí skoro každý), tak by som mu dal počítač a požiadal ho, nech mi do hodiny povie riešenie tejto úlohy :-)

* Pôvodne som formuloval úlohu so slovom "inej" a takáto úloha je zmysluplná a tiež pomerne obtiažna, pričom ju vyriešil Nanyk (pozri komentáre). Pôvodný zámer bol však taký, že dané riešenie musí dostať robota do miestnosti A aj ak ten robot začína v priamo v A. Pri riešení tohto pôvodne zamýšľaného problému sa však možno dajú Nanykove myšlienky použiť ...

10 komentárov:

Nanyk povedal(a)...

Mam take obskurne nezaujimave riesenie.

Pozerajme sa na vec tak ze mame sucasne 4 robotov na vsetkych moznych poziciach a chceme aby sa postupne "spojili" v A. Oznacme vrcholy grafu 1,2,3,4,A kde 3 je stredny a 4 nalavo od A a 2 nad A.

Potom jediny sposob ako sa mozu dva roboty stretnut je ze budu na poziciach 2,3 a vydaju sa cestou M. Niekedy nastane prve take stretnutie, po nom ale ziaden robot nesmie byt na pozicii 2 (nevedie tam ziadna cesta M). Do pozicie 2,3 sa ale dva roboty mozu dostat len cestou konciacou CC, ak ziaden z nich nebol pred tym v 2(co je po prvom stretnuti plati). Takze druhe spojenie nastane prinajlepsom po dalsich 3 krokoch. Navyse po druhom spojeni su nejake roboty v pozicii A a este stale potrebujeme jedno spojenie. Na to aby sa robot dostal z A do 2 potrebuje aspon 3 kroky, konkretne MMC, lenze zo ziadneho vrcholu sa neda cestou MMC dostat do 3 (analogicky aby sa dostal z A do 3 potrebuje aspon 3 kroky MMM, takym sposobom sa ale nejde dostat do 2 odnikial), takze z A budu roboty musiet putovat cestou dlzky aspon 4 tak aby sme mali dva roboty v poziciach 2,3 ked nastane finalne spojenie. Celkovo teda musi mat cesta dlzku aspon 9. To ze taka cesta existuje dosvedcuje M CCM MMCCM.

Radoslav Harman povedal(a)...

Oh, Nanyk. Tak ako som napísal zadanie je Tvoje riešenie zdá sa správne a je to naozaj dobrý výkon!

Avšak ja som sa vo formulácii zadania pomýlil; sorry. Namiesto "z akejkoľvek inej miestnosti" malo byť len "z akejkoľvek miestnosti", rovnako ako v predchádzajúcej úlohe. Pokúsim sa to v zadaní vhodným spôsobom zmeniť.

Nanyk povedal(a)...

ok:) potom som presvedceny ze optimalne riesenie je M CCM MMCCM MMCCM, pretoze priamym pouzitim postupu z povodneho riesenia (cast "druhe spojenie nastane prinajmensom po dalsich 3 krokoch") dostaneme spodny odhad 12. neviem ale odovodnit nutnost dalsich 2 krokov, iste by sli oddiskutovat prehlbenim argumentu, ale to nema cenu, radsej necham priestor nejakemu algoritmu..

Radoslav Harman povedal(a)...

OK Nanyk. Aj keď nevieš "odôvodniť nutnosť ďalších dvoch krokov" tak je obdivuhodné, že si bez počítača našiel uvedené riešenie.

Nechajme teda na nejakého šikovného programátora zistiť, či je toto riešenie najkratšie a ak je, tak či je jediné.

Hermi povedal(a)...

Takže Nanykove riešenie je skutočne najkratšie a žiadne iné takej dĺžky neexistuje.

Radoslav Harman povedal(a)...

Hermi: vitaj na QED. Áno, je to tak, Nanykove riešenie je najkratšie a jediné aj podľa mojich výpočtov.

Tak čo, už si dočítal TGD ? :-)

Hermi povedal(a)...

Este sa mi nepodarilo, je to podla mna pisane tazkopadnejsie ako ine jeho knihy a viac rozvlacne (asi s prihliadnutim k cielovej skupine), takze sa to necita tak dobre ako ostatne.

Radoslav Harman povedal(a)...

Hm. No, Nobelovu cenu za literatúru mu to nezíska a aj veľa iných vecí sa mu dá v tejto knihe vyčítať, napríklad príliš provokačné formulácie, ale ja som to aj tak prečítal rýchlo a celkovo mi tá kniha všeličo dala. Inak Ježiško (ehm) mi už z Amazonu objednal na Vianoce jeho najnovšiu knihu, na ktorú sa naozaj teším.

Charon ME povedal(a)...

Ked si kladiem otazku z ktorych vrcholov sa dostanem do vrcholu X cez C (prva vetva bin. stromu) respektive cez M (druha vetva), spisem si ich a idem dalej: z ktorych vrcholov sa mozem dostat do tychto vrcholov cez C resp. M? atd. tak mi vznika pekny binarny stromcek. Ked natrafim na mnozinu vrcholov, ktoru som uz niekde mal alebo ktora je podmnozinou inej, tak v tej vetve uz nepokracujem. Strom vetvim az kym sa nedopracujem k vsetkym 5 vrcholom a potom spetne precitam akymi vetvami som isiel. Ked v jednom kroku idem vo vsetkych otvorenych vetvach do hlbky o jeden krok, zarucujem tym optimalnost prveho najdeneho riesenia. Takto som sa na papieri a4 dopracoval k uz vyssie spomenutemu rieseniu.

Radoslav Harman povedal(a)...

Charon: Inteligentný postup. Takto sa naozaj dajú riešiť podobné úlohy aj "ručne".