#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import LinkedList, Cons, Nil
from and_or_best_search import BestSearch
biggest = 99
start = ("path", "a", "z")
stateS = dict(a=True, b=True, c=True, d=True, e=True)
stateU = dict(u=True, v=True, x=True, y=True, z=True)
borders = dict(l=True, k=True)
distances = dict(
a=[("b", 2), ("c", 3)],
b=[("d", 2)],
c=[("e", 1), ("l", 2)],
d=[("k", 1)],
e=[("k", 3), ("l", 2)],
k=[("u", 2), ("x", 3)],
l=[("u", 1)],
u=[("v", 5), ("y", 2)],
x=[("y", 3)],
y=[("z", 3)],
v=[("z", 3)])
def get_successors(node):
if node[0] == "path":
_, x, z = node
succ = Nil
if x in stateS and z in stateU:
for y in borders:
succ = Cons((("via", x, z, y), 0), succ)
if x in distances:
for y, d in distances[x]:
succ = Cons((("path", y, z), d), succ)
if succ == Nil:
return None
return ("or", succ)
if node[0] == "via":
_, x, z, y = node
return ("and", LinkedList([(("path", x, y), 0), (("path", y, z), 0)]))
def is_goal(node):
return node[0] == "path" and node[1] == node[2]
def h(node):
if is_goal(node):
return 0
if node[0] == "path":
_, x, z = node
if x in distances:
for y, d in distances[x]:
if y == z:
return d
if x in stateS and z in stateU or z in stateS and x in stateU:
return 2
return 1
if node[0] == "via":
_, x, z, _ = node
if x in stateS and z in stateU or z in stateS and x in stateU:
return 2
# demonstracni vypis
if __name__ == "__main__":
print("Cesta mezi mesty, algoritmus AND/OR A*\n")
print("Zadani: %s" % (start,))
print("\nNalezene reseni:")
obj = BestSearch(biggest, is_goal, get_successors, h)
solution = obj.search(start)
print("Prohledano %d stavu, vysledne reseni ma cenu %d." % (obj.total, solution[2]))
print(solution)
Cesta mezi mesty, algoritmus AND/OR A*
Zadani: ('path', 'a', 'z')
Nalezene reseni:
Prohledano 69 stavu, vysledne reseni ma cenu 11.
('solved_tree', ('path', 'a', 'z'), 11, ('or_result', ('solved_tree', ('path', 'c', 'z'), 11, ('or_result', ('solved_tree', ('via', 'c', 'z', 'l'), 8, ('and_result', [('solved_tree', ('path', 'l', 'z'), 6, ('or_result', ('solved_tree', ('path', 'u', 'z'), 6, ('or_result', ('solved_tree', ('path', 'y', 'z'), 5, ('or_result', ('solved_leaf', ('path', 'z', 'z'), 3))))))), ('solved_tree', ('path', 'c', 'l'), 2, ('or_result', ('solved_leaf', ('path', 'l', 'l'), 2)))]))))))
| % priklad Cesta mezi mesty pomoci AND/OR A*
move(a,b,2). move(a,c,3). move(b,e,3).
move(b,d,2). move(c,e,1). move(c,l,2).
move(e,k,4). move(e,l,2). move(k,u,2).
move(k,x,3). move(u,v,5). move(x,y,3).
move(y,z,3). move(v,z,3). move(l,u,1).
move(d,k,1). move(u,y,2).
stateS(a). stateS(b). stateS(c). stateS(d). stateS(e).
stateT(u). stateT(v). stateT(x). stateT(y). stateT(z).
border(l). border(k).
key(M1-M2,M3) :- stateS(M1), stateT(M2), border(M3).
city(X) :- (stateS(X);stateT(X);border(X)).
% slide 20 - konstrukce grafu
?- op(700, xfx, --->),
op(560,xfx,via). % operatory X-Z a X-Z via Y
% a-z ---> or:[a-z via k/0,a-z via l/0].
% a-v ---> or:[a-v via k/0,a-v via l/0].
% ...
X-Z ---> or:Problemlist :- city(X),city(Z), bagof((X-Z via Y)/0, key(X-Z,Y), Problemlist),!.
% a-l ---> or:[c-l/3,b-l/2].
% b-l ---> or:[e-l/3,d-l/2].
% ...
X-Z ---> or:Problemlist :- city(X),city(Z), bagof((Y-Z)/D, move(X,Y,D), Problemlist).
% a-z via l ---> and:[a-l/0,l-z/0].
% a-v via l ---> and:[a-l/0,l-v/0].
% ...
X-Z via Y ---> and:[(X-Y)/0,(Y-Z)/0]:- city(X),city(Z),key(X-Z,Y).
%goal(a-a). goal(b-b). ...
goal(X-X).
% heuristika h - podle hrany nebo ze stejneho statu=1, z ruzneho=2
h(X-X,0).
h(X-Z,C):-move(X,Z,C),!.
h(X-Z,C):-move(Z,X,C),!.
h(X-Z,2):-stateS(X),stateT(Z),!.
h(X-Z,2):-stateT(X),stateS(Z),!.
h(X-Z via _,2):-stateS(X),stateT(Z),!.
h(X-Z via _,2):-stateT(X),stateS(Z),!.
h(_-_,1).
biggest(99).
run:-
['5.3_15.pl'], nl,
write('Cesta mezi mesty, algoritmus AND/OR A*'), nl, nl,
Start=a-z,
write('Zadani: '), write(Start), nl,
andor(Start,SolutionTree),
write('Nalezene reseni:'),nl,
write(SolutionTree).
% s heuristikou h1 vyzaduje hodne pameti (pro d=26)
%:- set_prolog_stack(local, limit(256 000 000)). % vyzaduje 64-bit system
:- run.
% vim: set ft=prolog:
Cesta mezi mesty, algoritmus AND/OR A*
Zadani: a-z
Nalezene reseni:
solvedtree(a-z,11,solvedtree(a-z via l,11,and:[solvedtree(l-z,6,solvedtree(u-z,6,solvedtree(y-z,5,solvedleaf(z-z,3)))),solvedtree(a-l,5,solvedtree(c-l,5,solvedleaf(l-l,2)))]))
|