Bludiště - jak vytvořit algoritmus?

[Numeriprimi]

Zdravím.
Máte určité bludiště- množinu bodů v rovině - definovaný střed těchto bodů a poloměr.
Jste uprostřed, opět definice střed, poloměr, a potřebujete se dostat ven nejkratší možnou cestou.

Jak vytvořit algoritmus?
Prosím případně o popis jak pro úplné trdlo, potrvá mi tomu porozumět.

Mockrát děkuji.

[Reklama]

[CZechBoY]

pudu jednou cestou, když nebude slepá tak pudu dál a budu se snažit jít pořád z kruhu
logický ne?

[Numeriprimi]

No tak to mi je celkem jasné... Ale horší je pro mě je to přenést do algoritmu. Matematiku zvládám, ale s tímhle nemám moc zkušeností, tak nevím, jaké funkce využít.

[faraon]

Ty body jsou místa kam můžeš skákat? Podle jakých pravidel? Kdyby to bylo libovolně, tak by stačilo najít bod ležící zvenku nejblíž tomu poloměru a skočit rovnou na něj! Takže Pythagorova věta:

Kód: Vybrat vše

sqrt((xi-x0)^2 + (yi-y0)^2)

Nebo je to naopak, že na ty body nesmíš vstoupit a musíš prokličkovat mezi nimi?

[Numeriprimi]

Nene, nejspíš jsem to špatně popsala... Neskákat, ale prokličkovat :-) Vymanipulovat se mezi nimi, žádné nějaké "naklánění" apod.

[faraon]

Takže ty body jsou různě velká "kolečka", a ty musíš s dalším kolečkem mezi nimi nějak projet ven. Teď to mám správně?

[Numeriprimi]

Ano, přesně takto to myslím :-) A pokud možno nejkratší možnou cestou.

[faraon]

Tak zjistit jestli projdeš mezerou nebude tak těžké, ale vymysli jak spočítat délku té dráhy včetně obloučků:

Numeriprimi.png (5.7 KiB) Zobrazeno 921 x

Asi by bylo jednodušší přičíst poloměr toho utíkajícího bodu ke všem ostatním a pohybovat se po tečnách.

A další otázka - jak poznám že už jsem "venku" z toho bludiště?

[Numeriprimi]

Ještě dodám, že věc se má tak, že překážky mohou mít různý poloměr... Ale to snad nebude problém?

K otázce... Sama nevím. Nejspíš jen najít algoritmus, tak se z toho "vydrápat".

[faraon]

Různý poloměr nevadí, stejně se ty puntíky budou zpracovávat postupně. Tak postup bych navrhoval asi takhle:

1. K poloměru všech překážek přičíst poloměr toho cestovatele. Šlo by to i během hledání, ale je to počítání navíc, a složitější vzorečky. Takhle pak stačí pracovat s bodem s nulovou velikostí.

2. Z výchozího bodu brát postupně všechny překážky, a k nim vypočítat tečny k součtu průměrů (pozor, každá má dvě!).

3. Pokud tečna neprotíná žádnou jinou překážku (zase oba průměry), tak se hledá společná tečna k další překážce (rekurze na bod 2.), dokud se cestovatel nedostane na hranici N-úhelníku vytvořeného středy všech překážek. To je ta černá čára kolem.

4. V tu chvíli kdy je na hranici (průnik kružnice se spojnicí středů) se sečtená délka dráhy porovná s nejkratší doposud nalezenou, a pokud je kratší, tak se nahradí.

Ale jak tohle všechno spočítat se mě fakt neptej, kdysi na střední jsme nějaké protínání počítali, ale to je asi tak všechno co si z toho pamatuji
Ta dráha by se dala ukládat do pole nebo do spojového seznamu.

Numeriprimi2.png (4.53 KiB) Zobrazeno 921 x

[faraon]

Zapomněl jsem jednu důležitou věc, takže:

5. Když dojdeš na hranici, nebo do slepé uličky, tak se vrátíš o jednu úroveň zpátky a vyzkoušíš další tečnu, tak dlouho dokud tam nějaké neotestované jsou.

Nakonec, po vyčerpání všech možností, budeš zase stát na výchozím bodě, a budeš mít zaznamenanou nejkratší možnou cestu na hranici té plochy. Pokud bude víc stejně dlouhých, tak jen tu první nalezenou.