#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
""" Implementace algoritmu AND/OR A* """
from linked_lists import Cons, Nil
class BestSearch(object):
def __init__(self, bound, is_goal, get_successors, h):
self.total = 0
self.bound = bound
self.is_goal = is_goal
self.get_successors = get_successors
self.h = h
def search(self, start):
self.total = 0
sol, solved = self.expand(("leaf", start, 0, 0), self.bound)
if solved == "yes":
return sol
else:
raise ValueError("Reseni neexistuje.")
def expand(self, tree, bound):
if f(tree) > bound:
return (tree, "no")
tree_type = tree[0]
if tree_type == "leaf":
self.total = self.total + 1
_, node, f_, c = tree
if self.is_goal(node):
return (("solved_leaf", node, f_), "yes")
tree1 = self.expandnode(node, c)
if tree1 is None: # neexistuji naslednici
return (None, "never")
return self.expand(tree1, bound)
elif tree_type == "tree":
_, node, f_, c, subtrees = tree
newsubs, solved1 = self.expandlist(subtrees, bound-c)
return self.continue_(solved1, node, c, newsubs, bound)
def expandlist(self, trees, bound):
tree, othertrees, bound1 = select_tree(trees, bound)
newtree, solved = self.expand(tree, bound1)
return combine(othertrees, newtree, solved)
def continue_(self, subtr_solved, node, c, subtrees, bound):
if subtr_solved == "never":
return (None, "never")
h_ = bestf(subtrees)
f_ = c + h_
if subtr_solved == "yes":
return (("solved_tree", node, f_, subtrees), "yes")
if subtr_solved == "no":
return self.expand(("tree", node, f_, c, subtrees), bound)
def expandnode(self, node, c):
succ = self.get_successors(node)
if succ is None:
return None
op, successors = succ
subtrees = self.evaluate(successors)
h_ = bestf((op, subtrees))
f_ = c + h_
return ("tree", node, f_, c, (op, subtrees))
def evaluate(self, nodes):
if nodes == Nil:
return Nil
node, c = nodes.head
h_ = self.h(node)
f_ = c + h_
trees1 = self.evaluate(nodes.tail)
trees = insert(("leaf", node, f_, c), trees1)
return trees
def combine(subtrees, tree, solved):
op, trees = subtrees
if op == "or":
if solved == "yes":
return (("or_result", tree), "yes")
if solved == "no":
newtrees = insert(tree, trees)
return (("or", newtrees), "no")
if solved == "never":
if trees == Nil:
return (None, "never")
return (("or", trees), "no")
if op == "and":
if solved == "yes" and are_all_solved(trees):
return (("and_result", Cons(tree, trees)), "yes")
if solved == "never":
return (None, "never")
newtrees = insert(tree, trees)
return (("and", newtrees), "no")
def f(tree):
return tree[2]
def are_all_solved(trees):
if trees == Nil:
return True
return is_solved(trees.head) and are_all_solved(trees.tail)
def is_solved(tree):
tree_type = tree[0]
return tree_type == "solved_tree" or tree_type == "solved_leaf"
def insert(t, trees):
if trees == Nil:
return Cons(t, Nil)
t1 = trees.head
ts = trees.tail
if is_solved(t1):
return Cons(t, trees)
if is_solved(t):
return Cons(t1, insert(t, ts))
if f(t) <= f(t1):
return Cons(t, trees)
return Cons(t1, insert(t, ts))
def bestf(subtrees):
op = subtrees[0]
if op == "or":
trees = subtrees[1]
assert trees != Nil
return f(trees.head)
if op == "and" or op == "and_result":
trees = subtrees[1]
if trees == Nil:
return 0
return f(trees.head) + bestf(("and", trees.tail))
if op == "or_result":
tree = subtrees[1]
return f(tree)
def select_tree(subtrees, bound):
op, trees = subtrees
if trees.tail == Nil:
return (trees.head, (op, Nil), bound)
f_ = bestf((op, trees.tail))
assert op == "or" or op == "and"
if op == "or":
bound1 = min(bound, f_)
if op == "and":
bound1 = bound - f_
return (trees.head, (op, trees.tail), bound1)