Router algoritmust keresek - OFFT

[Kis Norbert]

Sziasztok!


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?

Udvozlettel:
		Norbi.