> 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. Myslim, ze zajimavejsi by tady bylo empiricke reseni, kde objekt bude mit v pameti celou matici, na zacatku cesty cistou, a pri postupnem prochazeni si bude u kazde bunky zaznamenavat faktory potrebne pro dalsi vyvoj cesty. Ale nebude jich malo a nebude vubec trivialni je potom spravne vyhodnocovat pro vyvoj dalsi cesty. Budou to asi predevsim: - volne smery z bunky - zavrene smery z bunky - jiz pouzite volne smery a jejich vysledek - historie pruchodu aktualni bunkou (orientovana!) - atd... Ale uvedom si, ze to vse bude velice rychle narustat a velice brzy se v tom totalne zahrabes. Ono totiz i takovehle empiricke reseni, ma li byt skutecne exaktni a komplexni, vyzaduje pouzit postupy z oblasti AI. Takze bych spise tomu objektu dovolil urcita chybna rozhodnuti, jako napriklad obcasne navraty na mista, kde uz (neuspesne) hledal, pouzil bych nahodne (i kdyz redukovane) rozhodovani, a cely postup zapisu a vyhodnocovani parametru dane bunky bych aproximoval jen na nejnutnejsi faktory potrebne k tomu, aby se mi ten objekt nekde nezacyklil a/nebo nezasekl. 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... pako Paco. ______________________________________________________________________ Reklama: Mapy Prahy, Brna a Cech najdete na http://www.mapy.cz
This archive was generated by hypermail 2.1.2 : 14. 06. 2002, 12:05 CEST