Stáhnout: 4.1_9.pl  SWISH   Zobrazit: jednoduše   4.1_9.py

% 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)

 Stáhnout: 4.1_9.pl  SWISH   Zobrazit: jednoduše   4.1_9.py