2 cella távolsága?

Fórumok

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.

Hozzászólások

Szerkesztve: 2024. 02. 06., k – 05:42

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

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á :)

lehet sqlben ilyet, ajanlott hozza window function es/vagy recursive query ha jót akarsz.

plus hasznalhato graf reprezentáció szoba,szoba,koltseg minimum

Kerdeskent mar csak azt latom, hogy letezik-e sikba (vagy N dimenzios terbe) rajzolhato grafra valami okosabb algoritmus, mint az altalanos megoldasok.

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.

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?