23

Sisendite-väljundite ühendamine (routing)

Trükiplaatide projekteerimisel on tarvis lahendada järgmine probleem (routing problem): n x n tasapinnalisel võrestikul on antud m sisendit ja väljundit, mis on tarvis paarikaupa ühendada nii, et kõik ühendusteed kulgevad mööda võrestiku servi ja samal lõigul ei kulge kusagil kaks ühendusteed; ühendusteed võivad ristuda, kuid sageli nõutakse ka ristumiste arvu minimaliseerimist.


Järgnevas vaatleme programmi, mis lahendab selle ülesande lihtsustatud variandi: kõik sisendid ja kõik väljundid asuvad samas veerus (seega piisab nende esitamiseks vastava rea numbri andmisest; ühendada tuleb esimene sisend esimese väljundiga, teine sisend teise väljundiga jne. Peale sisendite ja väljundite reanumbreid (need sisestatakse ühekaupa, kui kõik numbrid on sisestatud, sisestatakse sõna 'koik') on programmi sisendiks veel skeemi laius, st. veergude arv. skeemi ridade arvuks arvutatakse maksimum sisendite ja väljundite reanumbritest.

alga :-

kirjuta('Kus on algused? (sisesta ühekaupa, lopetuseks: koik) '),
rv,
sisesta(Xa),
kirjuta('Kus on lopud?'),
rv,
sisesta(Xb),
kirjuta('Mitu veergu on? '),
loe(V),
eemalda_koik(veerge(_)),
pea_meeles(veerge(V)),
salvesta_read(Xa,Xb),
teed(Xa,Xb,[]).
sisesta(Kokku) :-
hakka_lugema(Kokku,[]).
hakka_lugema(Kokku,Loetud) :-
loe(Y),
(Y = koik , ! , Kokku = Loetud , rv ; hakka_lugema(Kokku,[Y|Loetud])).
salvesta_read(Xa,Xb) :-
suurim(Xa,MXa),
suurim(Xb,MXb),
max(MXa,MXb,MX),
eemalda_koik(ridu(_)),
pea_meeles(ridu(MX)).

Predikaat suurim arvutab nimistu maksimaalse elemendi.

suurim([X],X) :-

!.
suurim([X|Y],Z) :-
suurim(Y,MY),
max(X,MY,Z).

Teed arvutab predikaat teed, mille esimeseks argumendiks on veel ühendamata sisendite nimistu, teiseks argumendiks - veel ühendamata väljundite nimistu ja kolmandaks - nimistu juba leitud teedest (iga tee on nimistu sellel esinevatest võrgu tippudest). Kui predikaat teed käivitatakse, on tema esimeseks ja teiseks argumendik kõigi sisendite ja väljundite nimistud ja kolmas argument on tühi nimistu (ühtegi teed ei ole veel leitud). Kui kõik sisendid-väljundid on ühendatud, on esimene ja teine argument tühjad nimistud ja tuleb leitud teed ekraanile joonistada. Kui ei kasutata Eesti-Prologi graafikavormi (prolog ei ole käivitatud käsuga eestigr ja viidud graafikareziimi) , tuleb predikaat joonista_teed ära jätta.

teed([],[],Teed) :-

!,
väljasta_teed(Teed),
joonista_read,
joonista_teed(Teed).
teed([Xa|Xad],[Xb|Xbd],Senised) :-
veerge(N),
tee([Xa,1],[Xb,N],[],Tee,Senised),
teed(Xad,Xbd,[Tee|Senised]).

Uue tee leiab (st. ühendab ühe sisendi ja sellele vastava väljundi) predikaat tee (see on väga sarnane kahe linna vahelise tee leidmise predikaadiga). Selle esimene argument on punkt, kus ollakse praegu, teine - kuhu on tarvis jõuda, kolmas - nimistu võrgu tippudest, mis on juba läbitud, neljas argument on vajalik vaid lõpliku tee väljastamiseks ja viies argument on teiste seni juba leitud teede nimistu (seda vajatakse kontrollimiseks, et sama serva ei kasutata kaht korda). Punktide (X,Y) ja (X1,Y1) vahelist uut teed otsides püütakse algul liikuda vertikaalsuunas õigele (s.t. sihtpunkti) kõrgusele ja siis jätkata horisontaalsuunas Näiteks ülaloleval joonisel sisend "[5,1]" ja väljund "[2,5]" on ühendatud just nii (teede leidmine algab viimasena sisestatud punktist). Kui kohe õigele horisontaalreale jõudmine ei õnnestu, liigutakse üks samm paremale ja proovitakse uuesti Kõrvaloleval näitel on punktide "[4,1]" ja "[1,5]" ühendamisel Prolog olnud sunnitud tagurdama ja muutma algul leitud ühendusteed [[4,1],[4,2],[3,2],[2,2],[1,2],[1,3],[1,4],[1,5]], kui punkte [1,1],[4,5] ühendada püudes selgus, et see tee suleb edasipääsud punktist [1,1].

tee([X,Y],[X,Y],Tee,Tee,_).
tee([X,Y],[X1,Y1],Käidud,Tee,Senised) :-

X < X1,
Y =< Y1,
Xuus oleks X + 1,
ei kasutatud([X,Y,Xuus,Y],Käidud,Senised),
tee([Xuus,Y],[X1,Y1],[[X,Y,Xuus,Y]|Käidud],Tee,Senised).
tee([X,Y],[X1,Y1],Käidud,Tee,Senised) :-
X > X1,
Y =< Y1,
Xuus oleks X - 1,
ei kasutatud([X,Y,Xuus,Y],Käidud,Senised),
tee([Xuus,Y],[X1,Y1],[[X,Y,Xuus,Y]|Käidud],Tee,Senised).
tee([X,Y],[X1,Y1],Käidud,Tee,Senised) :-
Y =< Y1,
Yuus oleks Y + 1,
ei kasutatud([X,Y,X,Yuus],Käidud,Senised),
tee([X,Yuus],[X1,Y1],[[X,Y,X,Yuus]|Käidud],Tee,Senised).
kusagil([X,Y,X1,Y1],[Tee|Teed]) :-
kasutatud([X,Y,X1,Y1],Tee).
kusagil([X,Y,X1,Y1],[_|Teed]) :-
kusagil([X,Y,X1,Y1],Teed).
kasutatud([X,Y,X1,Y1],Käidud,_) :-
kasutatud([X,Y,X1,Y1],Käidud).
kasutatud([X,Y,X1,Y1],_,Teed) :-
kusagil([X,Y,X1,Y1],Teed).
kasutatud([X,Y,X1,Y1],Käidud) :-
esineb([X,Y,X1,Y1],Käidud).
kasutatud([X,Y,X1,Y1],Käidud) :- esineb([X1,Y1,X,Y],Käidud).
tee([X,Y],[X,Y],Tee,Tee,_).
tee([X,Y],[X1,Y1],Käidud,Tee,Senised) :-
X < X1,
Y =< Y1,
Xuus oleks X + 1,
ei kasutatud([X,Y,Xuus,Y],Käidud,Senised),
tee([Xuus,Y],[X1,Y1],[[X,Y,Xuus,Y]|Käidud],Tee,Senised).
tee([X,Y],[X1,Y1],Käidud,Tee,Senised) :-
X > X1,
Y =< Y1,
Xuus oleks X - 1,
ei kasutatud([X,Y,Xuus,Y],Käidud,Senised),
tee([Xuus,Y],[X1,Y1],[[X,Y,Xuus,Y]|Käidud],Tee,Senised).
tee([X,Y],[X1,Y1],Käidud,Tee,Senised) :-
Y =< Y1,
Yuus oleks Y + 1,
ei kasutatud([X,Y,X,Yuus],Käidud,Senised),
tee([X,Yuus],[X1,Y1],[[X,Y,X,Yuus]|Käidud],Tee,Senised).

Jääb järele teede väljastamine ja lahendi joonistamine ekraanile. Kuna siin kasutatakse ka LPA-Prologi graafikaprimitiive, tuleb Prolog käivitada käsklusega eestigr (sse laeb ka vajalikud graafikamoodulid), peale Eesti-Prologi käivitumist minna üle graafikareziimi (vastava funktsionaalsõrmise abil) ja salvestada programm alamkataloogi joonista.

väljasta_teed([]) :-

rv,
kirjuta('Koik!').
väljasta_teed([Tee|Teed]) :-
väljasta(Tee),
väljasta_teed(Teed).
väljasta([[X,Y,X1,Y1]]) :-
!,
rv,
kirjuta(X),
kirjuta(','),
kirjuta(Y),
kirjuta(->),
kirjuta(X1),
kirjuta(','),
kirjuta(Y1).
väljasta([[X,Y,X1,Y1]|Lopp]) :-
väljasta(Lopp),
kirjuta(->),
kirjuta(X1),
kirjuta(','),
kirjuta(Y1).
joonista_teed([]) :-
ring(2),
!.
joonista_teed([Tee|Teed]) :-
joonista_tee(Tee),
joonista_teed(Teed).
joonista_tee([[X,Y,X1,Y1]]) :-
teisenda([X,Y,X1,Y1],[MX,MY,MX1,MY1]),
mine(MX,MY),
ring(2),
sirge(MX,MY,MX1,MY1),
ring(2).
joonista_tee([[X,Y,X1,Y1]|Muud]) :-
teisenda([X,Y,X1,Y1],[MX,MY,MX1,MY1]),
sirge(MX,MY,MX1,MY1),
ring(2),
joonista_tee(Muud).
joonista_rida(N,R) :-
N =< R,
!,
teisenda([N,0],[MN,M0]),
mine(MN,M0),
tekst(N),
N1 oleks N + 1,
joonista_rida(N1,R).
joonista_rida(_,_).
joonista_read :-
ridu(R),
joonista_rida(1,R).
teisenda([],[]) :-
!.
teisenda([X|Z],[MX|MZ]) :-
MX oleks 30 * X - 100,
teisenda(Z,MZ).


Lae uus Eesti-Prologi põhimoodul
Lae uus Eesti-Prologi graafikamoodul

Küsimused, probleemid:
jaak@cc.ttu.ee

Tagasi loengute sisukorra juurde