Router algoritmust keresek - OFFTO

[Kis Norbert]

Szia!

Koszi a segitseget mindenkinek. Volt, aki komplett algoritmust is kuldott
maganban. Vegul
a hetvegen -ket nap agyalas utan- talaltam egy viszonylag gyors, de
ugyanakkor egyszeru megoldast. Egy viszonylag kicsi router tablaban kell
lepkedni csak jobbra-balra, illeve scrollozni a tabla oszlopait eggyel
felfele.

Mellekelem is a parsoros algoritmust, de csatolva, hogy a tablazatok
olvashatok maradjanak.
Lehetna meg szepiteni rajta, de ez eleg konnyen leprogramozhato, s eleg
hatekony kodot is ad.
Eloszor FILE-ba akartam letarolni egyszer a variaciokat, de annyira gyors
lesz, hogy realtime is megfelelo, ha ASM-ben csinalom meg. (Remelem,
RB-ektol nem kapok irgumburgumot a csatolas miatt, mert igen rovid, es
tenyleg maskepp olvashatatlan lenne.)

Az altalatok leirt tippek baja az, hogy vagy az osszes kombinaciot kepezik,
es utolag
dontenek, hogy jo-e celnak. Vagy a masik, hogy nem mindig jarjak be az
osszes, lehetseges utat.
Az elso baja, hogy hatalmas memoria kell, ami ebben az esetben nincs, a
masodik pedig csak reszmegoldast ad. Viszont mindkettoben kozos, hogy
rengeteg adatot kell megmozgatni...

>Ha labirintusrol van szo, akkor egy matrixban tarolom a csomopont fajtajat.
>Lehet kereszt, balra fordul, jobbra fordul es tovabb egyenesen.

Plusz ehhez jon a T-elagazas nalam. :-)

>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.

Az enyem is hasonloan mukodik, de nem tarolom a teljes listat, mert az marha
nagy lenne. Helyette azt csinalom, hogy egy ROUTER-tablazatban lepkedek
jobbra, es az elozo poziciobol kiindulo szomszedvektorokat egymas alatti
helyekre szepen bejegyzem. 
Ezutan leptetek 1-el jobbra. (LEPES++)
Mivel nalam 4-irany van, ezert a negy soros tabla eleg. Az otodik csak
gyorsitasra kell, hogy igy -minden lepesnel vizsgalt adat helyett- gyorsabb
legyen a rutin. Ezutan celvizsgalat kovetkezik. Ha celt ertem, akkor a
legfelso sorat kiirom a router tablanak, (igy tarolni se kell tovabb a
RAM-ban) s a tovabbiakban ugy jarok el, mintha foglaltba utkoztem volna.
(maximalis hossz a szomszedvektorszam, azaz 64) Persze lehet, hogy 24 is
eleg lenne, hiszen foglalt elemen ugysem mehetek at... A feltoltetlen
elemeket termeszetesen 0-k reprezentaljak, amikkel indulas elott a ROUTER
tombot feltoltom.
S most jon a trukk: Ha olyan elem jott a kepbe, ami foglalt, akkor elugrok a
visszalepteto agra. Ha nem, akkor novelem a lepes-t 1-el, azaz jobbra lepek
a ROUTER tablazatban a kovetkezo oszlopra.

A visszalepteto rutin megintcsak parsoros. (5-sor!) A kovetkezokeppen
mukodik:
Eloszor is scrollozza felfele az adott ROUTER(lepes) oszlop sorat, igy az
utkozest okozo elem kiesik, s a negyedik elembe ures, azaz nulla ertek
shiftelodik be. Ha a kapott ertek nem nulla, akkor visszalepek a rendes
elore lepteto reszre, hiszen ez egy masik elagazas, lehet belole kiindulva
elore lepkedni! Elotte termeszetesen az otodik sor foglaltsagi elemet
modositjuk...

Ha a kapott ertek nulla, akkor ebben az oszlopban mar nincs tobb elagazasi
elem, tehat vissza kell leptetni a mutatot 1-el, es a fenti scroll-ra
ugrani. (Azaz: az elozo elagazasnal masik iranyba fordulunk.)

Mielott a scrollra ugranank, azonban megvizsgaljuk, hogy elertuk-e az elso
oszlopot! Ha igen, akkor ez utunk veget jelenti, hiszen valamennyi
lehetseges utvonalat bejartuk, igy a ROUTER alprogram futasa veget ert.

Hmm... Hat ennyi, meg ket atalvatlan ejszaka.... Igy elmondani nem is
bonyolult. :-))))

>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

Emlekeszem en is a cikkre, de ott eleg bonyolult volt a program, es igen
nagy tombmeretekkel dolgozott. Most nem paneltervezeshez kell a router,
hanem egy par (24) csomopontbol allo, osszesen 64-szomszedvektort tartalmazo
listahoz. Viszont sajnos _valamennyi_ variacio kell, me'g a legkevesbe
optimalisak is, amik hurkot nem tartalmaznak.

>visszafele megkeresheto. Ha nem talalod az illeto RT-t, akkor
megkereshetem.

Koszi, megvan. Azert kivancsisagbol megnezem, mekkora az O programjuk. (Az
enyem BASIC-ben megirva 15...20 sor, es mukodik! :-) )

>Remelem segitettem...
>Veres Sandor

Igen, koszi Neked, meg Toreki Attilanak is a segitseget. Ha nagyobb
autoroutert kell irnom, akkor valoszinuleg ujra eloveszem a most tanultakat,
koszi megegyszer.


Udvozlettel:
			Norbi.

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ROUTER.TXT
Url: http://www.centralnet.hu/pipermail/elektro/attachments/20000306/ee2a115b/attachment.ksh