✔ [Prolog] Rueckgabe eines Wertes

[Scotty86]

knoten(a).
knoten(b).
knoten(c).
knoten(d).
knoten(e).
knoten(f).
knoten(g).
knoten(h).
knoten(i).
knoten(j).
knoten(k).
knoten(l).
knoten(m).
knoten(n).

kante(a, b).
kante(a, c).
kante(a, d).
kante(b, f).
kante(c, e).
kante(d, f).
kante(e, f).
kante(f, g).
kante(g, h).
kante(h, i).
kante(h, j).
kante(i, j).
kante(j, k).
kante(j, l).
kante(j, m).

kosten(a, b, 2).
kosten(a, c, 5).
kosten(a, d, 7).
kosten(b, f, 9).
kosten(c, e, 1).
kosten(d, f, 5).
kosten(e, f, 2).
kosten(f, g, 7).
kosten(g, h, 18).
kosten(h, i, 7).
kosten(h, j, 6).
kosten(i, j, 1).
kosten(j, k, 1).
kosten(j, l, 2).
kosten(j, m, 5).


zweierkanten(X, Y) :- kante(X, Z), kante(Z, Y).


kostenpunkt(X, Y) :-  kosten(X, Y, Z),       
      write(Z).

zweierkantenkosten(X, Y) :- kosten(X, B, Z), kosten(B, Y, M), K is Z+M, write(K).

verbindung(X, X).
verbindung(X, Y) :- kante(X, A),
     verbindung(A, Y),
     write(A).

%HIER LIEGT DAS PREOBLEM
vk(X, Y) :- findall(Summe, verbindungskosten(X, Y, 0, [Y], Summe),L), write(L).
%HIER LIEGT DAS PREOBLEM

verbindungskosten(X, X, S, Pfad, Summe) :- write('Kosten: '), write(Summe), write('\nPfad: '), write(Pfad), write('\n').
verbindungskosten(X, Y, S, Pfad, Summe) :-  kosten(A, Y, Z), 
       N is S + Z,
       append([A],Pfad,NeuerPfad),
       verbindungskosten(X, A, N, NeuerPfad, N).

Ja Prolog, eine tolle Sprache, leider an der Uni relevant ...

Und zwar muss ich alle Lösungen irgendwie in L uebergeben, leider krieg ichs nicht hin :\

 

[deepthroat]

Hi.

Könntest du evtl. etwas genauer das Problem beschreiben? Vielleicht mit einem Beispiel?

Was funktioniert denn nicht?

Gruß

 

[Scotty86]

Oky, sorry.

Das 'Programm' durchlaeuft einen Graphen von Punkt X nach Y, wobei jede kannte einen Preis hat.
Also z.B.
A =5=> B =7=> C
Damit hab ich die Kosten 12 (5+7), wenn ich von A nach C will. So weit funktioniert auch alles prima.
Nun kann es aber auch mehrere Moeglichkeiten geben um von einem Punkt zu einem andern zu kommen.
A => B => D
A => D
A => E => F => D

Hier fuer ist Backtracking noetig, dies versuch ich mit findall zu realisieren. Es funktioniert auch, er sucht wirklich alle Wege die es gibt. Da er mit in der Konsole alle Wege anzeigt. Nun will ich aber die Kosten fuer jeden weg in eine Liste einfuegen, dass ich sie spaeter bearbeiten bzw. auswerten kann. Und genau hier liegt mein Problem.

findall(Summe, verbindungskosten(X, Y, 0, [Y], Summe),L), write(L).

Anstatt, dass er mit wirklich die Summen in L uebergibt, landen in der Liste nur drei Variablen _G307, _G305 ...

In einem Bsp von der Uni steht es auch so aehnlich drin mit dem findall leider funktioniert das Bsp auch net

 

[deepthroat]

verbindungskosten(X, X, S, Pfad, Summe) :- write('Kosten: '), write(Summe), write('\nPfad: '), write(Pfad), write('\n').
verbindungskosten(X, Y, S, Pfad, Summe) :-  kosten(A, Y, Z), 
       N is S + Z,
       append([A],Pfad,NeuerPfad),
       verbindungskosten(X, A, N, NeuerPfad, N).

Hier liegt das Problem. Zuerstmal sagt das erste Statement aus, dass die verbindungskosten von einem Knoten zu sich selbst völlig beliebig sind. Außerdem kann man auf jedem beliebigen Pfad von X zu X kommen:

| ?- verbindungskosten(a, b, 500, [a, b, c, d, e, a, b, c], 10000).
Yes

Meinst du, das dies sinnvoll ist?

Außerdem ist Summe im zweiten Statement eine völlig freie Variable. D.h. du stellst innerhalb des Prädikats ja überhaupt keine Bedingungen an die Variable Summe. So kann Prolog natürlich ganz einfach irgendwelche Variablen generieren, so dass es trivial ist das Prädikat verbindungskosten für die Variable Summe zu erfüllen - es ist noch nicht mal Backtracking notwendig

Ich wäre etwas anders an die Berechnung der Verbindungskosten herangegangen.
Z.B.

verbindungskosten(X, X, [X], 0).
verbindungskosten(X, Y, Pfad, Summe) :-  kosten(X, A, Z),
       verbindungskosten(A, Y, RestPfad, NSum), Summe is NSum + Z, append([X], RestPfad, Pfad).

Gruß

 

[Scotty86]

Ja, es gibt viele Moeglichkeiten das zu machen, nur hat deine Antwort grad nix mit meinem Problem zu tun.

Er traversiert den Baum ja richtig, da ich ihn gerichtet definiert habe. Mein Problem liegt bei dem findall, es kommen zwar alle sinnvollen Loesungen per write raus, nur Setzt er sie mir leider nicht in L ein.

 

[deepthroat]

Ja, es gibt viele Moeglichkeiten das zu machen, nur hat deine Antwort grad nix mit meinem Problem zu tun.

Er traversiert den Baum ja richtig, da ich ihn gerichtet definiert habe. Mein Problem liegt bei dem findall, es kommen zwar alle sinnvollen Loesungen per write raus, nur Setzt er sie mir leider nicht in L ein.

Nein, dein Problem liegt nicht bei dem findall. Du hast irgendwie noch nicht verstanden wie Prolog funktioniert. Es gibt keine "Rückgabewerte" in Prolog. Prolog "unifiziert" Variablen mit Hilfe von Backtracking und versucht eine Aussage anhand der Wissensbasis zu beweisen.

Natürlich traversiert Prolog den Baum, aber es nützt dir doch nichts wenn du am Ende der Rekursion den Pfad und die Summe zur Verfügung hast, die Variable wo alles gestartet wurde ist davon doch unberührt wenn sie in keiner Beziehung dazu steht.

Bsp:

xyz(X) :- 3 is 1 + 2.

Das kommt etwa auf's gleiche raus wie bei deinem verbindungskosten Prädikat. Wie soll Prolog denn jetzt die Variable X bestimmen? Was kann man für die Variable X als Wert erwarten? Wenn die Variable des Prädikats nicht auf der rechten Seite auftaucht, kannst du sie doch gleich weglassen.

Hier nochmal etwas anders:

verbindungskosten(X, X, [X], 0).
verbindungskosten(X, Y, [X|R], Summe) :-  kosten(X, A, Z),
       verbindungskosten(A, Y, R, NSum), Summe is NSum + Z.

Da steht:

1. es gilt verbindungskosten(X, X, [X], 0).
   
   D.h. die Verbindungskosten von einem Knoten zu sich selbst wo der Pfad nur den Knoten enthält, muß 0 sein.
2. Anderenfalls, für einen Knoten X zu einem Knoten Y:
   
   wenn gilt kosten(X, A, Z) und es gilt verbindungskosten(A, Y, R, NSum) und es gilt Summe = NSum + Z, dann gilt auch verbindungskosten(X, Y, [X | R], Summe).

Ich hoffe das macht deutlich, dass es etwas "andersherum" funktioniert als du dachtest.

Gruß

 

[Scotty86]

Ah, ja, jetzt versteh ich

So was aehnliches hatte ich als ersten Versuch auch, bekam dann den Fehler:
No permission to modify static_procedure
Dieser Fehler bezog sich auf die Zeile mit "S is bla + bla", also hab ich gedacht ich darf S keinen Wert zuweisen... bei genauerem betrachten stand in der Zeile vorher aber ein Punkt anstelle von einem Komma :-(

Vielen Dank fuer deine Hilfe und Muse, hast mir sehr geholfen!