% nacteni:
/* ['4.1_9.pl']. */
bestsearch(Start,Solution) :- biggest(Big), expand([], l(Start,0/0),Big,_,yes,Solution).
expand(P,l(N,_),_,_,yes,[N|P]) :- goal(N).
expand(P,l(N,F/G),Bound,Tree1,Solved,Sol) :- F=<Bound,
(bagof(M/C,(move(N,M,C),\+ member(M,P)),Succ),!,succlist(G,Succ,Ts),
bestf(Ts,F1), expand(P,t(N,F1/G,Ts),Bound,Tree1,Solved,Sol);Solved=never).
expand(P,t(N,F/G,[T|Ts]),Bound,Tree1,Solved,Sol) :- F=<Bound, bestf(Ts,BF),
min(Bound,BF,Bound1),expand([N|P],T,Bound1,T1,Solved1,Sol),
continue(P,t(N,F/G,[T1|Ts]),Bound,Tree1,Solved1,Solved,Sol).
expand(_,t(_,_,[]),_,_,never,_) :- !.
expand(_,Tree,Bound,Tree,no,_) :- f(Tree,F), F>Bound.
continue(_,_,_,_,yes,yes,_Sol).
continue(P,t(N,_F/G,[T1|Ts]),Bound,Tree1,Solved1,Solved,Sol) :-
(Solved1=no,insert(T1,Ts,NTs);Solved1=never,NTs=Ts),
bestf(NTs,F1),expand(P,t(N,F1/G,NTs),Bound,Tree1,Solved,Sol).
succlist(_,[],[]).
succlist(G0,[N/C|NCs],Ts) :- G is G0+C,h(N,H),F is G+H,
succlist(G0,NCs,Ts1), insert(l(N,F/G),Ts1,Ts).
insert(T,Ts,[T|Ts]) :- f(T,F),bestf(Ts,F1),F=<F1,!.
insert(T,[T1|Ts],[T1|Ts1]) :- insert(T,Ts,Ts1).
f(l(_,F/_),F).
f(t(_,F/_,_),F).
bestf([T|_], F) :- f(T,F).
bestf([], Big) :- biggest(Big).
min(X,Y,X) :- X=<Y,!.
min(_X,Y,Y).
| #!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import Cons, Nil, member
from romanian_cities import graph
# horni zavora pro cenu nejlepsi cesty
biggest = 9999
def best_search(start):
for _, solved, sol in expand(Nil, (start, 0, 0), biggest):
if solved == "yes":
yield sol
def expand(path, tree, bound):
if len(tree) == 3: # a leaf
node, f_, g = tree
if is_goal(node):
yield (None, "yes", (f_, Cons(node, path)))
if f_ <= bound:
succ = Nil
for m, c in move_anyYC(node):
if not member(m, path):
succ = Cons((m, c), succ)
if succ == Nil:
yield (None, "never", None)
else:
trees = succlist(g, succ)
f1 = bestf(trees)
for tree1, solved, sol in expand(path, (node, f1, g, trees), bound):
yield (tree1, solved, sol)
elif f_ > bound:
yield (tree, "no", None)
else: # a tree
node, f_, g, trees = tree
if trees == Nil:
yield (None, "never", None)
else:
if f_ <= bound:
bound1 = min(bound, bestf(trees.tail))
for t1, solved1, sol1 in expand(Cons(node, path), trees.head, bound1):
for tree1, solved, sol in continue_(path, (node, f_, g, Cons(t1, trees.tail)),
bound, solved1, sol1):
yield (tree1, solved, sol)
elif f_ > bound:
yield (tree, "no", None)
def continue_(path, tree, bound, subtr_solved, sol):
node, _, g, trees = tree
if subtr_solved == "yes":
yield (None, "yes", sol)
elif subtr_solved == "no":
nts = insert(trees.head, trees.tail)
f1 = bestf(nts)
for tree1, solved, sol in expand(path, (node, f1, g, nts), bound):
yield (tree1, solved, sol)
elif subtr_solved == "never":
f1 = bestf(trees.tail)
for tree1, solved, sol in expand(path, (node, f1, g, trees.tail), bound):
yield (tree1, solved, sol)
def succlist(g0, succ):
if succ == Nil:
return Nil
n, c = succ.head
g = g0 + c
f_ = g + h(n)
ts1 = succlist(g0, succ.tail)
ts = insert((n, f_, g), ts1)
return ts
def f(tree):
if len(tree) == 3: # a leaf
_, f_, _ = tree
else: # a tree
_, f_, _, _ = tree
return f_
def bestf(trees):
if trees == Nil:
return biggest
return f(trees.head)
def insert(t, ts):
if f(t) <= bestf(ts):
return Cons(t, ts)
return Cons(ts.head, insert(t, ts.tail))
def is_goal(x):
# zavisi na resenem problemu
return x == "Bukurest"
def move_anyYC(x):
# zavisi na resenem problemu
if x in graph:
for y, c in graph[x][0]:
yield (y, c)
def h(x):
# zavisi na resenem problemu
return graph[x][1]
# demonstracni vypis
if __name__ == "__main__":
print("Best-First Search (algoritmus A*)")
print("Veskere jednoduche cesty mezi mesty Arad a Bukurest serazene vzestupne podle ceny:")
for solution in best_search('Arad'):
print(solution)
Best-First Search (algoritmus A*)
Veskere jednoduche cesty mezi mesty Arad a Bukurest serazene vzestupne podle ceny:
(418, ['Bukurest', 'Pitesti', 'Rimnicu_Vilcea', 'Sibiu', 'Arad'])
(450, ['Bukurest', 'Fagaras', 'Sibiu', 'Arad'])
(575, ['Bukurest', 'Pitesti', 'Rimnicu_Vilcea', 'Sibiu', 'Oradea', 'Zerind', 'Arad'])
(605, ['Bukurest', 'Pitesti', 'Craiova', 'Rimnicu_Vilcea', 'Sibiu', 'Arad'])
(607, ['Bukurest', 'Fagaras', 'Sibiu', 'Oradea', 'Zerind', 'Arad'])
(733, ['Bukurest', 'Pitesti', 'Craiova', 'Dobreta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad'])
(762, ['Bukurest', 'Pitesti', 'Craiova', 'Rimnicu_Vilcea', 'Sibiu', 'Oradea', 'Zerind', 'Arad'])
(838, ['Bukurest', 'Pitesti', 'Rimnicu_Vilcea', 'Craiova', 'Dobreta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad'])
(1030, ['Bukurest', 'Fagaras', 'Sibiu', 'Rimnicu_Vilcea', 'Craiova', 'Dobreta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad'])
(1109, ['Bukurest', 'Fagaras', 'Sibiu', 'Rimnicu_Vilcea', 'Pitesti', 'Craiova', 'Dobreta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad'])
|