Nazdar, Paco napisal: >> programuju si čistě pro svoji potěchu takovou logickou hříčku >> v Javascriptu a teď jsem narazil na docela zásadní problém. Ve >> čtvercové síti, řekněme 10x10 čtverců, je výchozí a cílový bod, >> každý v jiném čtverci. Dále se v síti nacházejí překážky, které >> je potřeba inteligentně obejít. Zajímalo by mě obecné řeąení, >> jak najít optimální cestu z výchozího do cílového bodu, aniž by >> se objekt někde zaseknul ,nebo se nevracel na místa, kde už byl, >> apod. Prostudoval jsem si nějaké materály o této problematice a >> vyplynulo z nich, že hledání cest patří mezi složitějąí, takže >> si nedělám iluze o tom, že bych to dokázal naprogramovat. Přesto >> by mě zajímalo, jestli někdo už něco podobného nepsal, nebo >> aspoň teorerticky neřeąil. Díky Terr > Skutecne obecne - tedy ciste matematicke - reseni predpoklada > hluboke znalosti topologie a konkretne tzv. teorie grafu, ktere > patri mezi par nejslozitejsich odvetvi matematiky. Krome toho > mi zrovna tohle na HLEDANI cesty grafem nesedi, protoze to > predpoklada, ze objekt JIZ PREDEM zna parametry grafu (tedy cele > bludiste) a cestu si proste spocita, coz IMHO neni zrovna to, > co jsi chtel. Mne sa naopak vidi, ze Terr chcel prave hladat optimalne cesty v grafe, ktory pozna. Inak ak by chcel prechadzat graf bez toho aby ho poznal (cely videl), tak je to potom klasicka uloha na prechod bludiskom (vidi iba jeden stvorcek pred sebou) a cela tvoja dalsia uvaha je chybna pretoze to nedokaze ziadne AI, ani tvoje empiricke riesenie bez toho aby sa bolo treba vracat niektorymi chodbami ako to Terr pozadoval (kedze nevidi cely graf, napr. nemoze nijako rozhodnut ci chodba do ktorej chce ist je slepa alebo nie). Prechod bludiskom riesi algoritmus "Ariadnina nit". Mne sa vidi ze Terr chcel najst optimalnu (=najkratsiu) cestu z jedneho bodu do druheho. Nato sa pouziva Dijkstrov algoritmus. Pripadne ked hlada maticu najkratsich vzdialenosti z vsetkych uzlov do vsetkych tak Floyd-Warshallow algoritmus. > Myslim, ze zajimavejsi by tady bylo empiricke reseni... [delete velka uvaha] > Je mi jasne, ze jsem ti vlastne poskytl jen 'moudre kecy' a nijak > nepomohl s vlastnim resenim, ale ono to skutecne neni trivialni, > i kdyz by to tak pri pohledu na mrizku 10x10 mohlo vypadat... PS: urcite to nieje dobry napad robit to v JavaScripte. Ak ti to pomoze mozem ti vsetky tu spomenute algoritmy poslat v pascale, ale ked nevies nic z teorie grafov tak ti to moc nepomoze. S pozdravom, Michal Bilcik (ICQ# 156366308) -- Bůh je reálný, pokud nebyl deklarován jako integer.
This archive was generated by hypermail 2.1.2 : 14. 06. 2002, 22:48 CEST