Egy klasszikus - és nagyon hasznos - programozási feladat számok listájának növekvő sorrendbe rendezése. Erre rengeteg módszer van, itt csak a legfontosabbak közül nézünk meg néhányat.
Az első algoritmus a beszúrásos rendezés. Az ötlet a következő: ha van egy listám, akkor azt szétszedem az első elemre és a maradékára, az utóbbit (rekurzívan) rendezem, és végül az első elemet beszúrom a “megfelelő” helyre.
rendez1([], []).
rendez1([X|M], Y) :- rendez1(M, M1), beszúr(X, M1, Y).A megfelelő helyre való beszúrásnál pedig egyszerűen addig megyünk, amíg egy legalább akkora elemet nem találunk:
beszúr(X, [], [X]).
beszúr(X, [Y|M], [X,Y|M]) :- X =< Y.
beszúr(X, [Y|M], [Y|M1]) :- X > Y, beszúr(X, M, M1).Próbáljuk ki!
?- rendez1([4,1,9,2,6,0,3,2,5,1], X).
X = [0, 1, 1, 2, 2, 3, 4, 5, 6, 9]Ennek az algoritmusnak egy nagy előnye, hogy akkor is jól használható, ha az adatokat folyamatosan kapjuk, hiszen ha már van egy rendezett listánk, akkor utána mindig elég a beszúr műveletet használni. Egy másik jó tulajdonsága, hogy egy már rendezett sorozatnál nem végez plusz munkát, épp csak ellenőrzi, hogy a lista tényleg jó sorrendben van:
?- trace, rendez1([1,2,3], X).
Call:rendez1([1, 2, 3], X)
Call:rendez1([2, 3], X1)
Call:rendez1([3], X2)
Call:rendez1([], X3)
Exit:rendez1([], [])
Call:beszúr(3, [], X2)
Exit:beszúr(3, [], [3])
Exit:rendez1([3], [3])
Call:beszúr(2, [3], X1)
Call:2=<3
Exit:2=<3
Exit:beszúr(2, [3], [2, 3])
Exit:rendez1([2, 3], [2, 3])
Call:beszúr(1, [2, 3], X)
Call:1=<2
Exit:1=<2
Exit:beszúr(1, [2, 3], [1, 2, 3])
Exit:rendez1([1, 2, 3], [1, 2, 3])
X = [1, 2, 3]Ugyanakkor ha nincs szerencsénk, nem túl jó hatásfokú: ha a lista n hosszú, akkor kb. n^2 összehasonlítást végez a legrosszabb esetben.
A gyorsrendezésnél kiválasztunk egy tetszőleges elemet (pl. az elsőt), és a többit két részre osztjuk aszerint, hogy nagyobb-e ennél vagy sem. Ezután a két részt külön-külön rendezzük (rekurzívan), majd az eredmény ezek összefűzéséből adódik:
rendez2([], []).
rendez2([X|M], Y) :-
szétoszt(X, M, Kicsi, Nagy),
rendez2(Kicsi, K),
rendez2(Nagy, N),
hozzáfűz(K, [X|N], Y).A szétosztás elég magától értetődő:
szétoszt(_, [], [], []).
szétoszt(X, [Y|M], K, [Y|N]) :- X =< Y, szétoszt(X, M, K, N).
szétoszt(X, [Y|M], [Y|K], N) :- X > Y, szétoszt(X, M, K, N).Ez (nagyon hosszú listákra) bizonyíthatóan sokkal kevesebb ellenőrzést végez, mint a beszúrásos rendezés. A fenti program azonban a hozzáfűzések miatt nem igazán hatékony - a következő leckében majd szó lesz a különbség-listákról, amelyek segítségével sokkal gyorsabbá tehető.
Utolsónak nézzünk meg egy nagyon hasonló algoritmust: itt is két részre bontjuk mindig a listát, azokat rendezzük, majd összefűzzük, de itt nem a szétválasztás a bonyolultabb, hanem az összefűzés, vagy ez esetben az összefésülés.
A listát a felénél kettéosztjuk, és mindkét részt rendezzük (rekurzívan), végül a két rendezett listát egy listává fésüljük össze:
rendez3([], []).
rendez3([X], [X]).
rendez3(X, Y) :-
kettéoszt(X, X1, X2),
rendez3(X1, Y1),
rendez3(X2, Y2),
összefésül(Y1, Y2, Y).
kettéoszt([], [], []).
kettéoszt([X], [X], []).
kettéoszt([X,Y|M], [X|M1], [Y|M2]) :- kettéoszt(M, M1, M2).Az összefésülésnél a két lista elemét összehasonlítjuk, és a megfelelőt berakjuk a maradékok összefűzéséből kapott listába:
összefésül([X|Mx], [Y|My], [X|M]) :- X =< Y, összefésül(Mx, [Y|My], M).
összefésül([X|Mx], [Y|My], [Y|M]) :- X > Y, összefésül([X|Mx], My, M).
összefésül(X, [], X).
összefésül([], Y, Y).Itt érdekes módon azt tapasztaljuk, hogy a (helyes) eredményt végtelen sokszor megkapjuk. Ez azért van, mert a rendez3 harmadik szabálya az egyelemű listákra is meghívódhat. Ezt ki lehetne védeni azzal, hogy megköveteljük, hogy legyen legalább két eleme:
rendez3(X, Y) :-
X = [_,_|_], Y = [_,_|_],
kettéoszt(X, X1, X2),
rendez3(X1, Y1),
rendez3(X2, Y2),
összefésül(Y1, Y2, Y).… de ez nem a legelegánsabb. (Hasonlóan, az összefésül utolsó két szabálya közt is van átfedés.) Nincs valami jobb mód erre?
Egy szabály törzsében vágást eszközölhetünk a ! segítségével. Ez azt mondja, hogy ha már idáig eljutottunk, akkor vagy sikerül teljesíteni a törzs maradék részét, vagy ha nem, akkor úgy vesszük, hogy ezzel a fejjel való egyesítés sikertelen volt, nem próbálunk a ! előtti kifejezésekre visszamenni, vagy az azonos fejhez tartozó esetleges többi szabályt megnézni.
Nézzük meg például az alábbi szabályokat, ahol A, B, C stb. kifejezéseket jelölnek:
C :- P, Q, R, !, S, T, U.
C :- V.
A :- B, C, D.Ekkor ha az
?- A.kérdést feltesszük, a következő fog történni:
B teljesül-e (tegyük fel, hogy igen).P, Q, R teljesülnek-e (tegyük fel, hogy igen).S, T, U teljesülnek-e. Tegyük fel, hogy az S és T teljesül, de az U nem. Ekkor szokás szerint visszamegy a T-re, és megkeresi annak egy másik megoldását stb.S, T, U-t teljesíteni, akkor - a vágás miatt - már nem megy vissza, hogy az R egy másik megoldását keresse, és nem próbálkozik a C-hez tartozó második szabállyal sem, hanem egy szinttel feljebb megy, és a B-hez keres egy másik megoldást.Nézzük meg, hogyan lehet ezzel feljavítani az összefésülést!
összefésül([X|Mx], [Y|My], [X|M]) :- X =< Y, !, összefésül(Mx, [Y|My], M).
összefésül([X|Mx], [Y|My], [Y|M]) :- X > Y, !, összefésül([X|Mx], My, M).
összefésül(X, [], X) :- !.
összefésül([], Y, Y) :- !.A vágások a programot hatékonyabbá teszik: ha az első szabályban láttuk, hogy X =< Y, már nem kell ellenőrizni a többi szabályt stb. (Az utolsó sorban a vágás felesleges, csak a szimmetria kedvéért került bele.)
Hasonlóan, a rendez3 második szabályában:
rendez3([X], [X]) :- !.Ezekkel a módosításokkal már egyértelmű (determinisztikus) lesz a megoldás.
A vágások nem változtatják meg a program értelmét (tehát, hogy milyen kifejezésekre lesz igaz), csak a hatékonyságát.
Nézzünk egy másik példát! Az alábbi szabály két szám közül kiválasztja a nagyobbikat:
max1(X, Y, X) :- X >= Y.
max1(X, Y, Y) :- X < Y.A fenti módon ez átírható így:
max2(X, Y, X) :- X >= Y, !.
max2(X, Y, Y) :- X < Y.Felmerül akkor, hogy a második szabályban szükség van-e egyáltalán az X < Y összehasonlításra, hiszen csak akkor juthatunk oda, ha az X >= Y nem teljesült. A program akkor is működni látszik, ha elhagyjuk:
max3(X, Y, X) :- X >= Y, !.
max3(_, Y, Y).Teszteljük egy kicsit!
?- max3(3, 5, X).
X = 5
?- max3(4, 2, X).
X = 4
?- max3(1, 5, 5).
true
?- max3(5, 1, 1). % Ajjaj...
trueHoppá! Mi történt?
Mivel az utolsó példában mindhárom argumentumnak van értéke, és az első és harmadik nem azonos, az első szabállyal nem is próbálkozik, hanem rögtön a másodikra megy, ami pedig most, hogy kivettük a feltételt, teljesül.
A max3 változatban megváltozott a program deklaratív jelentése, hiszen egy olyan tényt tartalmaz, ami magában nézve nem igaz. Ez általában kerülendő, bár a hatékonysághoz néha szükséges. Ha ilyen gondolatmenetet alkalmazunk, nagyon óvatosnak kell lenni - itt pl. biztosnak kell lennünk benne, hogy a harmadik argumentum mindig változó.
Egy további példaként nézzük meg az alábbi szabályt:
% hozzáad(+X, +Halmaz, -Eredmény).
% Hozzáadja `X`-et a `Halmaz` listához,
% de csak akkor, ha az még nem tartalmazta.
hozzáad(X, L, L) :- tartalmaz(X, L), !.
hozzáad(X, L, [X|L]).A vágás nélkül itt a második szabályt nehezebb lenne megfogalmazni, kéne hozzá a 3. leckéhez tartozó projektben látott nemtartalmaz szabály, és következésképp a hatékonyságból is vesztene.
Cserébe itt is problémába ütközünk, ha a harmadik argumentum nem változó:
?- hozzáad(b, [a,b], [b,a,b]).
trueEzt elkerülendő, érdemes a dokumentációval egyértelművé tenni a használatot. A fenti programhoz tartozó megjegyzés is ilyen szellemben íródott. Az első sorában egy egyezményes jelölésrendszert használ, melyben minden argumentum háromféle lehet:
+X : kell, hogy legyen értéke?X : lehet értéke, de nem muszáj-X : csak változó lehetA help is ezeket használja. Például:
?- help(>).
+Expr1 > +Expr2
...
?- help(flatten). % lapít (3. lecke 10. feladat)
flatten(+NestedList, -FlatList)
...
?- help(member). % tartalmaz
member(?Elem, ?List)
...Az első esetben mindkét kifejezésnek ismertnek kell lennie; a másodikban a lapítandó lista ismert, és a lapított verzió csak változó lehet; a harmadikban pedig mind a lista, mind a benne tartalmazandó elem lehet változó vagy ismert is.
Nézzük meg az alábbi szabályokat!
p(1).
p(2) :- !.
p(3).Mit lesz az összes válasz az alábbi kérdésekre:
?- p(X).
?- p(X), p(Y).
?- p(X), !, p(Y).Írjátok át hatékonyabbra a szétoszt szabályt vágások segítségével!
Hogyan tudjuk megfogalmazni azt, hogy “Csilla szeret minden állatot, kivéve a pókokat”?
szereti(csilla, X) :- pók(X), !, fail.
szereti(csilla, X) :- állat(X).(Általában ilyenkor a false helyett a fail-t szokás használni, de a kettő jelentése azonos.)
Próbáljuk ki!
állat(tarantula).
állat(denevér).
pók(tarantula).
?- szereti(csilla, tarantula).
false
?- szereti(csilla, denevér).
trueEz annyira hasznos, hogy érdemes bevezetni, mint tagadást:
nem(P) :- P, !, fail.
nem(_).Figyeljük meg, hogy itt valami olyat csináltunk, amit eddig még soha: egy változót (P) a törzsben magában használtunk. Ez feltételezi, hogy a P-nek kiszámolható az igazságértéke. Például a fenti példát átírva:
szereti(csilla, X) :- állat(X), nem(pók(X)).Itt a P értéke a pók(X) struktúra, és a nem törzsében levő P kiértékelésekor ezt mint megoldandó célkifejezést értelmezi.
A tagadásnak ez a módja nem mindig intuitív. Egy így tagadott kifejezés akkor lesz igaz, ha a kifejezés nem bizonyítható.
Mi történik, ha az előző programban felcseréljük a törzs két tagját?
szereti(csilla, X) :- nem(pók(X)), állat(X).Érdekes módon Csilla most már a denevéreket sem szereti! Miért? Azért, mert a nem(pók(X))-ben az X egy változó, tehát a pók(X) bizonyítható az X = tarantula helyettesítéssel, így a nem(pók(X)) nem teljesül. Az érték nélküli argumentumokkal tehát vigyázni kell.
Hasonlóan furcsa lehet, hogy
?- nem(állat(kutya)).
true… de persze helyes, hiszen a programban levő szabályok alapján nem bizonyítható, hogy a kutya állat.
Ezek miatt a nem (vagy az angol not) helyett a \+ operátort szokás használni, melynek definíciója ugyanaz, csak az elnevezés kevésbé félrevezető:
szereti(csilla, X) :- állat(X), \+ pók(X).Milyen kérdéssel lehet a Jelöltek listából kiválasztani azokat, akik nem szerepelnek a Kiesettek listában? Használjátok a tartalmaz szabályt és a tagadást!
Készítsetek szabályt, ami két halmaz különbségét képzi! (A halmaz itt egy olyan lista, amiben minden elem egyszer fordul elő.)
?- különbség([a,b,c,d], [f,d,b,e], X).
X = [a, c]Készítsetek szabályt, ami kiválogatja egy listából azokat a kifejezéseket, amelyek egy adott másik kifejezéssel egyesíthetőek!
?- egyesíthető([X,b,t(Y)], t(a), L).
L = [X, t(Y)]Figyeljetek arra, hogy az X és Y ne kapjon ezáltal értéket!
Ez a dokumentum az alábbi könyv 5. és 9.1. fejezete alapján készült:
I. Bratko: Prolog Programming for Artificial Intelligence, 4th Ed., Pearson, 2011.
Az összefésüléses példa az alábbi könyv 11. fejezetéből származik:
L. Sterling, E. Shapiro: The Art of Prolog, 2nd Ed., MIT Press, 1994.
Rendezési algoritmusokból nincs hiány. Bizonyítható, hogy a gyorsrendezés, a fésülő rendezés (és még sok másik) a lehető leghatékonyabb … kivéve egy-két furcsa módszert: