Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- import bisect
- class Problem:
- def __init__(self, initial, goal=None):
- self.initial = initial
- self.goal = goal
- def successor(self, state):
- """За дадена состојба, врати речник од парови {акција : состојба}
- достапни од оваа состојба. Ако има многу следбеници, употребете
- итератор кој би ги генерирал следбениците еден по еден, наместо да
- ги генерирате сите одеднаш.
- :param state: дадена состојба
- :return: речник од парови {акција : состојба} достапни од оваа
- состојба
- :rtype: dict
- """
- raise NotImplementedError
- def actions(self, state):
- """За дадена состојба state, врати листа од сите акции што може да
- се применат над таа состојба
- :param state: дадена состојба
- :return: листа на акции
- :rtype: list
- """
- return self.successor(state).keys()
- def result(self, state, action):
- """За дадена состојба state и акција action, врати ја состојбата
- што се добива со примена на акцијата над состојбата
- :param state: дадена состојба
- :param action: дадена акција
- :return: резултантна состојба
- """
- possible = self.successor(state)
- return possible[action]
- def goal_test(self, state):
- """Врати True ако state е целна состојба. Даденава имплементација
- на методот директно ја споредува state со self.goal, како што е
- специфицирана во конструкторот. Имплементирајте го овој метод ако
- проверката со една целна состојба self.goal не е доволна.
- :param state: дадена состојба
- :return: дали дадената состојба е целна состојба
- :rtype: bool
- """
- return state == self.goal
- def path_cost(self, c, state1, action, state2):
- """Врати ја цената на решавачкиот пат кој пристигнува во состојбата
- state2 од состојбата state1 преку акцијата action, претпоставувајќи
- дека цената на патот до состојбата state1 е c. Ако проблемот е таков
- што патот не е важен, оваа функција ќе ја разгледува само состојбата
- state2. Ако патот е важен, ќе ја разгледува цената c и можеби и
- state1 и action. Даденава имплементација му доделува цена 1 на секој
- чекор од патот.
- :param c: цена на патот до состојбата state1
- :param state1: дадена моментална состојба
- :param action: акција која треба да се изврши
- :param state2: состојба во која треба да се стигне
- :return: цена на патот по извршување на акцијата
- :rtype: float
- """
- return c + 1
- def value(self):
- """За проблеми на оптимизација, секоја состојба си има вредност.
- Hill-climbing и сличните алгоритми се обидуваат да ја максимизираат
- оваа вредност.
- :return: вредност на состојба
- :rtype: float
- """
- raise NotImplementedError
- """
- Дефинирање на класата за структурата на јазел од пребарување.
- Класата Node не се наследува
- """
- class Node:
- def __init__(self, state, parent=None, action=None, path_cost=0):
- """Креирај јазол од пребарувачкото дрво, добиен од parent со примена
- на акцијата action
- :param state: моментална состојба (current state)
- :param parent: родителска состојба (parent state)
- :param action: акција (action)
- :param path_cost: цена на патот (path cost)
- """
- self.state = state
- self.parent = parent
- self.action = action
- self.path_cost = path_cost
- self.depth = 0 # search depth
- if parent:
- self.depth = parent.depth + 1
- def __repr__(self):
- return "<Node %s>" % (self.state,)
- def __lt__(self, node):
- return self.state < node.state
- def expand(self, problem):
- """Излистај ги јазлите достапни во еден чекор од овој јазол.
- :param problem: даден проблем
- :return: листа на достапни јазли во еден чекор
- :rtype: list(Node)
- """
- return [self.child_node(problem, action)
- for action in problem.actions(self.state)]
- def child_node(self, problem, action):
- """Дете јазел
- :param problem: даден проблем
- :param action: дадена акција
- :return: достапен јазел според дадената акција
- :rtype: Node
- """
- next_state = problem.result(self.state, action)
- return Node(next_state, self, action,
- problem.path_cost(self.path_cost, self.state,
- action, next_state))
- def solution(self):
- """Врати ја секвенцата од акции за да се стигне од коренот до овој јазол.
- :return: секвенцата од акции
- :rtype: list
- """
- return [node.action for node in self.path()[1:]]
- def solve(self):
- """Врати ја секвенцата од состојби за да се стигне од коренот до овој јазол.
- :return: листа од состојби
- :rtype: list
- """
- return [node.state for node in self.path()[0:]]
- def path(self):
- """Врати ја листата од јазли што го формираат патот од коренот до овој јазол.
- :return: листа од јазли од патот
- :rtype: list(Node)
- """
- x, result = self, []
- while x:
- result.append(x)
- x = x.parent
- result.reverse()
- return result
- """Сакаме редицата од јазли кај breadth_first_search или
- astar_search да не содржи состојби - дупликати, па јазлите што
- содржат иста состојба ги третираме како исти. [Проблем: ова може
- да не биде пожелно во други ситуации.]"""
- def __eq__(self, other):
- return isinstance(other, Node) and self.state == other.state
- def __hash__(self):
- return hash(self.state)
- """
- Дефинирање на помошни структури за чување на листата на генерирани, но непроверени јазли
- """
- class Queue:
- """Queue е апстрактна класа / интерфејс. Постојат 3 типа:
- Stack(): Last In First Out Queue (стек).
- FIFOQueue(): First In First Out Queue (редица).
- PriorityQueue(order, f): Queue во сортиран редослед (подразбирливо,од најмалиот кон
- најголемиот јазол).
- """
- def __init__(self):
- raise NotImplementedError
- def append(self, item):
- """Додади го елементот item во редицата
- :param item: даден елемент
- :return: None
- """
- raise NotImplementedError
- def extend(self, items):
- """Додади ги елементите items во редицата
- :param items: дадени елементи
- :return: None
- """
- raise NotImplementedError
- def pop(self):
- """Врати го првиот елемент од редицата
- :return: прв елемент
- """
- raise NotImplementedError
- def __len__(self):
- """Врати го бројот на елементи во редицата
- :return: број на елементи во редицата
- :rtype: int
- """
- raise NotImplementedError
- def __contains__(self, item):
- """Проверка дали редицата го содржи елементот item
- :param item: даден елемент
- :return: дали queue го содржи item
- :rtype: bool
- """
- raise NotImplementedError
- class Stack(Queue):
- """Last-In-First-Out Queue."""
- def __init__(self):
- self.data = []
- def append(self, item):
- self.data.append(item)
- def extend(self, items):
- self.data.extend(items)
- def pop(self):
- return self.data.pop()
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return item in self.data
- class FIFOQueue(Queue):
- """First-In-First-Out Queue."""
- def __init__(self):
- self.data = []
- def append(self, item):
- self.data.append(item)
- def extend(self, items):
- self.data.extend(items)
- def pop(self):
- return self.data.pop(0)
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return item in self.data
- class PriorityQueue(Queue):
- """Редица во која прво се враќа минималниот (или максималниот) елемент
- (како што е определено со f и order). Оваа структура се користи кај
- информирано пребарување"""
- """"""
- def __init__(self, order=min, f=lambda x: x):
- """
- :param order: функција за подредување, ако order е min, се враќа елементот
- со минимална f(x); ако order е max, тогаш се враќа елементот
- со максимална f(x).
- :param f: функција f(x)
- """
- assert order in [min, max]
- self.data = []
- self.order = order
- self.f = f
- def append(self, item):
- bisect.insort_right(self.data, (self.f(item), item))
- def extend(self, items):
- for item in items:
- bisect.insort_right(self.data, (self.f(item), item))
- def pop(self):
- if self.order == min:
- return self.data.pop(0)[1]
- return self.data.pop()[1]
- def __len__(self):
- return len(self.data)
- def __contains__(self, item):
- return any(item == pair[1] for pair in self.data)
- def __getitem__(self, key):
- for _, item in self.data:
- if item == key:
- return item
- def __delitem__(self, key):
- for i, (value, item) in enumerate(self.data):
- if item == key:
- self.data.pop(i)
- def tree_search(problem, fringe):
- """ Пребарувај низ следбениците на даден проблем за да најдеш цел.
- :param problem: даден проблем
- :param fringe: празна редица (queue)
- :return: Node
- """
- fringe.append(Node(problem.initial))
- while fringe:
- node = fringe.pop()
- print(node.state)
- if problem.goal_test(node.state):
- return node
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_tree_search(problem):
- """Експандирај го прво најплиткиот јазол во пребарувачкото дрво.
- :param problem: даден проблем
- :return: Node
- """
- return tree_search(problem, FIFOQueue())
- def depth_first_tree_search(problem):
- """Експандирај го прво најдлабокиот јазол во пребарувачкото дрво.
- :param problem:даден проблем
- :return: Node
- """
- return tree_search(problem, Stack())
- """
- Неинформирано пребарување во рамки на граф
- Основната разлика е во тоа што овде не дозволуваме јамки,
- т.е. повторување на состојби
- """
- def graph_search(problem, fringe):
- """Пребарувај низ следбениците на даден проблем за да најдеш цел.
- Ако до дадена состојба стигнат два пата, употреби го најдобриот пат.
- :param problem: даден проблем
- :param fringe: празна редица (queue)
- :return: Node
- """
- closed = set()
- fringe.append(Node(problem.initial))
- while fringe:
- node = fringe.pop()
- if problem.goal_test(node.state):
- return node
- if node.state not in closed:
- closed.add(node.state)
- fringe.extend(node.expand(problem))
- return None
- def breadth_first_graph_search(problem):
- """Експандирај го прво најплиткиот јазол во пребарувачкиот граф.
- :param problem: даден проблем
- :return: Node
- """
- return graph_search(problem, FIFOQueue())
- def depth_first_graph_search(problem):
- """Експандирај го прво најдлабокиот јазол во пребарувачкиот граф.
- :param problem: даден проблем
- :return: Node
- """
- return graph_search(problem, Stack())
- def depth_limited_search(problem, limit=50):
- def recursive_dls(node, problem, limit):
- """Помошна функција за depth limited"""
- cutoff_occurred = False
- if problem.goal_test(node.state):
- return node
- elif node.depth == limit:
- return 'cutoff'
- else:
- for successor in node.expand(problem):
- result = recursive_dls(successor, problem, limit)
- if result == 'cutoff':
- cutoff_occurred = True
- elif result is not None:
- return result
- if cutoff_occurred:
- return 'cutoff'
- return None
- return recursive_dls(Node(problem.initial), problem, limit)
- def iterative_deepening_search(problem):
- for depth in range(sys.maxsize):
- result = depth_limited_search(problem, depth)
- if result is not 'cutoff':
- return result
- def uniform_cost_search(problem):
- """Експандирај го прво јазолот со најниска цена во пребарувачкиот граф."""
- return graph_search(problem, PriorityQueue(lambda a, b : a.path_cost < b.path_cost))
- class WJ(Problem):
- def __init__(self, capacities=(5, 2), initial=(5, 0), goal=(0, 1)):
- super().__init__(initial, goal)
- self.capacities = capacities
- def goal_test(self, state):
- """Враќа True ако состојбата state е целна состојба.
- :param state: дадена состојба
- :type state: tuple
- :return: дали состојбата е целна состојба
- :rtype: bool
- """
- g = self.goal
- return (state[0] == g[0] or g[0] == '*') and \
- (state[1] == g[1] or g[1] == '*')
- def successor(self, j):
- """Враќа речник од следбеници на состојбата
- :param j: дадена состојба
- :type j: tuple
- :return: речник од следни состојби
- :rtype: dict
- """
- successors = dict()
- j0, j1 = j
- (C0, C1) = self.capacities
- if j0 > 0:
- j_new = 0, j1
- successors['isprazni go sadot J0'] = j_new
- if j1 > 0:
- j_new = j0, 0
- successors['isprazni go sadot J1'] = j_new
- if j1 < C1 and j0 > 0:
- delta = min(j0, C1 - j1)
- j_new = j0 - delta, j1 + delta
- successors['preturi od sadot J0 vo sadot J1'] = j_new
- if j0 < C0 and j1 > 0:
- delta = min(j1, C0 - j0)
- j_new = j0 + delta, j1 - delta
- successors['preturi od sadot J1 vo sadot J0'] = j_new
- return successors
- def actions(self, state):
- return self.successor(state).keys()
- def result(self, state, action):
- possible = self.successor(state)
- return possible[action]
- chovece_redica = int (input())
- chovece_kolona = int(input())
- kukja_redica = int(input())
- kukja_kolona = int(input())
- precka1 = ((2, 2), (2, 3)), -1
- precka2 = ((7, 2), (7, 3), (8, 2), (8, 3)), 1
- precka3 = ((7, 8), (8, 8)), 1
- def pomesti_precka1(precka):
- lista = precka[0]
- nasoka = precka[1]
- if lista[0][1] == 0:
- nasoka = 1
- if lista[1][1] == 5:
- nasoka = -1
- kocka_levo = lista[0][0], lista[0][1] + nasoka
- kocka_desno = lista[1][0], lista[1][1] + nasoka
- return (kocka_levo, kocka_desno), nasoka
- def pomesti_precka2(precka):
- lista = precka[0]
- nasoka = precka[1]
- gorno_levo = lista[0]
- gorno_desno = lista[1]
- dolno_levo = lista[2]
- dolno_desno = lista[3]
- if gorno_desno[0] == 5:
- nasoka = -1
- if dolno_levo[0] == 10:
- nasoka = 1
- gorno_levo = gorno_levo[0] - nasoka, gorno_levo[1] + nasoka
- gorno_desno = gorno_desno[0] - nasoka, gorno_levo[1] + nasoka
- dolno_levo = dolno_levo[0] - nasoka, dolno_levo[1] + nasoka
- dolno_desno = dolno_desno[0] - nasoka, dolno_desno[1] + nasoka
- return (gorno_levo, gorno_desno, dolno_levo, dolno_desno), nasoka
- def pomesti_precka3(precka):
- lista = precka[0]
- nasoka = precka[1]
- gorno = lista[0]
- dolno = lista[1]
- if gorno[0] == 5:
- nasoka = 1
- if dolno[0] == 10:
- nasoka = -1
- gorno = gorno[0] + nasoka, gorno[1]
- dolno = dolno[0] + nasoka, dolno[1]
- return (gorno, dolno), nasoka
- def validpos(xy, precka1, precka2, precka3):
- if xy in precka1[0]:
- return False
- if xy in precka2[0]:
- return False
- if xy in precka3[0]:
- return False
- return True
- class Istrazuvac(Problem):
- def __init__(self, initial, goal):
- Problem.__init__(self, initial, goal)
- self.initial = initial
- self.goal = goal
- def successor(self, state):
- successors = dict()
- x, y = state[0]
- p1 = pomesti_precka1(precka1)
- p2 = pomesti_precka2(precka2)
- p3 = pomesti_precka3(precka3)
- if x < 5 and y < 5:
- newstate = (x, y+1), p1, p2, p3
- if validpos(newstate[0], p1, p2, p3):
- successors["Desno"] = newstate
- if x > 5 and y < 10:
- newstate = (x, y+1), p1, p2, p3
- if validpos(newstate[0], p1, p2, p3):
- successors["Desno"] = newstate
- if y >= 0:
- newstate = (x, y-1), p1, p2, p3
- if validpos(newstate[0], p1, p2, p3):
- successors["Levo"] = newstate
- if y < 6 and x >= 0:
- newstate = (x-1, y), p1, p2, p3
- if validpos(newstate[0], p1, p2, p3):
- successors["Gore"] = newstate
- if y > 5 and x > 5:
- newstate = (x-1, y), p1, p2, p3
- if validpos(newstate[0], p1, p2, p3):
- successors["Gore"] = newstate
- if x < 10:
- newstate = (x+1, y), p1, p2, p3
- if validpos(newstate[0], p1, p2, p3):
- successors["Dolu"] = newstate
- return successors
- def actions(self, state):
- return self.successor(state).keys()
- def result(self, state, action):
- possible = self.successor(state)
- return possible[action]
- def goal_test(self, state):
- return state[0] == self.goal
- def value(self):
- pass
- def result(self, state, action):
- possible = self.successor(state)
- return possible[action]
- def path_cost(self, c, state1, action, state2):
- pass
- goal = kukja_redica, kukja_kolona
- initial = (chovece_redica, chovece_kolona), precka1, precka2, precka3
- istrazuvac = Istrazuvac(initial, goal)
- answer = breadth_first_graph_search(istrazuvac)
- print(answer.solution())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement