Tento príklad je motivovaný istou úlohou z knihy Ivan Moscovich: The Big Book of Brain Games.
Poznámka 3.11.: V komentároch ma upozornil misof na to, že táto úloha je príbuzná jednému otvorenému problému, ktorý súvisí s Československom. Tak som sa na to trochu pozrel a naozaj! Jedným z najznámejších otvorených problémov teórie konečných automatov je takzvaná Černého domnienka, ktorá vychádza z článku Jána Černého publikovaného priamo v slovenčine! Ako je možné, že to nepatrí ku "common knowledge" aspoň medzi slovenskými matematikmi?
Ak chcete o tomto probléme vedieť viac, tak si môžete prečítať tento pekný článok. Ale v zásade sa jedná o nasledovné: Predpokladajme, že máme podobný diagram ako v našej úlohe, pričom miestností je n a existuje nejaká pevná postupnosť príkazov, ktorá pošle robota do danej miestnosti z akejkoľvek inej miestnosti. Potom existuje aj postupnosť príkazov, ktorá toto spĺňa a jej dĺžka nepresahuje (n-1)2. Černého diagram stupňa 5, v ktorom je najkratšie riešenie dĺžky 16, je znázornený na nasledovnom obrázku. (Viete to riešenie nájsť?)
Pojmenuju si dalsi vrcholy ve smeru cervene sipky z A na B C D E. Po sekvenci MMM jiste robot skonci bud v A, E nebo C. Nyni po prikaze C bude v mistnosti B nebo D. Kdyz mu nyni dame sekvenci CMC, mel by se nachazet v mistnosti B. Odsud uz se snadno dostaneme do A, takze vysledna sekvence je: MMMCCMCMM.
OdpovedaťOdstrániťCMCCCCM je kratsia a mala by tiez fungovat.
OdpovedaťOdstrániť(Jestli se nemylim;)
Pre jednoduchú orientaciu, oznacme vrcholy v smere cervenej sipky z A cislami 1, 2, 3, 4. Vsimnime si, ze v grafe sa nachadzaju cykly. Cerveny cyklus z vrcholov 1, 2, 3, 4 a modry cyklus z A, 2, 4. Prva strategia je C, to nam zaruci, ze nie sme v A, t.j. sme v cervenom cykle. Na to, aby sme sa dostali do modreho cyklu potrebujeme aspon dva tahy modrou (z 1 potrebujeme dva, z 3 jeden a z 2 a 4 nula). V pripade dvoch tahov M by sme modli skoncit v A, ale po 3 tahoch M urcite v A nie sme (modry cyklus ma dlzku tri a v A urcite nie sme, lebo sme zacali cervenou). Po troch M sme bud v 2 alebo v 4. Teraz dame strategiu MCMCM:
OdpovedaťOdstrániť2 M 4 C 1 M 3 C 4 M A
4 M A C 1 MCM ako predchadzajuce.
Takze strategia ktora nas z kazdeho vrchola dopravi do A je C MMM MCMCM
Fú; to bola bleskovka. Fajn. Najkratšie riešenie našiel druhý anonym, ale za tými dvomi zvyšnými riešeniami je zasa vidieť ako sa k nim dá logicky dopracovať. Inak, priznám sa, po tom, čo som si tento problém formuloval, som si ja sám našiel riešenie, ktoré je ešte dlhšie: MMCMMMMCMM. Ale to tiež preto, že je založené na v istom zmysle "univerzálom" postupe ako takéto riešenia konštruovať.
OdpovedaťOdstrániťOtázkou už zostáva len to, či neexistuje riešenie, ktoré má dĺžku menej ako 7, ale to už dosť pochybujem.
CMCCMM
OdpovedaťOdstrániťCMCCMM
Takze Ako navigovat robota II bude asi o univerzalnom algoritme? :D
OdpovedaťOdstrániťCelkom zaujímavý a starý open problém (dokonca pochádzajúci od nás z Československa :) ) je s týmto spojený, viď napríklad http://en.wikipedia.org/wiki/Synchronizing_word
OdpovedaťOdstrániťRori: Super! No toto...
OdpovedaťOdstrániťVladimír: No taký bol pôvodný zámer, ale uvidíme, kedy si na to nájdem čas.
misof: Veľmi zaujímavé. Ďakujem za upozornenie; dám to ako poznámku k hlavnému článku.
Vcera som to stihol iba pastnut - nestihal som napisat komentar....
OdpovedaťOdstrániťKonecne som mohol vyuzit svoje programatorske schopnosti :) kedze dlzky 7 mi uz vyfukli a tak mi zostal brute force a pocitac :) inak je to jedine 6kove riesenie...
Rori: No pekne. Keď už máš ten program, mohol by si sa pokúsiť nájsť podobný diagram, v ktorom však optimálne riešenie bude dlhšie (povedzme taký diagram, v ktorom nie sú slučky, alebo násobné hrany, lebo s týmito by sme sa dostali práve k Černého diagramu). Ak máš čas samozrejme.
OdpovedaťOdstrániťNo pozriem sa na to, problem je ze na cisto brute force metodu je treba vyskusat 625000000 moznosti ( 9765625 moznych grafov a pri kazdom 64 moznych pokusov) - ale ked sa nad tym clovek zamysli tak je tam straaaaasne vela rovnakych grafov - len urcite transformacie... A kedze to mam doma a nie v robote - tak ak sa niekomu chce vymysliet rozumny sposob generovania vsetkych moznych grafov :) ... Mozno by bola zaujimava uloha urcit kolko je takych jednoznacnych :)
OdpovedaťOdstrániťinak k tomu Cernehoho diagramu - moj tip je CMMMMCMMMMCMMMMC
OdpovedaťOdstrániťRori, tých diagramov je naozaj len niekoľko, ak izomorfné diagramy považujeme za jeden a ten istý diagram (t.j. dva diagramy považujeme za rovnaké ak sa líšia len očíslovaním vrcholov a prípadne výmenou farieb.) Pre prípad, že každý vrchol je spojený s každým nejakou orientovanou cestou, nemáme násobné hrany ani slučky a z každého vrchola vychádza práve jedna červená a práve jedna čierna hrana, tak som našiel iba dva takéto grafy. Z grafu uvedeného na obrázku je možné spraviť ten druhý tak, že modrý cyklus dĺžky 3 opačne orientujeme. Ale ak by si chcel nájsť nejaký zaujímavý diagram, tak nemusíš prechádzať systematicky všetkými diagramami. Stačí náhodne vygenerovať pár tisícok (povedzme, že pripustíš aj slučky, ale nie násobné hrany) a z nich vyberieš ten najzaujímavejší (napríklad s najdlhším optimálnym riešením). Ak je tých tried neizomorných grafov málo, tak s veľkou pravdepodobnosťou natrafíš aspoň na jedného reprezentanta tejto triedy.
OdpovedaťOdstrániťInak to Tvoje riešenie Černého diagramu je správne. (Program, alebo si to tak rýchlo uvidel sám? :-)
Riesenie Černého diagramu bolo "by ocko" - vcera ked som sa hral s riesenim toho prveho tak clovek dostane "feeling" ako riesit :)
OdpovedaťOdstrániťZaklad je proste zmensovat "mnozinu moznych bodov" - zacnem ABCDE a transformaciami C/M upravujem tu mnozinu tak aby nakoniec zostalo iba A...
Kedze komentar moze byt len 4096 znakov a mne sa to sem nezmestilo tak sa grafy s dlzkou riesenia 17 a 20 nachadzaju na mojom blogu :)
OdpovedaťOdstrániťhttp://hladajuci-muz.blogspot.com/2009/11/qed-ako-navigovat-robota-i.html
Rori: Super.
OdpovedaťOdstrániťTIe grafy so slučkami zodpovedajú Černého grafom len s rôznymi permutáciami vrcholov B,C,D,E a s prípadnou zámenou orientácie hlavného cyklu. To je spolu oných 2x4!=48 prípadov. Inak pripomeniem, že v prípade Černého diagramov sa hovorí o najdlhšom optimálnom riešení 16, lebo tam stačí dostať robota do akejkoľvek spoločnej známej miestnosti, zatiaľčo v našej formulácii to musí byť práve miestnosť A, takže tam vyjde najdlhšia optimálna cesta 20.
Čo sa týka tých grafov bez slučiek, môžem z toho spraviť úlohu, Rori? (Samozrejme s kreditom na Teba.) Len prosím neprezrádzaj riešenie (t.j. navigačnú postupnosť.)
Tento komentár bol odstránený autorom.
OdpovedaťOdstrániťSom tam mal zly preklep tak este raz :)
OdpovedaťOdstrániťKludne :) budem len rad :)
A postupnost este nemam - hladanie dlzky cesty uz nebol tvrdy brute force ale podla mna zaujimavy algoritmus :) pri ktorom sa najde sice minimalna dlzka ale nenajde sa konkretna cesta...
Ak je zaujem tak ten c# program mozem dat na blog...
inak z neho vyplyva ze pre lubovolny graf je max cesta ohranicena zhora 2^n pricom n je pocet vrcholov... ale predpokladam ze tato vec uz bola niekym odhalena :)
OK. Už som si niektoré z tých grafov bez slučiek pozeral a musím priznať, že ma riešenie (t.j. navigačná postupnosť do miestnosti A) do nejakých 15 minút nenapadlo. Bude to fajn úloha.
OdpovedaťOdstrániťČo sa týka toho algoritmu, tak si neviem zatiaľ predstaviť ako sa dá zistiť dĺžka optimálneho riešenia pre nejaký graf bez toho, aby sa optimálne riešenie popri tom aj skonštruovalo. Samozrejme to, že si to neviem predstaviť, neznamená, že taký algoritmus neexistuje :-)
Čo sa týka tej hranice 2^n; myslím, že som čítal, že už našli horné ohraničenie kubickým polynómom. Ale aj tak je celkom fajn, že si takéto ohraničenie našiel, lebo ani to nie je až také triviálne.
To s ohraničením dĺžky tej postupnosti hodnotou N^3 som zrovna minulý rok dával druhákom informatikom ako prémiovú úlohu z Formálnych jazykov a automatov :)
OdpovedaťOdstrániťAk to niekoho zaujíma, moje "rozprávkové" zadanie aj riešenie sa dajú nájsť tu: http://foja.dcs.fmph.uniba.sk/materialy/alibaba.pdf
Algoritmus a aj dovod preco nepoznam postupnost najkratsej cesty je zas na mojom blogu:
OdpovedaťOdstrániťhttp://hladajuci-muz.blogspot.com/2009/11/qed-ako-navigovat-robota-i-ako-na-to.html
misof: No, keby som mal o dvadsať rokov menej, tak by som možno použil slovo "husté". Pretože to je lepšie ako horná hranica uvedená Černým v jeho prvom článku a momentálne najlepšia hranica je podľa Volkovovho článku (n^3-n)/6. Koľko študentov to vyriešilo?
OdpovedaťOdstrániťRori: Už rozumiem! OK; pekná myšlienka. Vybral som z tých Tvojich "ťažkých" grafov bez slučiek jeden, ten som trochu zmenil a uvediem ho ako ďalší príspevok.
misof: k Tvojmu dokazu - urcite plati ze "Teraz si uz len stací uvedomit, ze v kazdom kroku zmensíme pocet komnát, kde sa zbojníci môzu nachádzat,aspon o 1."?
OdpovedaťOdstrániť