API tools faq
paste
Advertisement
stefan97

Untitled

stefan97
Jan 25th, 2020
92
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 18.69 KB | None | 0 0
raw download clone embed print report
  1. # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
  2.  
  3. # ______________________________________________________________________________________________
  4. # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
  5.  
  6. import sys
  7. import bisect
  8.  
  9. infinity = float('inf') # sistemski definirana vrednost za beskonecnost
  10.  
  11.  
  12. # ______________________________________________________________________________________________
  13. # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
  14.  
  15. class Queue:
  16. """Queue is an abstract class/interface. There are three types:
  17. Stack(): A Last In First Out Queue.
  18. FIFOQueue(): A First In First Out Queue.
  19. PriorityQueue(order, f): Queue in sorted order (default min-first).
  20. Each type supports the following methods and functions:
  21. q.append(item) -- add an item to the queue
  22. q.extend(items) -- equivalent to: for item in items: q.append(item)
  23. q.pop() -- return the top item from the queue
  24. len(q) -- number of items in q (also q.__len())
  25. item in q -- does q contain item?
  26. Note that isinstance(Stack(), Queue) is false, because we implement stacks
  27. as lists. If Python ever gets interfaces, Queue will be an interface."""
  28.  
  29. def __init__(self):
  30. raise NotImplementedError
  31.  
  32. def extend(self, items):
  33. for item in items:
  34. self.append(item)
  35.  
  36.  
  37. def Stack():
  38. """A Last-In-First-Out Queue."""
  39. return []
  40.  
  41.  
  42. class FIFOQueue(Queue):
  43. """A First-In-First-Out Queue."""
  44.  
  45. def __init__(self):
  46. self.A = []
  47. self.start = 0
  48.  
  49. def append(self, item):
  50. self.A.append(item)
  51.  
  52. def __len__(self):
  53. return len(self.A) - self.start
  54.  
  55. def extend(self, items):
  56. self.A.extend(items)
  57.  
  58. def pop(self):
  59. e = self.A[self.start]
  60. self.start += 1
  61. if self.start > 5 and self.start > len(self.A) / 2:
  62. self.A = self.A[self.start:]
  63. self.start = 0
  64. return e
  65.  
  66. def __contains__(self, item):
  67. return item in self.A[self.start:]
  68.  
  69.  
  70. class PriorityQueue(Queue):
  71. """A queue in which the minimum (or maximum) element (as determined by f and
  72. order) is returned first. If order is min, the item with minimum f(x) is
  73. returned first; if order is max, then it is the item with maximum f(x).
  74. Also supports dict-like lookup. This structure will be most useful in informed searches"""
  75.  
  76. def __init__(self, order=min, f=lambda x: x):
  77. self.A = []
  78. self.order = order
  79. self.f = f
  80.  
  81. def append(self, item):
  82. bisect.insort(self.A, (self.f(item), item))
  83.  
  84. def __len__(self):
  85. return len(self.A)
  86.  
  87. def pop(self):
  88. if self.order == min:
  89. return self.A.pop(0)[1]
  90. else:
  91. return self.A.pop()[1]
  92.  
  93. def __contains__(self, item):
  94. return any(item == pair[1] for pair in self.A)
  95.  
  96. def __getitem__(self, key):
  97. for _, item in self.A:
  98. if item == key:
  99. return item
  100.  
  101. def __delitem__(self, key):
  102. for i, (value, item) in enumerate(self.A):
  103. if item == key:
  104. self.A.pop(i)
  105.  
  106.  
  107. # ______________________________________________________________________________________________
  108. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  109. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  110. # na sekoj eden problem sto sakame da go resime
  111.  
  112.  
  113. class Problem:
  114. """The abstract class for a formal problem. You should subclass this and
  115. implement the method successor, and possibly __init__, goal_test, and
  116. path_cost. Then you will create instances of your subclass and solve them
  117. with the various search functions."""
  118.  
  119. def __init__(self, initial, goal=None):
  120. """The constructor specifies the initial state, and possibly a goal
  121. state, if there is a unique goal. Your subclass's constructor can add
  122. other arguments."""
  123. self.initial = initial
  124. self.goal = goal
  125.  
  126. def successor(self, state):
  127. """Given a state, return a dictionary of {action : state} pairs reachable
  128. from this state. If there are many successors, consider an iterator
  129. that yields the successors one at a time, rather than building them
  130. all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  131. raise NotImplementedError
  132.  
  133. def actions(self, state):
  134. """Given a state, return a list of all actions possible from that state"""
  135. raise NotImplementedError
  136.  
  137. def result(self, state, action):
  138. """Given a state and action, return the resulting state"""
  139. raise NotImplementedError
  140.  
  141. def goal_test(self, state):
  142. """Return True if the state is a goal. The default method compares the
  143. state to self.goal, as specified in the constructor. Implement this
  144. method if checking against a single self.goal is not enough."""
  145. return state == self.goal
  146.  
  147. def path_cost(self, c, state1, action, state2):
  148. """Return the cost of a solution path that arrives at state2 from
  149. state1 via action, assuming cost c to get up to state1. If the problem
  150. is such that the path doesn't matter, this function will only look at
  151. state2. If the path does matter, it will consider c and maybe state1
  152. and action. The default method costs 1 for every step in the path."""
  153. return c + 1
  154.  
  155. def value(self):
  156. """For optimization problems, each state has a value. Hill-climbing
  157. and related algorithms try to maximize this value."""
  158. raise NotImplementedError
  159.  
  160.  
  161. # ______________________________________________________________________________
  162. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  163. # Klasata Node ne se nasleduva
  164.  
  165. class Node:
  166. """A node in a search tree. Contains a pointer to the parent (the node
  167. that this is a successor of) and to the actual state for this node. Note
  168. that if a state is arrived at by two paths, then there are two nodes with
  169. the same state. Also includes the action that got us to this state, and
  170. the total path_cost (also known as g) to reach the node. Other functions
  171. may add an f and h value; see best_first_graph_search and astar_search for
  172. an explanation of how the f and h values are handled. You will not need to
  173. subclass this class."""
  174.  
  175. def __init__(self, state, parent=None, action=None, path_cost=0):
  176. "Create a search tree Node, derived from a parent by an action."
  177. self.state = state
  178. self.parent = parent
  179. self.action = action
  180. self.path_cost = path_cost
  181. self.depth = 0
  182. if parent:
  183. self.depth = parent.depth + 1
  184.  
  185. def __repr__(self):
  186. return "<Node %s>" % (self.state,)
  187.  
  188. def __lt__(self, node):
  189. return self.state < node.state
  190.  
  191. def expand(self, problem):
  192. "List the nodes reachable in one step from this node."
  193. return [self.child_node(problem, action)
  194. for action in problem.actions(self.state)]
  195.  
  196. def child_node(self, problem, action):
  197. "Return a child node from this node"
  198. next = problem.result(self.state, action)
  199. return Node(next, self, action,
  200. problem.path_cost(self.path_cost, self.state,
  201. action, next))
  202.  
  203. def solution(self):
  204. "Return the sequence of actions to go from the root to this node."
  205. return [node.action for node in self.path()[1:]]
  206.  
  207. def solve(self):
  208. "Return the sequence of states to go from the root to this node."
  209. return [node.state for node in self.path()[0:]]
  210.  
  211. def path(self):
  212. "Return a list of nodes forming the path from the root to this node."
  213. x, result = self, []
  214. while x:
  215. result.append(x)
  216. x = x.parent
  217. return list(reversed(result))
  218.  
  219. # We want for a queue of nodes in breadth_first_search or
  220. # astar_search to have no duplicated states, so we treat nodes
  221. # with the same state as equal. [Problem: this may not be what you
  222. # want in other contexts.]
  223.  
  224. def __eq__(self, other):
  225. return isinstance(other, Node) and self.state == other.state
  226.  
  227. def __hash__(self):
  228. return hash(self.state)
  229.  
  230.  
  231. # ________________________________________________________________________________________________________
  232. #Neinformirano prebaruvanje vo ramki na drvo
  233. #Vo ramki na drvoto ne razresuvame jamki
  234.  
  235. def tree_search(problem, fringe):
  236. """Search through the successors of a problem to find a goal.
  237. The argument fringe should be an empty queue."""
  238. fringe.append(Node(problem.initial))
  239. while fringe:
  240. node = fringe.pop()
  241. print (node.state)
  242. if problem.goal_test(node.state):
  243. return node
  244. fringe.extend(node.expand(problem))
  245. return None
  246.  
  247.  
  248. def breadth_first_tree_search(problem):
  249. "Search the shallowest nodes in the search tree first."
  250. return tree_search(problem, FIFOQueue())
  251.  
  252.  
  253. def depth_first_tree_search(problem):
  254. "Search the deepest nodes in the search tree first."
  255. return tree_search(problem, Stack())
  256.  
  257.  
  258. # ________________________________________________________________________________________________________
  259. #Neinformirano prebaruvanje vo ramki na graf
  260. #Osnovnata razlika e vo toa sto ovde ne dozvoluvame jamki t.e. povtoruvanje na sostojbi
  261.  
  262. def graph_search(problem, fringe):
  263. """Search through the successors of a problem to find a goal.
  264. The argument fringe should be an empty queue.
  265. If two paths reach a state, only use the best one."""
  266. closed = {}
  267. fringe.append(Node(problem.initial))
  268. while fringe:
  269. node = fringe.pop()
  270. if problem.goal_test(node.state):
  271. return node
  272. if node.state not in closed:
  273. closed[node.state] = True
  274. fringe.extend(node.expand(problem))
  275. return None
  276.  
  277.  
  278. def breadth_first_graph_search(problem):
  279. "Search the shallowest nodes in the search tree first."
  280. return graph_search(problem, FIFOQueue())
  281.  
  282.  
  283. def depth_first_graph_search(problem):
  284. "Search the deepest nodes in the search tree first."
  285. return graph_search(problem, Stack())
  286.  
  287.  
  288. def uniform_cost_search(problem):
  289. "Search the nodes in the search tree with lowest cost first."
  290. return graph_search(problem, PriorityQueue(lambda a, b: a.path_cost < b.path_cost))
  291.  
  292.  
  293. def depth_limited_search(problem, limit=50):
  294. "depth first search with limited depth"
  295.  
  296. def recursive_dls(node, problem, limit):
  297. "helper function for depth limited"
  298. cutoff_occurred = False
  299. if problem.goal_test(node.state):
  300. return node
  301. elif node.depth == limit:
  302. return 'cutoff'
  303. else:
  304. for successor in node.expand(problem):
  305. result = recursive_dls(successor, problem, limit)
  306. if result == 'cutoff':
  307. cutoff_occurred = True
  308. elif result != None:
  309. return result
  310. if cutoff_occurred:
  311. return 'cutoff'
  312. else:
  313. return None
  314.  
  315. # Body of depth_limited_search:
  316. return recursive_dls(Node(problem.initial), problem, limit)
  317.  
  318.  
  319. def iterative_deepening_search(problem):
  320.  
  321. for depth in xrange(sys.maxint):
  322. result = depth_limited_search(problem, depth)
  323. if result is not 'cutoff':
  324. return result
  325.  
  326.  
  327.  
  328. # _________________________________________________________________________________________________________
  329. #PRIMER 1 : PROBLEM SO DVA SADA SO VODA
  330. #OPIS: Dadeni se dva sada J0 i J1 so kapaciteti C0 i C1
  331. #Na pocetok dvata sada se polni. Inicijalnata sostojba moze da se prosledi na pocetok
  332. #Problemot e kako da se stigne do sostojba vo koja J0 ke ima G0 litri, a J1 ke ima G1 litri
  333. #AKCII: 1. Da se isprazni bilo koj od sadovite
  334. #2. Da se prefrli tecnosta od eden sad vo drug so toa sto ne moze da se nadmine kapacitetot na sadovite
  335. # Moze da ima i opcionalen tret vid na akcii 3. Napolni bilo koj od sadovite (studentite da ja implementiraat ovaa varijanta)
  336. # ________________________________________________________________________________________________________
  337.  
  338. class WJ(Problem):
  339. """STATE: Torka od oblik (3,2) if jug J0 has 3 liters and J1 2 liters
  340. Opcionalno moze za nekoj od sadovite da se sretne i vrednost '*' sto znaci deka e nebitno kolku ima vo toj sad
  341. GOAL: Predefinirana sostojba do kade sakame da stigneme. Ako ne interesira samo eden sad za drugiot mozeme da stavime '*'
  342. PROBLEM: Se specificiraat kapacitetite na sadovite, pocetna sostojba i cel """
  343.  
  344. def __init__(self, capacities=(5, 2), initial=(5, 0), goal=(0, 1)):
  345. self.capacities = capacities
  346. self.initial = initial
  347. self.goal = goal
  348.  
  349. def goal_test(self, state):
  350. """ Vraka true ako sostojbata e celna """
  351. g = self.goal
  352. return (state[0] == g[0] or g[0] == '*') and \
  353. (state[1] == g[1] or g[1] == '*')
  354.  
  355. def successor(self, J):
  356. """Vraka recnik od sledbenici na sostojbata"""
  357. successors = dict()
  358. J0, J1 = J
  359. (C0, C1) = self.capacities
  360. if J0 > 0:
  361. Jnew = 0, J1
  362. successors['dump jug 0'] = Jnew
  363. if J1 > 0:
  364. Jnew = J0, 0
  365. successors['dump jug 1'] = Jnew
  366. if J1 < C1 and J0 > 0:
  367. delta = min(J0, C1 - J1)
  368. Jnew = J0 - delta, J1 + delta
  369. successors['pour jug 0 into jug 1'] = Jnew
  370. if J0 < C0 and J1 > 0:
  371. delta = min(J1, C0 - J0)
  372. Jnew = J0 + delta, J1 - delta
  373. successors['pour jug 1 into jug 0'] = Jnew
  374. return successors
  375.  
  376. def actions(self, state):
  377. return self.successor(state).keys()
  378.  
  379. def result(self, state, action):
  380. possible = self.successor(state)
  381. return possible[action]
  382.  
  383. # So vaka definiraniot problem mozeme da gi koristime site neinformirani prebaruvanja
  384. # Vo prodolzenie se dadeni mozni povici (vnimavajte za da moze da napravite povik mora da definirate problem)
  385. #
  386. # WJInstance = WJ((5, 2), (5, 2), ('*', 1))
  387. # print WJInstance
  388. #
  389. # answer1 = breadth_first_tree_search(WJInstance)
  390. # print answer1.solve()
  391. #
  392. # answer2 = depth_first_tree_search(WJInstance) #vnimavajte na ovoj povik, moze da vleze vo beskonecna jamka
  393. # print answer2.solve()
  394. #
  395. # answer3 = breadth_first_graph_search(WJInstance)
  396. # print answer3.solve()
  397. #
  398. # answer4 = depth_first_graph_search(WJInstance)
  399. # print answer4.solve()
  400. #
  401. # answer5 = depth_limited_search(WJInstance)
  402. # print answer5.solve()
  403. #
  404. # answer6 = iterative_deepening_search(WJInstance)
  405. # print answer6.solve()
  406.  
  407. def updateP1(P1):
  408. x = P1[0]
  409. y = P1[1]
  410. n = P1[2]
  411. if (y == 4 and n == 1):
  412. n = n * (-1)
  413. if (y == 0 and n == -1):
  414. n = n * (-1)
  415. ynew = y + n
  416. return (x, ynew, n)
  417.  
  418.  
  419. def updateP2(P2):
  420. x = P2[0]
  421. y = P2[1]
  422. n = P2[2]
  423. if (x == 5 and y == 4 and n == 1):
  424. n = n * (-1)
  425. if (y == 0 and x == 9 and n == -1):
  426. n = n * (-1)
  427. xnew = x - n
  428. ynew = y + n
  429. return (xnew, ynew, n)
  430.  
  431.  
  432. def updateP3(P3):
  433. x = P3[0]
  434. y = P3[1]
  435. n = P3[2]
  436. if (x == 5 and n == -1):
  437. n = n * (-1)
  438. if (x == 9 and n == 1):
  439. n = n * (-1)
  440. xnew = x + n
  441. return (xnew, y, n)
  442.  
  443.  
  444. def isValid(x, y, P1, P2, P3):
  445. t = 1
  446. if (x == P1[0] and y == P1[1]) or (x == P1[0] and y == P1[1] + 1):
  447. t = 0
  448. 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 (
  449. x == P2[0] + 1 and y == P2[1] + 1):
  450. t = 0
  451. if (x == P3[0] and y == P3[1]) or (x == P3[0] + 1 and y == P3[1]):
  452. t = 0
  453. return t
  454.  
  455.  
  456.  
  457. class Istrazuvac(Problem):
  458. def __init__(self, initial, goal):
  459. self.initial = initial
  460. self.goal = goal
  461.  
  462. def successor(self, state):
  463. successors = dict()
  464. X = state[0]
  465. Y = state[1]
  466. P1 = state[2]
  467. P2 = state[3]
  468. P3 = state[4]
  469. P1new = updateP1(P1)
  470. P2new = updateP2(P2)
  471. P3new = updateP3(P3)
  472.  
  473. # Levo
  474. if Y - 1 >= 0:
  475. Ynew = Y - 1
  476. Xnew = X
  477. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  478. successors['Levo'] = (Xnew, Ynew, P1new, P2new, P3new)
  479. # Desno
  480. if X < 5 and Y < 5:
  481. Ynew = Y + 1
  482. Xnew = X
  483. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  484. successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  485. elif X >= 5 and Y < 10:
  486. Xnew = X
  487. Ynew = Y + 1
  488. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  489. successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  490. # Dolu
  491. if X < 10:
  492. Xnew = X + 1
  493. Ynew = Y
  494. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  495. successors['Dolu'] = (Xnew, Ynew, P1new, P2new, P3new)
  496. # Gore
  497. if Y >= 6 and X > 5:
  498. Xnew = X - 1
  499. Ynew = Y
  500. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  501. successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  502. elif Y < 6 and X > 0:
  503. Xnew = X - 1
  504. Ynew = Y
  505. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  506. successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  507. return successors
  508.  
  509. def actions(self, state):
  510. return self.successor(state).keys()
  511.  
  512. def result(self, state, action):
  513. possible = self.successor(state)
  514. return possible[action]
  515.  
  516. def goal_test(self, state):
  517. g = self.goal
  518. return (state[0] == g[0] and state[1] == g[1])
  519. # def h(self,node):
  520. # rez=abs(node.state[0]-self.goal[0])+abs(node.state[1]-self.goal[1])
  521. # return rez
  522.  
  523.  
  524. #Vcituvanje na vleznite argumenti za test primerite
  525.  
  526. CoveceRedica = input()
  527. CoveceKolona = input()
  528. KukaRedica = input()
  529. KukaKolona = input()
  530.  
  531. #Vasiot kod pisuvajte go pod ovoj komentar
  532.  
  533. # prepreka 1 ima lev kvadrat na 2,2 odi levo (-1) na pocetok, prepreka 2 ima goren lev kvadrat na 2,7 odi gore desno (1)
  534. # prepreka 3 ima gore kvadrat na 8,7 odi nagore na pocetok(-1)
  535. IstrazuvacInstance = Istrazuvac((CoveceRedica, CoveceKolona, (2, 2, -1), (7, 2, 1), (7, 8, 1)),(KukaRedica, KukaKolona))
  536.  
  537. answer=breadth_first_graph_search(IstrazuvacInstance)
  538. print(answer.solution())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!