piatok, 6. novembra 2009

Q.E.D. : Ako navigovať robota I - ako na to

Predchádzajúcom príspevku som len ukázal výsledok, ale nie postup ako som sa k nemu dopracoval. Tak teraz to naprávam :)

V prvom rade si človek musí uvedomiť jednu vec, že riešením úlohu je vlastne transformácia množiny. Prvky množiny sú miesta kde sa v danom kroku môže nachádzať robot a transformácia je určená modrou alebo červenou cestou. Takže na začiatku množina obsahuje prvky {A,B,C,D,E} a snažíme sa postupnými úpravami dostať množinu {A}. Ak zoberieme graf z "Ako navigovať robota I" tak potom z prvého kroku {A,B,C,D,E} po transformácii M (modrá) dostaneme {A,B,C,D} a keď znova použijeme transformáciu M tak dostaneme {A,B,D}. Teraz vytvoríme nový graf pričom vrcholy sú všetky možné podmnožiny množiny {A,B,C,D,E}, ktoré sú pospájane jednosmernými hranami definovanými M a Č transformáciami. Úloha sa nám teraz vlastne zredukovala na nájdenie najkratšej cesty z vrchola {A,B,C,D,E} do vrchola {A}.

Toto všetko je výhodné v prípade ak riešime úlohu na počítači. Výrazne nám to redukuje počet krokov ak by sme použili "brute force" a hľadali všetky možné cesty. Vytvorenie grafu je lineárna záležitosť a potom už existuje viac stratégií ako nájsť najkratšiu cestu. Ja som použil prehľadávanie do šírky čo znamená, že prvý vrchol má nastavenú vzdialenosť 0 a ostatné -1 a potom v každom kroku i kontrolujem kam sa dostanem z vrcholov so vzdialenosťou i - 1 pričom uvažujem iba o cieľových vrcholoch ktoré ešte nemajú priradenú vzdialenosť. V každom kroku môžu nastať 3 možnosti:

  1. Ak nenájdem žiaden nový vrchol tak neexistuje cesta
  2. Dostali sme sa do cieľového vrcholu a v tom prípade minimálna vzdialenosť je i
  3. Ak neplatí 1. ani 2. tak pokračujeme krokom i + 1

Z daného postupu vyplýva, že počet krokov pre ľubovoľný počet vrcholov pôvodného grafu nemôže byť minimálna cesta ak existuje dlhšia ako je počet všetkých podmnožín a to je 2n. A to platí pre ľubovoľný počet transformácii (teda nie len pre 2 ako je použité v našom prípade).

Ak chceme nájsť maximálnu minimálnu cestu zo všetkých možných grafov - stačí generovať všetky možné grafy a vypočítať daným algoritmom najkratšiu dĺžku. Na priemernom počítači to trvalo menej ako 30s.

A ďalšia zaujímavá vec vyplýva z použitého algoritmu na nájdenie najkratšej dĺžky - pokiaľ si nepamätáme ako sme sa dostali do ktorého vrchola, čo je pre nájdenie minimálnej dĺžky zbytočné, tak na konci nie je známa postupnosť transformácií pre danú minimálnu cestu...

Žiadne komentáre:

Zverejnenie komentára