Stáhnout: 5.3_15.pl  SWISH   Zobrazit: jednoduše   5.3_15.py

% nacteni:
/* ['5.3_15.pl']. */

?- op(600, xfx, --->).
?- op(500, xfx, :).

andor(Node,SolutionTree) :- biggest(Bound),expand(leaf(Node,0,0),Bound,SolutionTree,yes).

% Case 1: bound exceeded, in all remaining cases F =< Bound
expand(Tree,Bound,Tree,no) :- f(Tree,F),F>Bound,!.
% Case 2: goal encountered
expand(leaf(Node,F,_C),_,solvedleaf(Node,F),yes) :- goal(Node),!.
% Case 3: expanding a leaf
expand(leaf(Node,_F,C),Bound,NewTree,Solved) :- expandnode(Node,C,Tree1),!,
    (expand(Tree1,Bound,NewTree,Solved);Solved=never,!).
% Case 4: expanding a tree
expand(tree(Node,_F,C,SubTrees),Bound,NewTree,Solved) :- Bound1 is Bound-C,
    expandlist(SubTrees,Bound1,NewSubs,Solved1),
    continue(Solved1,Node,C,NewSubs,Bound,NewTree,Solved).

expandlist(Trees,Bound,NewTrees,Solved) :-
    selecttree(Trees,Tree,OtherTrees,Bound,Bound1),
    expand(Tree,Bound1,NewTree,Solved1),
    combine(OtherTrees,NewTree,Solved1,NewTrees,Solved).

continue(yes,Node,C,SubTrees,_,solvedtree(Node,F,SubTrees),yes) :-
    bestf(SubTrees,H), F is C+H,!.
continue(never,_,_,_,_,_,never) :- ! .
continue(no,Node,C,SubTrees,Bound,NewTree,Solved) :- bestf(SubTrees,H),
    F is C+H,!,expand(tree(Node,F,C,SubTrees),Bound,NewTree,Solved).
    
% slide 16

combine(or:_,Tree,yes,Tree,yes) :- !.
combine(or:Trees,Tree,no,or:NewTrees,no) :- insert(Tree,Trees,NewTrees),!.
combine(or:[],_,never,_,never) :- ! .
combine(or:Trees,_,never,or:Trees,no) :- !.
combine(and:Trees,Tree,yes,and:[Tree|Trees],yes) :- allsolved(Trees),!.
combine(and:_,_,never,_,never) :- ! .
combine(and:Trees,Tree,_YesNo,and:NewTrees,no) :- insert(Tree,Trees,NewTrees),!.

expandnode(Node,C,tree(Node,F,C,Op:SubTrees)) :- Node ---> Op:Successors,
    evaluate(Successors,SubTrees),bestf(Op:SubTrees,H),F is C+H.
    
evaluate([],[]).
evaluate([Node/C|NodesCosts],Trees) :- h(Node,H),F is C+H,evaluate(NodesCosts,Trees1),
    insert( leaf(Node,F,C),Trees1,Trees).
    
allsolved([]).
allsolved([Tree|Trees]) :- solved(Tree),allsolved(Trees).

solved(solvedtree(_,_,_)).
solved(solvedleaf(_,_)).

% slide 17

f(Tree,F) :- arg(2,Tree,F),! .

insert(T ,[],[ T]) :- ! .
insert(T,[T1|Ts],[T,T1|Ts]) :- solved(T1),!.
insert(T,[T1|Ts],[T1|Ts1])  :- solved(T), insert(T,Ts,Ts1),! .
insert(T,[T1|Ts],[T,T1|Ts]) :- f(T,F), f(T1,F1),F=<F1,!.
insert(T,[T1|Ts],[T1|Ts1])  :- insert(T,Ts,Ts1).

% First tree in OR-list is best
bestf(or:[Tree|_], F) :- f(Tree,F), !.
bestf(and:[],0) :- ! .
bestf(and:[Tree1|Trees],F) :- f(Tree1,F1),bestf(and:Trees,F2),F is F1+F2,!.
bestf(Tree,F) :- f(Tree,F).

selecttree(Op:[Tree],Tree,Op:[],Bound,Bound) :- !. % The only candidate
selecttree(Op:[Tree|Trees],Tree,Op:Trees,Bound,Bound1) :- bestf(Op:Trees,F),
(Op=or,!,min(Bound,F,Bound1);Op=and,Bound1 is Bound-F).
min(A,B,A) :- A<B,!.
min(_A,B,B).


#!/usr/bin/env python
# encoding=utf-8 (pep 0263)

from linked_lists import LinkedList, Cons, Nil

# horni zavora pro cenu nejlepsi cesty
biggest = 9999

# format uzlu: ("leaf", n, f, c)
#              ("tree", n, f, c, subtrees)
#              ("solved_leaf", n, f)
#              ("solved_tree", n, f, subtrees)

# format seznamu potomku:
#              ("and", trees)
#              ("or", trees)
#              ("and_result", trees)
#              ("or_result", tree)

def andor(node):
    sol, solved = expand(("leaf", node, 0, 0), biggest)
    if solved == "yes":
        return sol
    else:
        raise ValueError("Reseni neexistuje.")

def expand(tree, bound):
    if f(tree) > bound:
        return (tree, "no")
    tree_type = tree[0]
    if tree_type == "leaf":
        _, node, f_, c = tree
        if is_goal(node):
            return (("solved_leaf", node, f_), "yes")
        tree1 = expandnode(node, c)
        if tree1 is None: # neexistuji naslednici
            return (None, "never")
        return expand(tree1, bound)
    elif tree_type == "tree":
        _, node, f_, c, subtrees = tree
        newsubs, solved1 = expandlist(subtrees, bound-c)
        return continue_(solved1, node, c, newsubs, bound)

def expandlist(trees, bound):
    tree, othertrees, bound1 = select_tree(trees, bound)
    newtree, solved = expand(tree, bound1)
    return combine(othertrees, newtree, solved)

def continue_(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 expand(("tree", node, f_, c, subtrees), bound)

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 expandnode(node, c):
    succ = get_successors(node)
    if succ is None:
        return None
    op, successors = succ
    subtrees = evaluate(successors)
    h_ = bestf((op, subtrees))
    f_ = c + h_
    return ("tree", node, f_, c, (op, subtrees))

def evaluate(nodes):
    if nodes == Nil:
        return Nil
    node, c = nodes.head
    h_ = h(node)
    f_ = c + h_
    trees1 = evaluate(nodes.tail)
    trees = insert(("leaf", node, f_, c), trees1)
    return trees

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 f(tree):
    return tree[2]

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)

def h(_):
    # zavisi na resenem problemu
    return 0

graph = dict(
    a=("or", LinkedList([("b", 1), ("c", 3)])),
    b=("and", LinkedList([("d", 1), ("e", 1)])),
    c=("and", LinkedList([("f", 2), ("g", 1)])),
    e=("or", LinkedList([("h", 6)])),
    f=("or", LinkedList([("h", 2), ("i", 3)])))

goals = dict(d=True, g=True, h=True)

def is_goal(node):
    # zavisi na resenem problemu
    return node in goals

# tato funkce nahrazuje prologovska fakta tvaru node ---> Op:Subtrees
# a pro zadany node navraci prislusne Op:Subtrees
def get_successors(node):
    # zavisi na resenem problemu
    if node in graph:
        return graph[node]
    return None

# demonstracni vypis
if __name__ == "__main__":
    print('Prohledavani AND/OR grafu')
    print('\n  Graf:')
    print('    a ---> or:[b/1,c/3].')
    print('    b ---> and:[d/1,e/1].')
    print('    c ---> and:[f/2,g/1].')
    print('    e ---> or:[h/6].')
    print('    f ---> or:[h/2,i/3].')
    print('    h(X,0).')
    print('    goal(d).')
    print('    goal(g).')
    print('    goal(h).')
    print('\nVysledky dotazu andor("a"):')
    print(andor("a"))

 Stáhnout: 5.3_15.pl  SWISH   Zobrazit: jednoduše   5.3_15.py