#!/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)))]))))))
|