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
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ť ...
Mam take obskurne nezaujimave riesenie.
OdpovedaťOdstrániť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.
Oh, Nanyk. Tak ako som napísal zadanie je Tvoje riešenie zdá sa správne a je to naozaj dobrý výkon!
OdpovedaťOdstrániť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ť.
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..
OdpovedaťOdstrániť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.
OdpovedaťOdstrániťNechajme teda na nejakého šikovného programátora zistiť, či je toto riešenie najkratšie a ak je, tak či je jediné.
Takže Nanykove riešenie je skutočne najkratšie a žiadne iné takej dĺžky neexistuje.
OdpovedaťOdstrániťHermi: vitaj na QED. Áno, je to tak, Nanykove riešenie je najkratšie a jediné aj podľa mojich výpočtov.
OdpovedaťOdstrániťTak čo, už si dočítal TGD ? :-)
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.
OdpovedaťOdstrániť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.
OdpovedaťOdstrániť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.
OdpovedaťOdstrániťCharon: Inteligentný postup. Takto sa naozaj dajú riešiť podobné úlohy aj "ručne".
OdpovedaťOdstrániť