SHARE
TWEET

lab3

krstevskim Apr 24th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from sys import maxsize as infinity
  2. import bisect
  3.  
  4. class Queue:
  5.     """Queue is an abstract class/interface. There are three types:
  6.       Stack(): A Last In First Out Queue.
  7.       FIFOQueue(): A First In First Out Queue.
  8.       PriorityQueue(order, f): Queue in sorted order (default min-first).
  9.   Each type supports the following methods and functions:
  10.       q.append(item)  -- add an item to the queue
  11.       q.extend(items) -- equivalent to: for item in items: q.append(item)
  12.       q.pop()         -- return the top item from the queue
  13.       len(q)          -- number of items in q (also q.__len())
  14.       item in q       -- does q contain item?
  15.   Note that isinstance(Stack(), Queue) is false, because we implement stacks
  16.   as lists.  If Python ever gets interfaces, Queue will be an interface."""
  17.  
  18.     def __init__(self):
  19.         raise NotImplementedError
  20.  
  21.     def extend(self, items):
  22.         for item in items:
  23.             self.append(item)
  24.  
  25.  
  26. def Stack():
  27.     """A Last-In-First-Out Queue."""
  28.     return []
  29.  
  30.  
  31. class FIFOQueue(Queue):
  32.     """A First-In-First-Out Queue."""
  33.  
  34.     def __init__(self):
  35.         self.A = []
  36.         self.start = 0
  37.  
  38.     def append(self, item):
  39.         self.A.append(item)
  40.  
  41.     def __len__(self):
  42.         return len(self.A) - self.start
  43.  
  44.     def extend(self, items):
  45.         self.A.extend(items)
  46.  
  47.     def pop(self):
  48.         e = self.A[self.start]
  49.         self.start += 1
  50.         if self.start > 5 and self.start > len(self.A) / 2:
  51.             self.A = self.A[self.start:]
  52.             self.start = 0
  53.         return e
  54.  
  55.     def __contains__(self, item):
  56.         return item in self.A[self.start:]
  57.  
  58.  
  59. class PriorityQueue(Queue):
  60.     """A queue in which the minimum (or maximum) element (as determined by f and
  61.   order) is returned first. If order is min, the item with minimum f(x) is
  62.   returned first; if order is max, then it is the item with maximum f(x).
  63.   Also supports dict-like lookup. This structure will be most useful in informed searches"""
  64.  
  65.     def __init__(self, order=min, f=lambda x: x):
  66.         self.A = []
  67.         self.order = order
  68.         self.f = f
  69.  
  70.     def append(self, item):
  71.         bisect.insort(self.A, (self.f(item), item))
  72.  
  73.     def __len__(self):
  74.         return len(self.A)
  75.  
  76.     def pop(self):
  77.         if self.order == min:
  78.             return self.A.pop(0)[1]
  79.         else:
  80.             return self.A.pop()[1]
  81.  
  82.     def __contains__(self, item):
  83.         return any(item == pair[1] for pair in self.A)
  84.  
  85.     def __getitem__(self, key):
  86.         for _, item in self.A:
  87.             if item == key:
  88.                 return item
  89.  
  90.     def __delitem__(self, key):
  91.         for i, (value, item) in enumerate(self.A):
  92.             if item == key:
  93.                 self.A.pop(i)
  94.  
  95.  
  96. # ______________________________________________________________________________________________
  97. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  98. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  99. # na sekoj eden problem sto sakame da go resime
  100.  
  101.  
  102. class Problem:
  103.     """The abstract class for a formal problem.  You should subclass this and
  104.   implement the method successor, and possibly __init__, goal_test, and
  105.   path_cost. Then you will create instances of your subclass and solve them
  106.   with the various search functions."""
  107.  
  108.     def __init__(self, initial, goal=None):
  109.         """The constructor specifies the initial state, and possibly a goal
  110.       state, if there is a unique goal.  Your subclass's constructor can add
  111.       other arguments."""
  112.         self.initial = initial
  113.         self.goal = goal
  114.  
  115.     def successor(self, state):
  116.         """Given a state, return a dictionary of {action : state} pairs reachable
  117.       from this state. If there are many successors, consider an iterator
  118.       that yields the successors one at a time, rather than building them
  119.       all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  120.         raise NotImplementedError
  121.  
  122.     def actions(self, state):
  123.         """Given a state, return a list of all actions possible from that state"""
  124.         raise NotImplementedError
  125.  
  126.     def result(self, state, action):
  127.         """Given a state and action, return the resulting state"""
  128.         raise NotImplementedError
  129.  
  130.     def goal_test(self, state):
  131.         """Return True if the state is a goal. The default method compares the
  132.       state to self.goal, as specified in the constructor. Implement this
  133.       method if checking against a single self.goal is not enough."""
  134.         return state == self.goal
  135.  
  136.     def path_cost(self, c, state1, action, state2):
  137.         """Return the cost of a solution path that arrives at state2 from
  138.       state1 via action, assuming cost c to get up to state1. If the problem
  139.       is such that the path doesn't matter, this function will only look at
  140.       state2.  If the path does matter, it will consider c and maybe state1
  141.       and action. The default method costs 1 for every step in the path."""
  142.         return c + 1
  143.  
  144.     def value(self):
  145.         """For optimization problems, each state has a value.  Hill-climbing
  146.       and related algorithms try to maximize this value."""
  147.         raise NotImplementedError
  148.  
  149.  
  150. # ______________________________________________________________________________
  151. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  152. # Klasata Node ne se nasleduva
  153.  
  154. class Node:
  155.     """A node in a search tree. Contains a pointer to the parent (the node
  156.   that this is a successor of) and to the actual state for this node. Note
  157.   that if a state is arrived at by two paths, then there are two nodes with
  158.   the same state.  Also includes the action that got us to this state, and
  159.   the total path_cost (also known as g) to reach the node.  Other functions
  160.   may add an f and h value; see best_first_graph_search and astar_search for
  161.   an explanation of how the f and h values are handled. You will not need to
  162.   subclass this class."""
  163.  
  164.     def __init__(self, state, parent=None, action=None, path_cost=0):
  165.         "Create a search tree Node, derived from a parent by an action."
  166.         self.state = state
  167.         self.parent = parent
  168.         self.action = action
  169.         self.path_cost = path_cost
  170.         self.depth = 0
  171.         if parent:
  172.             self.depth = parent.depth + 1
  173.  
  174.     def __repr__(self):
  175.         return "<Node %s>" % (self.state,)
  176.  
  177.     def __lt__(self, node):
  178.         return self.state < node.state
  179.  
  180.     def expand(self, problem):
  181.         "List the nodes reachable in one step from this node."
  182.         return [self.child_node(problem, action)
  183.                 for action in problem.actions(self.state)]
  184.  
  185.     def child_node(self, problem, action):
  186.         "Return a child node from this node"
  187.         next = problem.result(self.state, action)
  188.         return Node(next, self, action,
  189.                     problem.path_cost(self.path_cost, self.state,
  190.                                       action, next))
  191.  
  192.     def solution(self):
  193.         "Return the sequence of actions to go from the root to this node."
  194.         return [node.action for node in self.path()[1:]]
  195.  
  196.     def solve(self):
  197.         "Return the sequence of states to go from the root to this node."
  198.         return [node.state for node in self.path()[0:]]
  199.  
  200.     def path(self):
  201.         "Return a list of nodes forming the path from the root to this node."
  202.         x, result = self, []
  203.         while x:
  204.             result.append(x)
  205.             x = x.parent
  206.         return list(reversed(result))
  207.  
  208.     # We want for a queue of nodes in breadth_first_search or
  209.     # astar_search to have no duplicated states, so we treat nodes
  210.     # with the same state as equal. [Problem: this may not be what you
  211.     # want in other contexts.]
  212.  
  213.     def __eq__(self, other):
  214.         return isinstance(other, Node) and self.state == other.state
  215.  
  216.     def __hash__(self):
  217.         return hash(self.state)
  218.  
  219.  
  220. """
  221. Информирано пребарување во рамки на граф
  222. """
  223.  
  224. def memoize(fn, slot=None):
  225.  
  226.     """ Запамети ја пресметаната вредност за која била листа од
  227.    аргументи. Ако е специфициран slot, зачувај го резултатот во
  228.    тој slot на првиот аргумент. Ако slot е None, зачувај ги
  229.    резултатите во речник.
  230.  
  231.    :param fn: зададена функција
  232.    :param slot: име на атрибут во кој се чуваат резултатите од функцијата
  233.    :return: функција со модификација за зачувување на резултатите
  234.    """
  235.     if slot:
  236.         def memoized_fn(obj, *args):
  237.             if hasattr(obj, slot):
  238.                 return getattr(obj, slot)
  239.             else:
  240.                 val = fn(obj, *args)
  241.                 setattr(obj, slot, val)
  242.                 return val
  243.     else:
  244.         def memoized_fn(*args):
  245.             if args not in memoized_fn.cache:
  246.                 memoized_fn.cache[args] = fn(*args)
  247.             return memoized_fn.cache[args]
  248.  
  249.         memoized_fn.cache = {}
  250.     return memoized_fn
  251.  
  252.  
  253. def best_first_graph_search(problem, f):
  254.     """Пребарувај низ следбениците на даден проблем за да најдеш цел. Користи
  255.     функција за евалуација за да се одлучи кој е сосед најмногу ветува и
  256.     потоа да се истражи. Ако до дадена состојба стигнат два пата, употреби
  257.     го најдобриот пат.
  258.  
  259.    :param problem: даден проблем
  260.    :param f: дадена функција за евристика
  261.    :return: Node or None
  262.    """
  263.     f = memoize(f, 'f')
  264.     node = Node(problem.initial)
  265.     if problem.goal_test(node.state):
  266.         return node
  267.     frontier = PriorityQueue(min, f)
  268.     frontier.append(node)
  269.     explored = set()
  270.     while frontier:
  271.         node = frontier.pop()
  272.         if problem.goal_test(node.state):
  273.             return node
  274.         explored.add(node.state)
  275.         for child in node.expand(problem):
  276.             if child.state not in explored and child not in frontier:
  277.                 frontier.append(child)
  278.             elif child in frontier:
  279.                 incumbent = frontier[child]
  280.                 if f(child) < f(incumbent):
  281.                     del frontier[incumbent]
  282.                     frontier.append(child)
  283.     return None
  284.  
  285.  
  286. def greedy_best_first_graph_search(problem, h=None):
  287.     """ Greedy best-first пребарување се остварува ако се специфицира дека f(n) = h(n).
  288.  
  289.    :param problem: даден проблем
  290.    :param h: дадена функција за евристика
  291.    :return: Node or None
  292.    """
  293.     h = memoize(h or problem.h, 'h')
  294.     return best_first_graph_search(problem, h)
  295.  
  296.  
  297. def astar_search(problem, h=None):
  298.     """ A* пребарување е best-first graph пребарување каде f(n) = g(n) + h(n).
  299.  
  300.    :param problem: даден проблем
  301.    :param h: дадена функција за евристика
  302.    :return: Node or None
  303.    """
  304.     h = memoize(h or problem.h, 'h')
  305.     return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
  306.  
  307.  
  308. def recursive_best_first_search(problem, h=None):
  309.     """Recursive best first search - ја ограничува рекурзијата
  310.     преку следење на f-вредноста на најдобриот алтернативен пат
  311.     од било кој јазел предок (еден чекор гледање нанапред).
  312.  
  313.    :param problem: даден проблем
  314.    :param h: дадена функција за евристика
  315.    :return: Node or None
  316.    """
  317.     h = memoize(h or problem.h, 'h')
  318.  
  319.     def RBFS(problem, node, flimit):
  320.         if problem.goal_test(node.state):
  321.             return node, 0  # (втората вредност е неважна)
  322.         successors = node.expand(problem)
  323.         if len(successors) == 0:
  324.             return None, infinity
  325.         for s in successors:
  326.             s.f = max(s.path_cost + h(s), node.f)
  327.         while True:
  328.             # Подреди ги според најниската f вредност
  329.             successors.sort(key=lambda x: x.f)
  330.             best = successors[0]
  331.             if best.f > flimit:
  332.                 return None, best.f
  333.             if len(successors) > 1:
  334.                 alternative = successors[1].f
  335.             else:
  336.                 alternative = infinity
  337.             result, best.f = RBFS(problem, best, min(flimit, alternative))
  338.             if result is not None:
  339.                 return result, best.f
  340.  
  341.     node = Node(problem.initial)
  342.     node.f = h(node)
  343.     result, bestf = RBFS(problem, node, infinity)
  344.     return result
  345.  
  346.  
  347. def updateP1(P1):
  348.     x = P1[0]
  349.     y = P1[1]
  350.     n = P1[2]
  351.     if (y == 4 and n == 1):
  352.         n = n * (-1)
  353.     if (y == 0 and n == -1):
  354.         n = n * (-1)
  355.     ynew = y + n
  356.     return (x, ynew, n)
  357.  
  358.  
  359. def updateP2(P2):
  360.     x = P2[0]
  361.     y = P2[1]
  362.     n = P2[2]
  363.     if (x == 5 and y == 4 and n == 1):
  364.         n = n * (-1)
  365.     if (y == 0 and x == 9 and n == -1):
  366.         n = n * (-1)
  367.     xnew = x - n
  368.     ynew = y + n
  369.     return (xnew, ynew, n)
  370.  
  371.  
  372. def updateP3(P3):
  373.     x = P3[0]
  374.     y = P3[1]
  375.     n = P3[2]
  376.     if (x == 5 and n == -1):
  377.         n = n * (-1)
  378.     if (x == 9 and n == 1):
  379.         n = n * (-1)
  380.     xnew = x + n
  381.     return (xnew, y, n)
  382.  
  383.  
  384. def isValid(x, y, P1, P2, P3):
  385.     t = 1
  386.     if (x == P1[0] and y == P1[1]) or (x == P1[0] and y == P1[1] + 1):
  387.         t = 0
  388.     if (x == P2[0] and y == P2[1]) or (x == P2[0] and y == P2[1] + 1) or (x == P2[0] + 1 and y == P2[1]) or (
  389.             x == P2[0] + 1 and y == P2[1] + 1):
  390.         t = 0
  391.     if (x == P3[0] and y == P3[1]) or (x == P3[0] + 1 and y == P3[1]):
  392.         t = 0
  393.     return t
  394.  
  395.  
  396. class Istrazuvac(Problem):
  397.     def __init__(self, initial, goal):
  398.         self.initial = initial
  399.         self.goal = goal
  400.  
  401.     def successor(self, state):
  402.         successors = dict()
  403.         X = state[0]
  404.         Y = state[1]
  405.         P1 = state[2]
  406.         P2 = state[3]
  407.         P3 = state[4]
  408.         P1new = updateP1(P1)
  409.         P2new = updateP2(P2)
  410.         P3new = updateP3(P3)
  411.  
  412.         # Desno
  413.         if X < 5 and Y < 5:
  414.             Ynew = Y + 1
  415.             Xnew = X
  416.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  417.                 successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  418.         elif X >= 5 and Y < 10:
  419.             Xnew = X
  420.             Ynew = Y + 1
  421.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  422.                 successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  423.         # Levo
  424.         if Y - 1 >= 0:
  425.             Ynew = Y - 1
  426.             Xnew = X
  427.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  428.                 successors['Levo'] = (Xnew, Ynew, P1new, P2new, P3new)
  429.         # Gore
  430.         if Y >= 6 and X > 5:
  431.             Xnew = X - 1
  432.             Ynew = Y
  433.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  434.                 successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  435.         elif Y < 6 and X > 0:
  436.             Xnew = X - 1
  437.             Ynew = Y
  438.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  439.                 successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  440.         # Dolu
  441.         if X < 10:
  442.             Xnew = X + 1
  443.             Ynew = Y
  444.             if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  445.                 successors['Dolu'] = (Xnew, Ynew, P1new, P2new, P3new)
  446.         return successors
  447.  
  448.     def actions(self, state):
  449.         return self.successor(state).keys()
  450.  
  451.     def result(self, state, action):
  452.         possible = self.successor(state)
  453.         return possible[action]
  454.  
  455.     def goal_test(self, state):
  456.         g = self.goal
  457.         return (state[0] == g[0] and state[1] == g[1])
  458.  
  459.     def h(self, node):
  460.         rez = abs(node.state[0] - self.goal[0]) + abs(node.state[1] - self.goal[1])
  461.         return rez
  462.  
  463.  
  464. CoveceRedica = eval(input())
  465. CoveceKolona = eval(input())
  466. KukaRedica = eval(input())
  467. KukaKolona = eval(input())
  468.  
  469.  
  470. IstrazuvacInstance = Istrazuvac((CoveceRedica, CoveceKolona, (2, 2, -1), (7, 2, 1), (7, 8, 1)), (KukaRedica, KukaKolona))
  471.  
  472. answer = astar_search(IstrazuvacInstance).solution()
  473. print(answer)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top