Prolog - Breitensuche < Sonstige < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:54 Di 26.01.2010 | | Autor: | Wimme |
| Aufgabe | 1) Erweitern Sie die Datei "search.pl" um die Breitensuche zu implementieren.
2) Erweitern Sie die Datei "search.pl" um die Tiefensuche zu implementieren.
____________Datei "search.pl"_______________
search(Paths,X):-
choose([Node|Path],Paths,_),
goal(Node),
reverse([Node|Path],X).
search(Paths,Path):-
choose(P,Paths,RestofPaths),
findall([S|P],S expands P,Exps),
combine(Exps,RestofPaths, NewPaths),
search(NewPaths,Path).
NewState expands [State|_]:-
arc(State,NewState).
|
Hallo!
Erstmal natürlich hauptsächlich zur Aufgabe 1).
Vor allem implementiert werden müssen "combine" und "choose".
Ein Graph wird übrigens z.B. wie folgt gebaut:
arc(a,b).
arc(a,f).
arc(b,c).
arc(b,e).
arc(b,f).
goal(f).
So sieht meine bisherige "Lösung" zu 1) aus:
/*
simply puts all the lists of the first and second parameter into a single list
the lists of RestofPaths are at the beginning of the list
*/
combine([],[],NewPaths) :- NewPaths = [].
combine(Exps,[R|RestofPaths],NewPaths) :- NewPaths = [R|NewPath],combine(Exps,RestofPaths,NewPath).
combine([E|Exps],[],NewPaths) :- NewPaths = [E|NewPath],combine(Exps,[],NewPath).
/*choose(Path,Paths,RestofPaths)*/
choose(Path,[P|Paths],Paths) :- Path = P.
______________
Aufruf einer Suche zB mit search( [ [a] ],X).
Im Prinzip funktioniert das auch so, denke ich.
Aber:
1) Die Listen für die Pfade werden ja vor dem Prüfen auf "goal" erstellt. Bei meinem Beispielbaum zB würde [c,b] erstellt, bevor "b" auf "goal" überprüft wurde. So richtig schöne Breitensuche ist das dann nicht mehr, oder?
2) kommt mir meine Lösung merkwürdig vor. Habt ihr andere Ideen, wie man Breitensuche mit Hilfe der Vorgaben implementieren könnte?
Erstmal soweit. Hoffentlich kann hier einer gut Prolog und ich habe mich verständlich genug ausgedrückt!
Bis dann,
Wimme
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 So 31.01.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
