Van egy csomó egyforma cellám (szoba), ezeknek O oldaluk van, a szomszédjaikkal 1-1 oldalon kapcsolódnak = 1 közös faluk van.
Az egyszerűség kedvéért a szomszéd szobába mindig át lehet menni, vagyis az ajtók nincsenek egyik irányból sem zárva.
A feladat azt kitalálni, hogy 2 random szoba milyen messze van egymástól, a távolságot mérjük mondjuk "ajtó"-ban, Hány ajtón kell minimálisan átmenni, hogy A-ból B-be jussunk.
A legegyszerűbb ilyen, ha négyzet alakú szobák vannak, 4-4 ajtóval, szépen, mint a füzetben. Erre gyorsan ki lehet találni egy magik képletet, ami a poziciójuk alapján megmondja.
De mondjuk általános esetben? Mondjuk 6 oldalú szobák esetén. Netán szélsőséges esetben, pl. Ha Voronoj-celláim vannak?
Vagy ha nem egyformák a szobák?
- Bonyolítja kicsit, hogy kell majd hozzá vmi model is, jellemzően SQL-ben szeretném az egészet aszalni.
- Jó lenne, ha majd lehetne írni egy egyszerű, tömör, zárt query-t, ami 2 cella-ID alapján megmondja a tutit. Szóval geometriai megoldások egyelőre visszafogottan érdekelnek.
Lehet ezt még bonyolítani, pl. ha "lyukak" is vannak (mint a keresztrejtvényben), vagy nem minden ajtó nyitható. De ezeket most hagyjuk.
Az mondjuk már félig megoldás, ha a tisztelt közösség nevesíteni tudja a problémát, olvasni tudok.
TIA.
- 826 megtekintés
Hozzászólások
Ha négyzet alakú szobák vannak, akkor két cella távolsága egyszerűen a Manhatan távolság. Ha nem négyzetes cellákból áll a háló, akkor valamelyik másik taxicab metrics lesz a válasz.
Csaba
- A hozzászóláshoz be kell jelentkezni
- A hozzászóláshoz be kell jelentkezni
+1, ez adja magát hogy egy gráf, így tárolni is jobb gráf adatbázisban mint sql-ben, onnantól kezdve a fenti probléma egyetlen lekérdezés
- A hozzászóláshoz be kell jelentkezni
asszem ez most pont nem annyira jó, de másra pont adott 1 ötletet, szóval:
Nincs elbaxva, csak másra lesz jó.
- A hozzászóláshoz be kell jelentkezni
Pedig szerintem is valami hasonló lehet a megoldás. Ha egy cella tartalmazza a szomszédos cellák koordinátáit, és ez alapján számolod a távolságot, akkor a zárt ajtók kezelése triviális lesz.
Debian - The "What?!" starts not!
http://nyizsa.blogspot.com
- A hozzászóláshoz be kell jelentkezni
Pedig amit írtál, az pont ez a probléma: gráfban legrövidebb út keresése, amire a Dijkstra algoritmus való.
Az ajtók felenek meg az éleknek (1-es súllyal), a szobák/cellák pedig a gráf csúcsai. Ezzel a bonyolítások is megoldhatók (zárt ajtó (= végtelen, vagy nagyon nagy érték), ha egy ajtón áthaladásnak nagyobb az ára (nagyobb súlyú él), vagy ha esetleg nem 4 szomszédja van (nalakzat formája nem számít, csak a szomszédsági viszonyok)...
Egyetemen elsős házi volt egy ilyen feladat talán pascal programozásból, és 2. évfolyamon tanultuk meg az elméletet hozzá :)
- A hozzászóláshoz be kell jelentkezni
Dijksta es Bellman-Ford alap.
Ha mar IT portal, akkor distance-vector routing.
- A hozzászóláshoz be kell jelentkezni
lehet sqlben ilyet, ajanlott hozza window function es/vagy recursive query ha jót akarsz.
plus hasznalhato graf reprezentáció szoba,szoba,koltseg minimum
- A hozzászóláshoz be kell jelentkezni
Ez egy gráf. A szobák a gráf csúcspontjai, az ajtók azt jelentik, hogy két csúcspont között van él a gráfban.
Innentől kezdve tetszőleges erre használható legkisebb utat kereső gráfalgoritmus jó: https://en.wikipedia.org/wiki/Shortest_path_problem
- A hozzászóláshoz be kell jelentkezni
Kerdeskent mar csak azt latom, hogy letezik-e sikba (vagy N dimenzios terbe) rajzolhato grafra valami okosabb algoritmus, mint az altalanos megoldasok.
- A hozzászóláshoz be kell jelentkezni
Ezt hogy érted? A síkbarajzolhatóságnak nagyon jó szükséges és elégséges feltétele van, könnyen eldönthető (Kuratowski-tétel).
Vagy arra gondolsz, hogy a legrövidebb-út problémánál használjuk ki azt, hogy itt síkbateríthető gráfokról van szó?
Erre is van azért már kutatás: http://theory.stanford.edu/~virgi/cs267/papers/planar-sssp.pdf Első találat a Google-ben.
- A hozzászóláshoz be kell jelentkezni
Az A* (astar) játékfejlesztésben nagyon gyakran használt, rengeteg implementációval készen mindenféle nyelven. A tárolás és költségbecslő (vagy mi a neve) függvény lesz az érdekes inkább.
- A hozzászóláshoz be kell jelentkezni
Van, az A* ilyen. Ennek az a lenyeget, hogy az eddig megtett ut plusz innen a celig legvonalbeli tavolsagot probalja minimalizalni. Emiatt rogton jo iranyba indul el. Olyat is lehet, hogy a ket oldalrol elindulsz, es valahol taalalkozik a ket front. Ez hatekonyabb, de tobb memoriat foglal.
A legjobb a HNR (highway node routing), ez joreszt fix terkepen mukodik, es kell hozza valamennyi elofeldolgozas is. Ezt hasznalja az iGO. Valamikor 2012-13 kornyeken adott elo errol Hanak David a BME-n, en neten neztem akkor eloben, talan megtalalhato rola a video (17 masodperc alatt Moszkvabol Lisszabonig vagy valami ilyesmi cimmel, a vaarosok nem biztosak). Az algoritmus lenyege, hogy - elore kiszamolt - kulonbozo fontossagu utaid vannak, es ha egyszer felleptel egy magasabb szintre, onnantol egy olyan grafban keresel utat, ahol csak ezek a fontosabb utak leteznek. Ez dramaian meggyorsitja az utkeresest.
Erdekes kerdes meg, hogy a grafban mi legyen egy csucs es mi egy el. A "nyilvanvalo" valasztas, hogy az utcak az elek, a keresztezodesek meg a csucsok, amit az elek osszekotnek. A "nemtrivialis" valasztas az, hogy az utcak kozepere tegyuk a csucsokat, es azt kossuk ossze - iranyitott es sulyozott - elekkel, ahonnan atmehetunk a masikba kozvetlenul. Ez elegge egyszeruve teszi az "egyiranyu utca", "nem kanyarodhatsz balra", es hasonlo problemak lekezeleset.
A strange game. The only winning move is not to play. How about a nice game of chess?
- A hozzászóláshoz be kell jelentkezni
Erdekes kerdes meg, hogy a grafban mi legyen egy csucs es mi egy el. ...
Ez jo! Erdekes a tema, utanaolvasok picit tutira.
- A hozzászóláshoz be kell jelentkezni