Advertisement
Guest User

lab3 zad1 VI

a guest
Apr 24th, 2019
415
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 22.51 KB | None | 0 0
  1. # -*- coding: utf-8 -*-
  2.  
  3. import bisect
  4. import math
  5. from sys import maxsize as infinity
  6.  
  7. CoveceRedica = int(input()) + 1
  8. CoveceKolona = int(input()) + 1
  9. KukaRedica = int(input()) + 1
  10. KukaKolona = int(input()) + 1
  11.  
  12. """
  13. Дефинирање на класа за структурата на проблемот кој ќе го решаваме со пребарување.
  14. Класата Problem е апстрактна класа од која правиме наследување за дефинирање на основните
  15. карактеристики на секој проблем што сакаме да го решиме
  16. """
  17.  
  18.  
  19. class Problem:
  20.     def __init__(self, initial, goal=None):
  21.         self.initial = initial
  22.         self.goal = goal
  23.  
  24.     def successor(self, state):
  25.         """За дадена состојба, врати речник од парови {акција : состојба}
  26.        достапни од оваа состојба. Ако има многу следбеници, употребете
  27.        итератор кој би ги генерирал следбениците еден по еден, наместо да
  28.        ги генерирате сите одеднаш.
  29.  
  30.        :param state: дадена состојба
  31.        :return:  речник од парови {акција : состојба} достапни од оваа
  32.                  состојба
  33.        :rtype: dict
  34.        """
  35.         raise NotImplementedError
  36.  
  37.     def actions(self, state):
  38.         """За дадена состојба state, врати листа од сите акции што може да
  39.        се применат над таа состојба
  40.  
  41.        :param state: дадена состојба
  42.        :return: листа на акции
  43.        :rtype: list
  44.        """
  45.         return self.successor(state).keys()
  46.  
  47.     def result(self, state, action):
  48.         """За дадена состојба state и акција action, врати ја состојбата
  49.        што се добива со примена на акцијата над состојбата
  50.  
  51.        :param state: дадена состојба
  52.        :param action: дадена акција
  53.        :return: резултантна состојба
  54.        """
  55.         possible = self.successor(state)
  56.         return possible[action]
  57.  
  58.     def goal_test(self, state):
  59.         """Врати True ако state е целна состојба. Даденава имплементација
  60.        на методот директно ја споредува state со self.goal, како што е
  61.        специфицирана во конструкторот. Имплементирајте го овој метод ако
  62.        проверката со една целна состојба self.goal не е доволна.
  63.  
  64.        :param state: дадена состојба
  65.        :return: дали дадената состојба е целна состојба
  66.        :rtype: bool
  67.        """
  68.         return state == self.goal
  69.  
  70.     def path_cost(self, c, state1, action, state2):
  71.         """Врати ја цената на решавачкиот пат кој пристигнува во состојбата
  72.        state2 од состојбата state1 преку акцијата action, претпоставувајќи
  73.        дека цената на патот до состојбата state1 е c. Ако проблемот е таков
  74.        што патот не е важен, оваа функција ќе ја разгледува само состојбата
  75.        state2. Ако патот е важен, ќе ја разгледува цената c и можеби и
  76.        state1 и action. Даденава имплементација му доделува цена 1 на секој
  77.        чекор од патот.
  78.  
  79.        :param c: цена на патот до состојбата state1
  80.        :param state1: дадена моментална состојба
  81.        :param action: акција која треба да се изврши
  82.        :param state2: состојба во која треба да се стигне
  83.        :return: цена на патот по извршување на акцијата
  84.        :rtype: float
  85.        """
  86.         return c + 1
  87.  
  88.     def value(self):
  89.         """За проблеми на оптимизација, секоја состојба си има вредност. 
  90.        Hill-climbing и сличните алгоритми се обидуваат да ја максимизираат
  91.        оваа вредност.
  92.  
  93.        :return: вредност на состојба
  94.        :rtype: float
  95.        """
  96.         raise NotImplementedError
  97.  
  98.  
  99. """
  100. Дефинирање на класата за структурата на јазел од пребарување.
  101. Класата Node не се наследува
  102. """
  103.  
  104.  
  105. class Node:
  106.     def __init__(self, state, parent=None, action=None, path_cost=0):
  107.         """Креирај јазол од пребарувачкото дрво, добиен од parent со примена
  108.        на акцијата action
  109.  
  110.        :param state: моментална состојба (current state)
  111.        :param parent: родителска состојба (parent state)
  112.        :param action: акција (action)
  113.        :param path_cost: цена на патот (path cost)
  114.        """
  115.         self.state = state
  116.         self.parent = parent
  117.         self.action = action
  118.         self.path_cost = path_cost
  119.         self.depth = 0  # search depth
  120.         if parent:
  121.             self.depth = parent.depth + 1
  122.  
  123.     def __repr__(self):
  124.         return "<Node %s>" % (self.state,)
  125.  
  126.     def __lt__(self, node):
  127.         return self.state < node.state
  128.  
  129.     def expand(self, problem):
  130.         """Излистај ги јазлите достапни во еден чекор од овој јазол.
  131.  
  132.        :param problem: даден проблем
  133.        :return: листа на достапни јазли во еден чекор
  134.        :rtype: list(Node)
  135.        """
  136.         return [self.child_node(problem, action)
  137.                 for action in problem.actions(self.state)]
  138.  
  139.     def child_node(self, problem, action):
  140.         """Дете јазел
  141.  
  142.        :param problem: даден проблем
  143.        :param action: дадена акција
  144.        :return: достапен јазел според дадената акција
  145.        :rtype: Node
  146.        """
  147.         next_state = problem.result(self.state, action)
  148.         return Node(next_state, self, action,
  149.                     problem.path_cost(self.path_cost, self.state,
  150.                                       action, next_state))
  151.  
  152.     def solution(self):
  153.         """Врати ја секвенцата од акции за да се стигне од коренот до овој јазол.
  154.  
  155.        :return: секвенцата од акции
  156.        :rtype: list
  157.        """
  158.         return [node.action for node in self.path()[1:]]
  159.  
  160.     def solve(self):
  161.         """Врати ја секвенцата од состојби за да се стигне од коренот до овој јазол.
  162.  
  163.        :return: листа од состојби
  164.        :rtype: list
  165.        """
  166.         return [node.state for node in self.path()[0:]]
  167.  
  168.     def path(self):
  169.         """Врати ја листата од јазли што го формираат патот од коренот до овој јазол.
  170.  
  171.        :return: листа од јазли од патот
  172.        :rtype: list(Node)
  173.        """
  174.         x, result = self, []
  175.         while x:
  176.             result.append(x)
  177.             x = x.parent
  178.         result.reverse()
  179.         return result
  180.  
  181.     """Сакаме редицата од јазли кај breadth_first_search или
  182.    astar_search да не содржи состојби - дупликати, па јазлите што
  183.    содржат иста состојба ги третираме како исти. [Проблем: ова може
  184.    да не биде пожелно во други ситуации.]"""
  185.  
  186.     def __eq__(self, other):
  187.         return isinstance(other, Node) and self.state == other.state
  188.  
  189.     def __hash__(self):
  190.         return hash(self.state)
  191.  
  192.  
  193. """
  194. Дефинирање на помошни структури за чување на листата на генерирани, но непроверени јазли
  195. """
  196.  
  197.  
  198. class Queue:
  199.     """Queue е апстрактна класа / интерфејс. Постојат 3 типа:
  200.         Stack(): Last In First Out Queue (стек).
  201.         FIFOQueue(): First In First Out Queue (редица).
  202.         PriorityQueue(order, f): Queue во сортиран редослед (подразбирливо,од најмалиот кон
  203.                                 најголемиот јазол).
  204.     """
  205.  
  206.     def __init__(self):
  207.         raise NotImplementedError
  208.  
  209.     def append(self, item):
  210.         """Додади го елементот item во редицата
  211.  
  212.        :param item: даден елемент
  213.        :return: None
  214.        """
  215.         raise NotImplementedError
  216.  
  217.     def extend(self, items):
  218.         """Додади ги елементите items во редицата
  219.  
  220.        :param items: дадени елементи
  221.        :return: None
  222.        """
  223.         raise NotImplementedError
  224.  
  225.     def pop(self):
  226.         """Врати го првиот елемент од редицата
  227.  
  228.        :return: прв елемент
  229.        """
  230.         raise NotImplementedError
  231.  
  232.     def __len__(self):
  233.         """Врати го бројот на елементи во редицата
  234.  
  235.        :return: број на елементи во редицата
  236.        :rtype: int
  237.        """
  238.         raise NotImplementedError
  239.  
  240.     def __contains__(self, item):
  241.         """Проверка дали редицата го содржи елементот item
  242.  
  243.        :param item: даден елемент
  244.        :return: дали queue го содржи item
  245.        :rtype: bool
  246.        """
  247.         raise NotImplementedError
  248.  
  249.  
  250. class Stack(Queue):
  251.     """Last-In-First-Out Queue."""
  252.  
  253.     def __init__(self):
  254.         self.data = []
  255.  
  256.     def append(self, item):
  257.         self.data.append(item)
  258.  
  259.     def extend(self, items):
  260.         self.data.extend(items)
  261.  
  262.     def pop(self):
  263.         return self.data.pop()
  264.  
  265.     def __len__(self):
  266.         return len(self.data)
  267.  
  268.     def __contains__(self, item):
  269.         return item in self.data
  270.  
  271.  
  272. class FIFOQueue(Queue):
  273.     """First-In-First-Out Queue."""
  274.  
  275.     def __init__(self):
  276.         self.data = []
  277.  
  278.     def append(self, item):
  279.         self.data.append(item)
  280.  
  281.     def extend(self, items):
  282.         self.data.extend(items)
  283.  
  284.     def pop(self):
  285.         return self.data.pop(0)
  286.  
  287.     def __len__(self):
  288.         return len(self.data)
  289.  
  290.     def __contains__(self, item):
  291.         return item in self.data
  292.  
  293.  
  294. class PriorityQueue(Queue):
  295.     """Редица во која прво се враќа минималниот (или максималниот) елемент
  296.    (како што е определено со f и order). Оваа структура се користи кај
  297.    информирано пребарување"""
  298.     """"""
  299.  
  300.     def __init__(self, order=min, f=lambda x: x):
  301.         """
  302.        :param order: функција за подредување, ако order е min, се враќа елементот
  303.                      со минимална f(x); ако order е max, тогаш се враќа елементот
  304.                      со максимална f(x).
  305.        :param f: функција f(x)
  306.        """
  307.         assert order in [min, max]
  308.         self.data = []
  309.         self.order = order
  310.         self.f = f
  311.  
  312.     def append(self, item):
  313.         bisect.insort_right(self.data, (self.f(item), item))
  314.  
  315.     def extend(self, items):
  316.         for item in items:
  317.             bisect.insort_right(self.data, (self.f(item), item))
  318.  
  319.     def pop(self):
  320.         if self.order == min:
  321.             return self.data.pop(0)[1]
  322.         return self.data.pop()[1]
  323.  
  324.     def __len__(self):
  325.         return len(self.data)
  326.  
  327.     def __contains__(self, item):
  328.         return any(item == pair[1] for pair in self.data)
  329.  
  330.     def __getitem__(self, key):
  331.         for _, item in self.data:
  332.             if item == key:
  333.                 return item
  334.  
  335.     def __delitem__(self, key):
  336.         for i, (value, item) in enumerate(self.data):
  337.             if item == key:
  338.                 self.data.pop(i)
  339.  
  340.  
  341. """
  342. Информирано пребарување во рамки на граф
  343. """
  344.  
  345.  
  346. def memoize(fn, slot=None):
  347.     """ Запамети ја пресметаната вредност за која била листа од
  348.    аргументи. Ако е специфициран slot, зачувај го резултатот во
  349.    тој slot на првиот аргумент. Ако slot е None, зачувај ги
  350.    резултатите во речник.
  351.  
  352.    :param fn: зададена функција
  353.    :param slot: име на атрибут во кој се чуваат резултатите од функцијата
  354.    :return: функција со модификација за зачувување на резултатите
  355.    """
  356.     if slot:
  357.         def memoized_fn(obj, *args):
  358.             if hasattr(obj, slot):
  359.                 return getattr(obj, slot)
  360.             else:
  361.                 val = fn(obj, *args)
  362.                 setattr(obj, slot, val)
  363.                 return val
  364.     else:
  365.         def memoized_fn(*args):
  366.             if args not in memoized_fn.cache:
  367.                 memoized_fn.cache[args] = fn(*args)
  368.             return memoized_fn.cache[args]
  369.  
  370.         memoized_fn.cache = {}
  371.     return memoized_fn
  372.  
  373.  
  374. def best_first_graph_search(problem, f):
  375.     """Пребарувај низ следбениците на даден проблем за да најдеш цел. Користи
  376.     функција за евалуација за да се одлучи кој е сосед најмногу ветува и
  377.     потоа да се истражи. Ако до дадена состојба стигнат два пата, употреби
  378.     го најдобриот пат.
  379.  
  380.    :param problem: даден проблем
  381.    :param f: дадена функција за евристика
  382.    :return: Node or None
  383.    """
  384.     f = memoize(f, 'f')
  385.     node = Node(problem.initial)
  386.     if problem.goal_test(node.state):
  387.         return node
  388.     frontier = PriorityQueue(min, f)
  389.     frontier.append(node)
  390.     explored = set()
  391.     while frontier:
  392.         node = frontier.pop()
  393.         if problem.goal_test(node.state):
  394.             return node
  395.         explored.add(node.state)
  396.         for child in node.expand(problem):
  397.             if child.state not in explored and child not in frontier:
  398.                 frontier.append(child)
  399.             elif child in frontier:
  400.                 incumbent = frontier[child]
  401.                 if f(child) < f(incumbent):
  402.                     del frontier[incumbent]
  403.                     frontier.append(child)
  404.     return None
  405.  
  406.  
  407. def greedy_best_first_graph_search(problem, h=None):
  408.     """ Greedy best-first пребарување се остварува ако се специфицира дека f(n) = h(n).
  409.  
  410.    :param problem: даден проблем
  411.    :param h: дадена функција за евристика
  412.    :return: Node or None
  413.    """
  414.     h = memoize(h or problem.h, 'h')
  415.     return best_first_graph_search(problem, h)
  416.  
  417.  
  418. def astar_search(problem, h=None):
  419.     """ A* пребарување е best-first graph пребарување каде f(n) = g(n) + h(n).
  420.  
  421.    :param problem: даден проблем
  422.    :param h: дадена функција за евристика
  423.    :return: Node or None
  424.    """
  425.     h = memoize(h or problem.h, 'h')
  426.     return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
  427.  
  428.  
  429. def recursive_best_first_search(problem, h=None):
  430.     """Recursive best first search - ја ограничува рекурзијата
  431.     преку следење на f-вредноста на најдобриот алтернативен пат
  432.     од било кој јазел предок (еден чекор гледање нанапред).
  433.  
  434.    :param problem: даден проблем
  435.    :param h: дадена функција за евристика
  436.    :return: Node or None
  437.    """
  438.     h = memoize(h or problem.h, 'h')
  439.  
  440.     def RBFS(problem, node, flimit):
  441.         if problem.goal_test(node.state):
  442.             return node, 0  # (втората вредност е неважна)
  443.         successors = node.expand(problem)
  444.         if len(successors) == 0:
  445.             return None, infinity
  446.         for s in successors:
  447.             s.f = max(s.path_cost + h(s), node.f)
  448.         while True:
  449.             # Подреди ги според најниската f вредност
  450.             successors.sort(key=lambda x: x.f)
  451.             best = successors[0]
  452.             if best.f > flimit:
  453.                 return None, best.f
  454.             if len(successors) > 1:
  455.                 alternative = successors[1].f
  456.             else:
  457.                 alternative = infinity
  458.             result, best.f = RBFS(problem, best, min(flimit, alternative))
  459.             if result is not None:
  460.                 return result, best.f
  461.  
  462.     node = Node(problem.initial)
  463.     node.f = h(node)
  464.     result, bestf = RBFS(problem, node, infinity)
  465.     return result
  466.  
  467.  
  468. class Obstacles(Problem):
  469.  
  470.     def __init__(self, initial, goal=None):
  471.         self.initial = initial
  472.         self.goal = goal
  473.  
  474.     def move1(self, state):
  475.         p1 = state[1]
  476.         nasoka = state[1][2]
  477.         kocka1 = p1[0]
  478.         kocka2 = p1[1]
  479.  
  480.         if kocka1[1] == 1:
  481.             return (3, 2), (3, 3), 1
  482.         elif kocka1[1] == 5:
  483.             return (3, 4), (3, 5), -1
  484.         else:
  485.             return (kocka1[0], kocka1[1] + nasoka), (kocka2[0], kocka2[1] + nasoka), nasoka
  486.  
  487.     def move2(self, state):
  488.         p2 = state[2]
  489.         nasoka = state[2][4]
  490.         kocka1 = p2[0]
  491.         kocka2 = p2[1]
  492.         kocka3 = p2[2]
  493.         kocka4 = p2[3]
  494.  
  495.         if kocka1[0] == 6:
  496.             return (7, 4), (7, 5), (8, 4), (8, 5), 1
  497.         elif kocka1[0] == 10:
  498.             return (9, 2), (9, 3), (10, 2), (10, 3), -1
  499.         else:
  500.             return (kocka1[0] + nasoka, kocka1[1] - nasoka), (kocka2[0] + nasoka, kocka2[1] - nasoka), \
  501.                    (kocka3[0] + nasoka, kocka3[1] - nasoka), (kocka4[0] + nasoka, kocka4[1] - nasoka), nasoka
  502.  
  503.     def move3(self, state):
  504.         p3 = state[3]
  505.         nasoka = p3[2]
  506.         kocka1 = p3[0]
  507.         kocka2 = p3[1]
  508.  
  509.         if kocka1[0] == 6:
  510.             return (7, kocka1[1]), (8, kocka2[1]), 1
  511.         elif kocka1[0] == 10:
  512.             return (9, 9), (10, 9), -1
  513.         else:
  514.             return (kocka1[0] + nasoka, kocka1[1]), (kocka2[0] + nasoka, kocka2[1]), nasoka
  515.  
  516.     def check(self, state):
  517.         person = list(state[0])
  518.         kocki = list(state[1])[0:2] + list(state[2])[0:4] + list(state[3])[0:2]
  519.  
  520.         for (x, y) in kocki:
  521.             if person[0] == x and person[1] == y:
  522.                 return False
  523.  
  524.         if person[0] < 1 or person[0] > 11:
  525.             return False
  526.         if person[1] < 1 or person[1] > 11:
  527.             return False
  528.         if person[0] < 6 < person[1]:
  529.             return False
  530.  
  531.         return True
  532.  
  533.     def successor(self, state):
  534.         succs = {}
  535.         person = state[0]
  536.         p1 = self.move1(state)
  537.         p2 = self.move2(state)
  538.         p3 = self.move3(state)
  539.  
  540.         new = (person[0], person[1] - 1), p1, p2, p3
  541.         if self.check(new):
  542.             succs["Levo"] = new
  543.  
  544.         new = (person[0] - 1, person[1]), p1, p2, p3
  545.         if self.check(new):
  546.             succs["Gore"] = new
  547.  
  548.         new = (person[0], person[1] + 1), p1, p2, p3
  549.         if self.check(new):
  550.             succs["Desno"] = new
  551.  
  552.         new = (person[0] + 1, person[1]), p1, p2, p3
  553.         if self.check(new):
  554.             succs["Dolu"] = new
  555.  
  556.         return succs
  557.  
  558.     def actions(self, state):
  559.         """Given a state, return a list of all actions possible from that state"""
  560.         return self.successor(state).keys()
  561.  
  562.     def h(self, node):
  563.  
  564.         initialX, initialY = node.state[0]
  565.         goalX, goalY = self.goal
  566.         return math.fabs(initialX - goalX) + math.fabs(initialY - goalY)
  567.  
  568.     def result(self, state, action):
  569.         """Given a state and action, return the resulting state"""
  570.         return self.successor(state)[action]
  571.  
  572.     def goal_test(self, state):
  573.         """Return True if the state is a goal. The default method compares the
  574.       state to self.goal, as specified in the constructor. Implement this
  575.       method if checking against a single self.goal is not enough."""
  576.         person = state[0]
  577.         return person[0] == self.goal[0] and person[1] == self.goal[1]
  578.  
  579.     def path_cost(self, c, state1, action, state2):
  580.         """Return the cost of a solution path that arrives at state2 from
  581.       state1 via action, assuming cost c to get up to state1. If the problem
  582.       is such that the path doesn't matter, this function will only look at
  583.       state2.  If the path does matter, it will consider c and maybe state1
  584.       and action. The default method costs 1 for every step in the path."""
  585.         return c + 1
  586.  
  587.     def value(self):
  588.         """For optimization problems, each state has a value.  Hill-climbing
  589.       and related algorithms try to maximize this value."""
  590.         raise NotImplementedError
  591.  
  592.  
  593. initial = (CoveceRedica, CoveceKolona), ((3, 3), (3, 4), -1), ((8, 3), (8, 4), (9, 3), (9, 4), -1), ((8, 9), (9, 9), 1)
  594. goal = KukaRedica, KukaKolona
  595.  
  596. problem = Obstacles(initial, goal)
  597.  
  598. # answer = breadth_first_graph_search(problem)
  599. # print(answer.solution())
  600.  
  601. # Example1 = ((0, 3), (2, 2, -1), (7, 2, 1), (7, 8, 1))  # Pochetnata sostojba dadena na code
  602. # Problem1 = Obstacles(Example1)
  603. # # Test1 = breadth_first_graph_search(Problem1)  # Test za neinformirano prebaruvanje koristejki BFS
  604. # # print(Test1.solution())  # Lista od akcii
  605. # # print(Test1.solve())  # Lista od sostojbi
  606. Test2 = astar_search(problem)  # Test za informirano prebaruvanje so hevristika koristejki A* algoritmot
  607. print(Test2.solution())  # Lista od akcii
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement