[prolog] route tonen

[Marc]

ik ben begonnen om te programmeren in prolog, en ik lees nu het boek "learn prolog now!".
daar komen op het eind van elk hoofdstuk praktische opdrachten, maar ik ben bij hoofdstuk 3 al vastgelopen.
dit is het probleem:

de volgende knowledge base is gegeven:

Prolog:

byCar(auckland,hamilton).
byCar(hamilton,raglan).
.......
byTrain(metz,frankfurt).
.......
byPlane(frankfurt,bangkok).
....

de eerste opdracht was een predikaat te schrijven dat je vertelt of je van de ene plek naar de ander kunt komen. dat was niet moeilijk:

Prolog:

travel(X,Y):-byCar(X,Y).
travel(X,Y):-byTrain(X,Y).
travel(X,Y):-byPlane(X,Y).

travel(X,Y):-byCar(X,Z),travel(Z,Y).
travel(X,Y):-byTrain(X,Z),travel(Z,Y).
travel(X,Y):-byPlane(X,Z),travel(Z,Y).

maar bij de volgende vraag loop ik vast:
schrijf een predikaat travel/3 dat vertelt welke route er genomen moet worden om van de ene plek naar de ander te komen. het programma moet als volgt reageren:

Prolog:

X = go(valmont,metz,
              go(metz,paris,
              go(paris,losAngeles)))

op de query travel(valmont, losAngeles, X).

ik kom hier niet uit. het lukt me niet om het rare predikaat go/2 en go/3 te verwerken in travel/3.

iemand enig idee? iemand uberhaupt die prolog programmeert?

[Soultaker]

Deze vraag is dermate simpel dat ik je niet echt een hint kan geven zonder de oplossing te geven, dus ik geef je het antwoord in de hoop dat je er zelf goed naar kijkt tot je begrijpt hoe het in elkaar steekt.

Aangezien de vervoerswijze er eigenlijk niet toe doet, is het handig om eerst een predicaat te introduceren dat bepaalt of je van de ene stad naar de andere kunt. (Dit is niet noodzakelijk, maar voorkomt redundantie, wat een goed streven is bij programmeren in welke taal dan ook.)

Prolog:

hop(A,B) :- byCar(A,B); byTrain(A,B); byPlane(A,B).

Nu kan het travel/2 predicaat eenvoudiger geschreven worden:

code:

travel(A,B) :- hop(A,B).
travel(A,C) :- hop(A,B), travel(B,C).

Dit komt precies overeen met wat je zelf al bedacht had. Het is nu ook eenvoudig om het travel/3 predicaat te definiëren, want de logica voor het vinden van de route blijft precies hetzelfde. Het enige wat je toe hoeft te voegen, is het gevonden pad in de laatste variabele te coderen:

code:

travel(A,B,go(A,B))   :- hop(A,B).
travel(A,C,go(A,B,R)) :- hop(A,B), travel(B,C,R).

[Marc]

haha te gek. bedankt voor je antwoord.
als ik het antwoord zie kan ik alleen maar lachen. het is zo simpel.
maar ik ben er zelf niet opgekomen. je moet echt anders denken bij deze taal, raar is dat.

vooral hoe je data teruggeeft is verwarrend. ik wil de hele tijd een variabele een waarde toekennen, zoiets als travel(A,B,C) :- C= .... maar zo werkt het echt totaal niet.
het is volgens mij wel een nadeel om al wat programmeer ervaring te hebben wanneer je met deze taal begint...

[ Voor 41% gewijzigd door Marc op 21-02-2010 00:50 ]

[Soultaker]

Hehe, klopt ja, Prolog kan behoorlijk verwarrend zijn, zeker als je verwacht dat het gewoon weer een andere programmeertaal is. Prolog is als taal niet ingewikkeld, maar het paradigma is toch behoorlijk uniek, en daardoor moet je op een hele andere manier leren nadenken over problemen.

vooral hoe je data teruggeeft is verwarrend. ik wil de hele tijd een variabele een waarde toekennen, zoiets als travel(A,B,C) :- C= .... maar zo werkt het echt totaal niet.

Op zich kán dat ook wel:

code:

travel(A,B,X) :- hop(A,B), X=go(A,B).
travel(A,C,X) :- hop(A,B), travel(B,C,R), X=go(A,B,R).

Je kunt zo een beetje doen alsof het variabelen in de gebruikelijke zin zijn, maar het is beter om te proberen op een Prolog-manier te denken dan patronen die je kent uit een andere programmeertaal na te bootsen. Met Prolog kun je juist ook constructies gebruiken die de meeste andere talen niet kennen, en daar zit juist de kracht van de taal in.

Overigens wordt het boek dat je aan het lezen bent tegen het einde nog vrij ingewikkeld, ik kan je aanraden de eerste paar hoofdstukken goed door te nemen zodat je de basis goed snapt. Succes!

[mysticyx]

[removed]

[ Voor 184% gewijzigd door mysticyx op 27-02-2012 21:23 ]

[user109731]

mysticyx schreef op dinsdag 23 februari 2010 @ 01:31:

code:

byAny(X,Y) :- byCar(X,Y); byTrain(X,Y); byPlane(X,Y).

travel(X,Y) :- byAny(X,Y);byAny(Y,X).
travel(X,Y) :- byAny(X,Z), travel(Z,Y).
travel(Y,X) :- byAny(X,Z), travel(Z,Y).

Kan dit niet veel eenvoudiger, zoiets:

code:

byAny(X,Y) :- byCar(X,Y); byTrain(X,Y); byPlane(X,Y).
byAny(X,Y) :- byAny(Y,X).

travel(X,Y) :- byAny(X,Y).
travel(X,Y) :- byAny(X,Z), travel(Z,Y).

Nu zit de 'regel' "je mag ook de andere kant op" alleen in het tweede predikaat

[mysticyx]

[removed]

[ Voor 100% gewijzigd door mysticyx op 27-02-2012 21:23 ]

[Soultaker]

Ik vermoed dat in de opdracht de verbindingen niet bidirectioneel bedoeld waren (hoewel dat inderdaad niet helemaal duidelijk is). In dat geval werkt de aanpassing van JanDM in ieder geval niet, omdat je zelfs bij het simpele voorbeeld van travel(valmont,raglan) al in een oneindige lus terecht komt:

code:

?- trace.

?- travel(valmont,raglan).
      1    1  Call: travel(valmont,raglan) ? 
      2    2  Call: byAny(valmont,raglan) ? 
      3    3  Call: byCar(valmont,raglan) ? 
      3    3  Fail: byCar(valmont,raglan) ? 
      3    3  Call: byTrain(valmont,raglan) ? 
      3    3  Fail: byTrain(valmont,raglan) ? 
      3    3  Call: byPlane(valmont,raglan) ? 
      3    3  Fail: byPlane(valmont,raglan) ? 
      3    3  Call: byAny(raglan,valmont) ? 
      4    4  Call: byCar(raglan,valmont) ? 
      4    4  Fail: byCar(raglan,valmont) ? 
      4    4  Call: byTrain(raglan,valmont) ? 
      4    4  Fail: byTrain(raglan,valmont) ? 
      4    4  Call: byPlane(raglan,valmont) ? 
      4    4  Fail: byPlane(raglan,valmont) ? 
      4    4  Call: byAny(valmont,raglan) ?

De laatste regel is gelijk aan de tweede en zo zit je dus in een eindeloze lus, terwijl het antwoord wel gevonden kan worden.

In mysticyx's implementatie gebeurt het omwisselen van locaties een niveau hoger, waardoor hij het probleem lijkt te omzeilen, maar eigenlijk is dat raar. Ik denk dat je altijd oneindige recursie kan verwachten zodra de graaf cykels bevat (en dat is het geval wanneer je alle edges bidirectioneel maakt). Overigens blijkt hieruit ook dat recursie met backtracking (wat de Prolog interpreter doet) zonder verdere aanpassingen niet zo geschikt is om arbitraire grafen te doorlopen. Het voorbeeld is dus een beetje ongelukkig gekozen, wat mij betreft.

edit:
De reden dat mysticyx methode niet in een oneindige lus komt, komt omdat zijn implementatie überhaupt niet klopt. Als ik 'm iets herschrijf (door alleen variabelen te herlabelen) is dat duidelijker:

Prolog:

travel(X,Y) :- byAny(X,Y);byAny(Y,X).
travel(X,Y) :- byAny(X,Z), travel(Z,Y).
travel(X,Y) :- travel(Z,X), byAny(Y,Z).

De eerste regel is wel bidirectioneel. De volgende twee regels staan een forward edge aan het begin van de route toe, of een backward edge aan het einde (waarbij de eindpunten van de route ook worden omgedraaid), maar geen backward edge aan het begin of een forward edge aan het einde. Vandaar dat travel(singapore,bangkok) faalt, terwijl er wel degelijk een route via Frankfurt is.

[ Voor 19% gewijzigd door Soultaker op 23-02-2010 15:25 ]

[user109731]

Soultaker schreef op dinsdag 23 februari 2010 @ 15:11:
Ik vermoed dat in de opdracht de verbindingen niet bidirectioneel bedoeld waren (hoewel dat inderdaad niet helemaal duidelijk is). In dat geval werkt de aanpassing van JanDM in ieder geval niet, omdat je zelfs bij het simpele voorbeeld van travel(valmont,raglan) al in een oneindige lus terecht komt:

Goed punt, ik dacht dat de Prolog-interpreter dat wel zou herkennen Wat zou dan volgens jou de mooiste oplossing zijn?

[ Voor 7% gewijzigd door user109731 op 23-02-2010 15:46 ]

[Soultaker]

Tja, een mooie oplossing is lastig, want Prolog's backtracking interpreter is niet heel geschikt voor andere zoekvolgordes. Een manier is om dynamische clauses te gebruiken en negation by failure (wat de TS nog niet gehad heeft):

Prolog:

:- dynamic(visited/1).

byAny(X,Y) :- byCar(X,Y); byTrain(X,Y); byPlane(X,Y).

edge(X,Y) :- byAny(X, Y); byAny(Y, X).

travel(X,Y) :- edge(X,Y).
travel(X,Y) :- edge(X,Z), \+ visited(Z), asserta(visited(Z)),
               (travel(Z,Y); retract(visited(Z))).

Dit werkt, maar alleen als je alle oplossingen afloopt, want als je eerder afbreekt dan wordt visited(Z) niet meer teruggenomen. Dat kun je verhelpen door af te breken na het vinden van de eerste oplossing (met cuts, wat de TS ook nog niet gehad heeft):

Prolog:

travel(X,Y) :- edge(X,Y), !.
travel(X,Y) :- edge(X,Z), \+ visited(Z), assert(visited(Z)),
               (travel(Z,Y), retract(visited(Z)), !; retract(visited(Z))).

Dit is vermoedelijk wat je wil, omdat zonder verdere informatie over de route het toch niet zo zinnig is om travel/2 meerdere keren te laten slagen.

Persoonlijk ben ik niet zo'n fan van dynamische databases (ik ben dan ook meer pure functional programming gewend). Het alternatief is dan zelf bij te houden welke plaatsen je al bezocht hebt, bijvoorbeeld in een lijst:

Prolog:

travel(X,Y) :- travel(X,Y,[X]).
travel(X,Y,_)  :- edge(X, Y).
travel(X,Y,V1) :- edge(X,Z), add(V1,Z,V2), travel(Z,Y,V2).

add([],X,[X]).
add([H|T1],X,[H|T2]) :- \+ X=H, add(T1,X,T2).

Een stuk netter, naar mijn idee. Je kunt hier ook weer cuts toevoegen (net als hierboven) maar het voordeel van ze weglaten is dat je dan dingen als travel(X,Y) nog kunt doen (waarbij je alle paren van steden krijgt die direct of indirect verbonden krijgt, waarbij je een nieuwe oplossing krijgt voor elk mogelijk pad).

Nadeel van zo'n aanpak ten opzichte van de dynamische database is dat de Prolog interpreter zijn database waarschijnlijk efficiënter heeft geïmplementeerd dan een lijst (of dan je überhaupt kan doen in Prolog zelf).

edit:
Trouwens, in het laatste voorbeeld is duidelijk dat de lijst met bezochte toestanden ook gelijk een pad van A naar B geeft, dus kun je een parameter elimineren en de boel herschrijven naar:

code:

travel(From,To) :- travel2([From], To).

travel2(Path,To) :- Path=[Prev|_], edge(Prev,Next), \+ contains(Path,Next),
                    (Next=To; travel2([Next|Path],To)).

contains(List,Elem) :- append(_,[Elem|_],List).

(Hier is travel/2 alleen maar een hulppredicaat om de eerste stad in een lijst te zetten, en contains kan natuurlijk in travel2/2 gezet worden als je 'm nergens anders nodig hebt.)

[ Voor 25% gewijzigd door Soultaker op 23-02-2010 17:33 ]