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