#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import LinkedList, Cons, Nil, member_anyX
graph = dict(
a=("or", LinkedList(["b", "c"])),
b=("and", LinkedList(["d", "e"])),
c=("and", LinkedList(["f", "g"])),
e=("or", LinkedList(["h"])),
f=("and", LinkedList(["h", "i"])))
goals = dict(d=True, g=True, h=True)
def is_goal(node):
# zavisi na resenem problemu
return node in goals
def solve(node):
if is_goal(node):
yield node
if node in graph:
nodes = graph[node][1]
if graph[node][0] == "or":
for node1 in member_anyX(nodes):
for tree in solve(node1):
yield (node, "--->", tree)
elif graph[node][0] == "and":
for trees in solveall(nodes):
yield (node, "--->", ("and", trees))
def solveall(nodes):
if nodes == Nil:
yield Nil
else:
for tree in solve(nodes.head):
for trees in solveall(nodes.tail):
yield Cons(tree, trees)
# demonstracni vypis
if __name__ == "__main__":
print('Prohledavani AND/OR grafu')
print('\n Graf:')
print(' a ---> or:[b,c].')
print(' b ---> and:[d,e].')
print(' c ---> and:[f,g].')
print(' e ---> or:[h].')
print(' f ---> and:[h,i].')
print(' goal(d).')
print(' goal(g).')
print(' goal(h).')
print('\nVysledky dotazu solve("a"):')
for solution in solve("a"):
print(solution)
Prohledavani AND/OR grafu
Graf:
a ---> or:[b,c].
b ---> and:[d,e].
c ---> and:[f,g].
e ---> or:[h].
f ---> and:[h,i].
goal(d).
goal(g).
goal(h).
Vysledky dotazu solve("a"):
('a', '--->', ('b', '--->', ('and', ['d', ('e', '--->', 'h')])))
|