Autor Zpráva
Leopik 2x
Profil
Táto otázka ani tak nepatrí do PHP, je to skôr také všeobecné ale... Ako nájdem cestu medzi bodmi A a B? Príklad:
Mám obrázok o veľkosti 100x100px a 2 body na súradniciach 95x95 a 10x10. Tieto body majú farbu #000000 a medzi nimi vedú 2 čiary. Jedná má farbu #111111 a druhá #222222. Čiara s farbou #111111 ich spája kratšou vzdialenosťou. Ako zistím pomocou scriptu, ktorá z nich je kratšia?
Alphard
Profil
Leopik 2x:
Ako nájdem cestu medzi bodmi A a B?
Potřebujete mapu rozdělenou na cesty a uzly. V podstatě se testují všechny možné trasy, dokud ostatní možné nejsou delší než nejkratší nalezená. Pro urychlení lze použít i centrální uzly, mezi kterými jsou trasy již nalezené. Ale tohle váš problém zřejmě neřeší.

Jakou formu mají ty čáry, nestačilo by porovnat počet pixelů dané barvy?
Leopik 2x
Profil
Porovnať farby by nestačilo, pretože to som len uviedol ako príklad, aby sa to rozlíšilo. Oni sú vždy 1 farby. Síce som si nevedel predstaviť, ako zistiť to, ktorá trasa je najkratšia bez toho, aby som prechádzal každú jednu zaradom no ale keď to inak nejde tak to budem musieť asi urobiť tak.
Každopádne ďakujem za odpoveď
Alphard
Profil
Leopik 2x:
Nejlepší by bylo, kdybyste sem dal ukázku vašeho obrázku. Obecné řešení tohoto problému není snadné.
Leopik 2x
Profil
Zatiaľ nemám žiaden obrázok, len rozmýšľam, ako by to bolo najlepšie. Ide o to, že sa zadá východzia súradnica, cieľová súradnica a začne sa hľadať najkratší spoj medzi nimi. Cesty budú zapísané v databáze.
_es
Profil
Leopik 2x:
Cesty budú zapísané v databáze.
Tak potom k tomu nepotrebuješ žiadny obrázok, ale priamo vyrátaš dĺžky trás.
Cesty budú zapísané akým spôsobom?
Leopik 2x
Profil
Každý bod (kus cesty) zvlášť. Teda cesta od 5x5 do 5x7 bude zapísaná: 5x5, 5x6, 5x7. A z takejto kopy dát by som chcel nájsť najrýchlejšiu cestu.
jabloň
Profil *
Ahoj,
koukni se na dijkstrův algorytmus. Jde vlastně o hledání nejkratší cesty v grafu.
_es
Profil
Leopik 2x:
Ten problém je trochu zložitejší.
Môžu byť na mape aj slepé cesty?
Bude vždy platiť, že v tom zápise sa bude x-ová aj y-ová súradnica meniť najviac o 1?
Ako budeš mať zapísaný šikmý smer, teda môžu sa zmeniť súčasne obe súradnice v jednom kroku?
Podľa toho, v akom tvare sú dáta zapísané, bude pre každý spôsob existovať veľa rôznych algoritmov.
Leopik 2x
Profil
_es
1.Môžu byť na mape aj slepé cesty? : Áno môžu
2.Bude vždy platiť, že v tom zápise sa bude x-ová aj y-ová súradnica meniť najviac o 1? : Áno
3.Ako budeš mať zapísaný šikmý smer, teda môžu sa zmeniť súčasne obe súradnice v jednom kroku? : Nie, vždy sa bude meniť maximálne 1 súradnica
jabloň
Profil *
Jedna otázka, není náhodou jedno kde je uzel položen? Přeci hledáš nejkratší cestu z bodu A do bodu B a důležitá je pro tebe cesta která je ohodnocená a ta může precí vést nohoru dolu, je to jedno.
_es
Profil
Leopik 2x:
vždy sa bude meniť maximálne 1 súradnica
To je ďalšia komplikácia.
Potom nastáva ďalšia otázka, aké dlhé sú šikmé čiary?
Ak by si to rátal po jednom kroku, potom by ti vyšlo, že rovná čiara z (0, 0) do (10,10) má dĺžku 20, lebo by to rátalo ako dĺžku schodov.
Leopik 2x
Profil
No ale aj tak by to bola tá najkratšia cesta z A do B pretože keby to šlo dole a potom do prava tak by to bolo 20 takže to sedí alebo nie?
_es
Profil
Leopik 2x:
ale aj tak by to bola tá najkratšia cesta z A do B
Ale ak by si mal ešte jednu cestu, ktorá by nešla z A do B takto priamo, ale by bola zalomená, najprv rovno doprava a potom hore k B, tak by vyšla rovnaká vzdialenosť ako priama úsečka, čo v skutočnosti neplatí.
Kacko
Profil
Leopik 2x:
A*
Leopik 2x
Profil
OK, pozriem sa na to A*, vyzerá to na to, čo hľadám.
Leopik 2x
Profil
No trocha som už aj pochopil to A* ale nejako nerozumiem tomu, ako nájsť cestu späť.
WanTo
Profil
Leopik 2x:
Zběžně jsem si pročetl diskuzi - jestli máš obrázek "bludiště", tedy mřížku, kde je vzdálenost každých dvou pixelů sousedících hranou (tedy ne diagonálně - rohem) stejná, jednotková, navíc nejde cestovat skrz roh pixelu po diagonále, tak vůbec nepotřebuješ Dijkstru ani A*. Bohatě ti stačí poměrně jednoduché prohledávání do šířky - najdeš nejkratší cestu podle jedné barvy, pak podle druhé barvy, porovnáš délky cest a je to.

Jinak cestu zpět (i v A* a Dijkstrovi) najdeš tak, že si u každého pixelu resp. vrcholu grafu zapamatuješ, odkuď jsi do něj přišel. Každopádně jestli ti jde jen o délku cesty, tak tohle u prohledávání do šířky vůbec nepotřebuješ, mělo by ti stačit pamatovat si, kolik jsi vybral pixelů z fronty.
Leopik 2x
Profil
Teda zo štartovného bodu budem mať 4 susedov, ďalej pre každého tohto jedného suseda ďalších 4...?
WanTo
Profil
Tak nějak. Do fronty nejdřív přidáš počáteční bod, pak v každém kroku odebereš z fronty první bod, zkontroluješ, jestli náhodou nejde o cíl, a když ne, tak daný bod označíš jako navštívený (můžeš na to použít třeba dvourozměrné pole) a do fronty přidáš ty z jeho 4 sousedů, kteří mají požadovanou barvu a zároveň ještě nebyli navštívení. Algoritmus skončí buď nalezením cíle nebo vyprázdněním fronty, pokud cesta z počátku do cíle neexistuje.

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: