#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import LinkedList, Cons, Nil, member, append
def is_goal(x):
# zavisi na resenem problemu
return x == "E"
def solution(node):
for path in breadth_first_search(LinkedList([LinkedList(node)])):
yield path
def breadth_first_search(paths):
if paths == Nil:
return
path = paths.head
node = path.head
if is_goal(node):
yield path
new_paths = Nil
for node1 in move_anyY(node):
if not member(node1, path):
new_paths = Cons(Cons(node1, path), new_paths)
if new_paths != Nil:
paths1 = append(paths.tail, new_paths)
else:
paths1 = paths.tail
for path in breadth_first_search(paths1):
yield path
graph = dict(A=["B", "E", "F"],
B=["C"], F=["C"],
C=["D"],
D=["E"])
def move_anyY(x):
# zavisi na resenem problemu
if x in graph:
for y in graph[x]:
yield y
# demonstracni vypis
if __name__ == "__main__":
print("Breadth-First Search")
print("Volani next(solution('A')): %s" % next(solution('A')))
print("Vsechna reseni solution('A'):")
for s in solution('A'):
print s
Breadth-First Search
Volani next(solution('A')): ['E', 'A']
Vsechna reseni solution('A'):
['E', 'A']
['E', 'D', 'C', 'F', 'A']
['E', 'D', 'C', 'B', 'A']
| % nacteni:
/* ['3.6_17.pl']. */
solution(Start ,Solution) :- breadth_first_search([[ Start ]], Solution).
breadth_first_search([[ Node|Path]|_],[Node|Path]) :- goal(Node).
breadth_first_search([[ N|Path]|Paths],Solution) :-
bagof([M,N|Path],(move(N,M),\+ member(M,[N|Path])), NewPaths),
NewPaths\=[], append(Paths,NewPaths,Path1), !,
breadth_first_search(Path1,Solution); breadth_first_search(Paths,Solution).
% vzorova data
goal(e).
move(a,b). move(a,e). move(a,f).
move(b,c). move(f,c). move(c,d). move(d,e).
% demonstracni vypis
start:-
write('breadth_first_search'),nl,
write('Prvni reseni solution(a,Solution):'),nl,
solution(a,Solution),write(Solution),nl.
?-start.
breadth_first_search
Prvni reseni solution(a,Solution):
[e,a]
|