02 novembra 2009

Ako navigovať robota I

Máme labyrint piatich miestností znázornený na ilustračnom obrázku. Medzi každými dvomi miestnosťami je práve jedna jednosmerná cesta, ktorá je buď modrá, alebo červená. V niektorej (neznámej) miestnosti tohto labyrintu je robot, ktorého síce nevidíme, ale môžeme mu posielať príkazy typu M (prejdi modrou cestou) a C (prejdi červenou cestou). Je možné vyslať robotovi takú postupnosť príkazov M/C, aby po jej vykonaní s istotou skončil v miestnosti A?

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ť?)

23 komentárov:

Anonymný povedal(a)...

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.

Anonymný povedal(a)...

CMCCCCM je kratsia a mala by tiez fungovat.

(Jestli se nemylim;)

Vladimír povedal(a)...

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:
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

Radoslav Harman povedal(a)...

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ť.

Otázkou už zostáva len to, či neexistuje riešenie, ktoré má dĺžku menej ako 7, ale to už dosť pochybujem.

Rori povedal(a)...

CMCCMM
CMCCMM

Vladimír povedal(a)...

Takze Ako navigovat robota II bude asi o univerzalnom algoritme? :D

misof povedal(a)...

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

Radoslav Harman povedal(a)...

Rori: Super! No toto...

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.

Rori povedal(a)...

Vcera som to stihol iba pastnut - nestihal som napisat komentar....

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...

Radoslav Harman povedal(a)...

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.

Rori povedal(a)...

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 :)

Rori povedal(a)...

inak k tomu Cernehoho diagramu - moj tip je CMMMMCMMMMCMMMMC

Radoslav Harman povedal(a)...

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.

Inak to Tvoje riešenie Černého diagramu je správne. (Program, alebo si to tak rýchlo uvidel sám? :-)

Rori povedal(a)...

Riesenie Černého diagramu bolo "by ocko" - vcera ked som sa hral s riesenim toho prveho tak clovek dostane "feeling" ako riesit :)

Zaklad je proste zmensovat "mnozinu moznych bodov" - zacnem ABCDE a transformaciami C/M upravujem tu mnozinu tak aby nakoniec zostalo iba A...

Rori povedal(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 :)

http://hladajuci-muz.blogspot.com/2009/11/qed-ako-navigovat-robota-i.html

Radoslav Harman povedal(a)...

Rori: Super.

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ť.)

Rori povedal(a)...
Tento komentár bol odstránený autorom.
Rori povedal(a)...

Som tam mal zly preklep tak este raz :)

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 :)

Radoslav Harman povedal(a)...

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.

Č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.

misof povedal(a)...

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 :)

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

Rori povedal(a)...

Algoritmus a aj dovod preco nepoznam postupnost najkratsej cesty je zas na mojom blogu:
http://hladajuci-muz.blogspot.com/2009/11/qed-ako-navigovat-robota-i-ako-na-to.html

Radoslav Harman povedal(a)...

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?

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.

Rori povedal(a)...

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."?