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

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

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

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