Router algoritmust keresek - OFFTO

[Veres Sandor]

>Bocs, ha kisse offto, bar sokaknak erdekes lehet. Egy panel autorouterhez,
>ternavigaciohoz is hasznalhato, algoritmust keresek.
>
>A kovetkezo a gond: Adott egy labirintus, amiben a folyosok sarkaiban,
>illetve a fordulokban, T, vagy + elagazasokban egy-egy csomopont van
>elhelyezve. (Osszesen 24, tehat nem tul sok) Ebbol 4DB kereszt, azaz
>ne'gyfele' lehet menni, 8DB T, 12Db L-alak, azaz sima sarok ket irannyal.
>A feladat a kovetkezo:
>Kepezni kell ket pont kozott a letezo _osszes_ utat, ahogy oda lehet jutni.
>Kell a lepesek szama, illetve a lepesek listaja. A ket pont a 24 csomopont
>barmelyike lehet!
>Most ott tartok, hogy a szomszedos pontokat osszekoto valamennyi vektort
>osszeirtam. Irannyal egyutt 64db van eppen beloluk. (Tehat: pl. a 11-22,
>illetve 22-11 szomszedos csomopontokat osszekoto vektor kulon szerepel)
>Ez az egesz egy szetagazo fat ad, melynek egyes agai elerik a celt, masok
>pedig nem. Nekem csak a celt ero agakra lenne szukseg, illetve a celig
>vezeto lepesek szamaira, vagyis, hogy hany elemi vektoron mentem keresztul.
>Van valakinek valami otlete, hogy hogyan lehet egyszeruen, gyorsan irni
>ilyen algoritmust?
>A futasi ido mellekes, egyetlen egyszer kell az osszes pont osszes
>kombinaciojara felirni, az adatokat letarolni, es kesz! (276 fele
>csomopontpar kepezheto osszesen, ezek mindegyikerol egy-egy teljes listat
>kesziteni a lepesek szamarol az erintett vektorok felsorolasaval.)
>
>Tehat osszefoglalva a lenyeget: Most 64-vektorom van egy ketdimenzios
>tombben, pl: V(k,v)
>Ahol V a tomb neve, k a kezdopont, v pedig a szomszedos pont, ahova
>egyetlen, elemi lepessel lephetek. A feladat: a tomb cimeibol allo
>szamsorokat generalni, a kiindulo, es a vegpont kozott, meghozza az osszes
>bejarhato utvonalra.
>
>Me'g valami: egy vektoron (folyososzakaszon), illetve csomoponton
>termeszetesen nem mehetek at ketszer, hiszen akkor felesleges keruloutat
>valasztanek, s ezzel a megoldasok szama vegtelen lenne.
>
>Nem konkret program kell, egyszeruen 'csak' jo otletek! Valami gra'f
>elmeletre, vagy hasonlora gondoltam elso megkozelitesben...
>Lehet, hogy van egyszerubb megoldas is?


Ha labirintusrol van szo, akkor egy matrixban tarolom a csomopont fajtajat.
Lehet kereszt, balra fordul, jobbra fordul es tovabb egyenesen.
Keszitek egy rekurziv algoritmust, amely minden pontra megadja a lehetseges
tovabblepesek koordinatajat (a lepessel elert uj csomopontot). A csomopontokat
feljegyzem es az osszes lista kozul kivalasztom azt (azokat) amelyek a
legrovidebbek
es elerik a celt.

A routert irsz, akkor az RT-ben volt kozolve egy NYAK-tervezo. Abban le volt
irva
egy algoritmus. Valahogy ugy mukodott, hogy a kiindulasi pontbol az osszes
szomszedos, meg ures pontba letette az 1 erteket. Ezutan minden 1-essel
szomszedos,
meg ures pontba letette a 2 erteket. Igy tovabb, amig a celt el nem erte. Az
utvonal
visszafele megkeresheto. Ha nem talalod az illeto RT-t, akkor megkereshetem.

Remelem segitettem...

Veres Sandor