Advertisement
Guest User

Untitled

a guest
Jan 25th, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 28.87 KB | None | 0 0
  1.  
  2.  
  3. import sys
  4. import math
  5. import random
  6. import bisect
  7. from sys import maxsize as infinity
  8.  
  9. """
  10. Дефинирање на класа за структурата на проблемот кој ќе го решаваме со пребарување.
  11. Класата Problem е апстрактна класа од која правиме наследување за дефинирање на основните
  12. карактеристики на секој проблем што сакаме да го решиме
  13. """
  14.  
  15.  
  16. class Problem:
  17. def __init__(self, initial, goal=None):
  18. self.initial = initial
  19. self.goal = goal
  20.  
  21. def successor(self, state):
  22. """За дадена состојба, врати речник од парови {акција : состојба}
  23. достапни од оваа состојба. Ако има многу следбеници, употребете
  24. итератор кој би ги генерирал следбениците еден по еден, наместо да
  25. ги генерирате сите одеднаш.
  26.  
  27. :param state: дадена состојба
  28. :return: речник од парови {акција : состојба} достапни од оваа
  29. состојба
  30. :rtype: dict
  31. """
  32. raise NotImplementedError
  33.  
  34. def actions(self, state):
  35. """За дадена состојба state, врати листа од сите акции што може да
  36. се применат над таа состојба
  37.  
  38. :param state: дадена состојба
  39. :return: листа на акции
  40. :rtype: list
  41. """
  42. raise NotImplementedError
  43.  
  44. def result(self, state, action):
  45. """За дадена состојба state и акција action, врати ја состојбата
  46. што се добива со примена на акцијата над состојбата
  47.  
  48. :param state: дадена состојба
  49. :param action: дадена акција
  50. :return: резултантна состојба
  51. """
  52. raise NotImplementedError
  53.  
  54. def goal_test(self, state):
  55. """Врати True ако state е целна состојба. Даденава имплементација
  56. на методот директно ја споредува state со self.goal, како што е
  57. специфицирана во конструкторот. Имплементирајте го овој метод ако
  58. проверката со една целна состојба self.goal не е доволна.
  59.  
  60. :param state: дадена состојба
  61. :return: дали дадената состојба е целна состојба
  62. :rtype: bool
  63. """
  64. return state == self.goal
  65.  
  66. def path_cost(self, c, state1, action, state2):
  67. """Врати ја цената на решавачкиот пат кој пристигнува во состојбата
  68. state2 од состојбата state1 преку акцијата action, претпоставувајќи
  69. дека цената на патот до состојбата state1 е c. Ако проблемот е таков
  70. што патот не е важен, оваа функција ќе ја разгледува само состојбата
  71. state2. Ако патот е важен, ќе ја разгледува цената c и можеби и
  72. state1 и action. Даденава имплементација му доделува цена 1 на секој
  73. чекор од патот.
  74.  
  75. :param c: цена на патот до состојбата state1
  76. :param state1: дадена моментална состојба
  77. :param action: акција која треба да се изврши
  78. :param state2: состојба во која треба да се стигне
  79. :return: цена на патот по извршување на акцијата
  80. :rtype: float
  81. """
  82. return c + 1
  83.  
  84. def value(self):
  85. """За проблеми на оптимизација, секоја состојба си има вредност. 
  86. Hill-climbing и сличните алгоритми се обидуваат да ја максимизираат
  87. оваа вредност.
  88.  
  89. :return: вредност на состојба
  90. :rtype: float
  91. """
  92. raise NotImplementedError
  93.  
  94.  
  95. """
  96. Дефинирање на класата за структурата на јазел од пребарување.
  97. Класата Node не се наследува
  98. """
  99.  
  100.  
  101. class Node:
  102. def __init__(self, state, parent=None, action=None, path_cost=0):
  103. """Креирај јазол од пребарувачкото дрво, добиен од parent со примена
  104. на акцијата action
  105.  
  106. :param state: моментална состојба (current state)
  107. :param parent: родителска состојба (parent state)
  108. :param action: акција (action)
  109. :param path_cost: цена на патот (path cost)
  110. """
  111. self.state = state
  112. self.parent = parent
  113. self.action = action
  114. self.path_cost = path_cost
  115. self.depth = 0 # search depth
  116. if parent:
  117. self.depth = parent.depth + 1
  118.  
  119. def __repr__(self):
  120. return "<Node %s>" % (self.state,)
  121.  
  122. def __lt__(self, node):
  123. return self.state < node.state
  124.  
  125. def expand(self, problem):
  126. """Излистај ги јазлите достапни во еден чекор од овој јазол.
  127.  
  128. :param problem: даден проблем
  129. :return: листа на достапни јазли во еден чекор
  130. :rtype: list(Node)
  131. """
  132.  
  133. return [self.child_node(problem, action)
  134. for action in problem.actions(self.state)]
  135.  
  136. def child_node(self, problem, action):
  137. """Дете јазел
  138.  
  139. :param problem: даден проблем
  140. :param action: дадена акција
  141. :return: достапен јазел според дадената акција
  142. :rtype: Node
  143. """
  144. next_state = problem.result(self.state, action)
  145. return Node(next_state, self, action,
  146. problem.path_cost(self.path_cost, self.state,
  147. action, next_state))
  148.  
  149. def solution(self):
  150. """Врати ја секвенцата од акции за да се стигне од коренот до овој јазол.
  151.  
  152. :return: секвенцата од акции
  153. :rtype: list
  154. """
  155. return [node.action for node in self.path()[1:]]
  156.  
  157. def solve(self):
  158. """Врати ја секвенцата од состојби за да се стигне од коренот до овој јазол.
  159.  
  160. :return: листа од состојби
  161. :rtype: list
  162. """
  163. return [node.state for node in self.path()[0:]]
  164.  
  165. def path(self):
  166. """Врати ја листата од јазли што го формираат патот од коренот до овој јазол.
  167.  
  168. :return: листа од јазли од патот
  169. :rtype: list(Node)
  170. """
  171. x, result = self, []
  172. while x:
  173. result.append(x)
  174. x = x.parent
  175. result.reverse()
  176. return result
  177.  
  178. """Сакаме редицата од јазли кај breadth_first_search или
  179. astar_search да не содржи состојби - дупликати, па јазлите што
  180. содржат иста состојба ги третираме како исти. [Проблем: ова може
  181. да не биде пожелно во други ситуации.]"""
  182.  
  183. def __eq__(self, other):
  184. return isinstance(other, Node) and self.state == other.state
  185.  
  186. def __hash__(self):
  187. return hash(self.state)
  188.  
  189.  
  190. """
  191. Дефинирање на помошни структури за чување на листата на генерирани, но непроверени јазли
  192. """
  193.  
  194.  
  195. class Queue:
  196. """Queue е апстрактна класа / интерфејс. Постојат 3 типа:
  197.         Stack(): Last In First Out Queue (стек).
  198.         FIFOQueue(): First In First Out Queue (редица).
  199.         PriorityQueue(order, f): Queue во сортиран редослед (подразбирливо,од најмалиот кон
  200. најголемиот јазол).
  201.     """
  202.  
  203. def __init__(self):
  204. raise NotImplementedError
  205.  
  206. def append(self, item):
  207. """Додади го елементот item во редицата
  208.  
  209. :param item: даден елемент
  210. :return: None
  211. """
  212. raise NotImplementedError
  213.  
  214. def extend(self, items):
  215. """Додади ги елементите items во редицата
  216.  
  217. :param items: дадени елементи
  218. :return: None
  219. """
  220. raise NotImplementedError
  221.  
  222. def pop(self):
  223. """Врати го првиот елемент од редицата
  224.  
  225. :return: прв елемент
  226. """
  227. raise NotImplementedError
  228.  
  229. def __len__(self):
  230. """Врати го бројот на елементи во редицата
  231.  
  232. :return: број на елементи во редицата
  233. :rtype: int
  234. """
  235. raise NotImplementedError
  236.  
  237. def __contains__(self, item):
  238. """Проверка дали редицата го содржи елементот item
  239.  
  240. :param item: даден елемент
  241. :return: дали queue го содржи item
  242. :rtype: bool
  243. """
  244. raise NotImplementedError
  245.  
  246.  
  247. class Stack(Queue):
  248. """Last-In-First-Out Queue."""
  249.  
  250. def __init__(self):
  251. self.data = []
  252.  
  253. def append(self, item):
  254. self.data.append(item)
  255.  
  256. def extend(self, items):
  257. self.data.extend(items)
  258.  
  259. def pop(self):
  260. return self.data.pop()
  261.  
  262. def __len__(self):
  263. return len(self.data)
  264.  
  265. def __contains__(self, item):
  266. return item in self.data
  267.  
  268.  
  269. class FIFOQueue(Queue):
  270. """First-In-First-Out Queue."""
  271.  
  272. def __init__(self):
  273. self.data = []
  274.  
  275. def append(self, item):
  276. self.data.append(item)
  277.  
  278. def extend(self, items):
  279. self.data.extend(items)
  280.  
  281. def pop(self):
  282. return self.data.pop(0)
  283.  
  284. def __len__(self):
  285. return len(self.data)
  286.  
  287. def __contains__(self, item):
  288. return item in self.data
  289.  
  290.  
  291. class PriorityQueue(Queue):
  292. """Редица во која прво се враќа минималниот (или максималниот) елемент
  293. (како што е определено со f и order). Оваа структура се користи кај
  294. информирано пребарување"""
  295. """"""
  296.  
  297. def __init__(self, order=min, f=lambda x: x):
  298. """
  299. :param order: функција за подредување, ако order е min, се враќа елементот
  300. со минимална f(x); ако order е max, тогаш се враќа елементот
  301. со максимална f(x).
  302. :param f: функција f(x)
  303. """
  304. assert order in [min, max]
  305. self.data = []
  306. self.order = order
  307. self.f = f
  308.  
  309. def append(self, item):
  310. bisect.insort_right(self.data, (self.f(item), item))
  311.  
  312. def extend(self, items):
  313. for item in items:
  314. bisect.insort_right(self.data, (self.f(item), item))
  315.  
  316. def pop(self):
  317. if self.order == min:
  318. return self.data.pop(0)[1]
  319. return self.data.pop()[1]
  320.  
  321. def __len__(self):
  322. return len(self.data)
  323.  
  324. def __contains__(self, item):
  325. return any(item == pair[1] for pair in self.data)
  326.  
  327. def __getitem__(self, key):
  328. for _, item in self.data:
  329. if item == key:
  330. return item
  331.  
  332. def __delitem__(self, key):
  333. for i, (value, item) in enumerate(self.data):
  334. if item == key:
  335. self.data.pop(i)
  336.  
  337.  
  338. """
  339. Неинформирано пребарување во рамки на дрво.
  340. Во рамки на дрвото не разрешуваме јамки.
  341. """
  342.  
  343.  
  344. def tree_search(problem, fringe):
  345. """ Пребарувај низ следбениците на даден проблем за да најдеш цел.
  346.  
  347. :param problem: даден проблем
  348. :param fringe: празна редица (queue)
  349. :return: Node
  350. """
  351. fringe.append(Node(problem.initial))
  352. while fringe:
  353. node = fringe.pop()
  354. print(node.state)
  355. if problem.goal_test(node.state):
  356. return node
  357. fringe.extend(node.expand(problem))
  358. return None
  359.  
  360.  
  361. def breadth_first_tree_search(problem):
  362. """Експандирај го прво најплиткиот јазол во пребарувачкото дрво.
  363.  
  364. :param problem: даден проблем
  365. :return: Node
  366. """
  367. return tree_search(problem, FIFOQueue())
  368.  
  369.  
  370. def depth_first_tree_search(problem):
  371. """Експандирај го прво најдлабокиот јазол во пребарувачкото дрво.
  372.  
  373. :param problem:даден проблем
  374. :return: Node
  375. """
  376. return tree_search(problem, Stack())
  377.  
  378.  
  379. """
  380. Неинформирано пребарување во рамки на граф
  381. Основната разлика е во тоа што овде не дозволуваме јамки,
  382. т.е. повторување на состојби
  383. """
  384.  
  385.  
  386. def graph_search(problem, fringe):
  387. """Пребарувај низ следбениците на даден проблем за да најдеш цел.
  388. Ако до дадена состојба стигнат два пата, употреби го најдобриот пат.
  389.  
  390. :param problem: даден проблем
  391. :param fringe: празна редица (queue)
  392. :return: Node
  393. """
  394. closed = set()
  395. fringe.append(Node(problem.initial))
  396. while fringe:
  397. node = fringe.pop()
  398. if problem.goal_test(node.state):
  399. return node
  400. if node.state not in closed:
  401. closed.add(node.state)
  402. fringe.extend(node.expand(problem))
  403. return None
  404.  
  405.  
  406. def breadth_first_graph_search(problem):
  407. """Експандирај го прво најплиткиот јазол во пребарувачкиот граф.
  408.  
  409. :param problem: даден проблем
  410. :return: Node
  411. """
  412. return graph_search(problem, FIFOQueue())
  413.  
  414.  
  415. def depth_first_graph_search(problem):
  416. """Експандирај го прво најдлабокиот јазол во пребарувачкиот граф.
  417.  
  418. :param problem: даден проблем
  419. :return: Node
  420. """
  421. return graph_search(problem, Stack())
  422.  
  423.  
  424. def depth_limited_search(problem, limit=50):
  425. def recursive_dls(node, problem, limit):
  426. """Помошна функција за depth limited"""
  427. cutoff_occurred = False
  428. if problem.goal_test(node.state):
  429. return node
  430. elif node.depth == limit:
  431. return 'cutoff'
  432. else:
  433. for successor in node.expand(problem):
  434. result = recursive_dls(successor, problem, limit)
  435. if result == 'cutoff':
  436. cutoff_occurred = True
  437. elif result is not None:
  438. return result
  439. if cutoff_occurred:
  440. return 'cutoff'
  441. return None
  442.  
  443. return recursive_dls(Node(problem.initial), problem, limit)
  444.  
  445.  
  446. def iterative_deepening_search(problem):
  447. for depth in range(sys.maxsize):
  448. result = depth_limited_search(problem, depth)
  449. if result is not 'cutoff':
  450. return result
  451.  
  452.  
  453. def uniform_cost_search(problem):
  454. """Експандирај го прво јазолот со најниска цена во пребарувачкиот граф."""
  455. return graph_search(problem, PriorityQueue(min, lambda a: a.path_cost))
  456.  
  457.  
  458. """
  459. Информирано пребарување во рамки на граф
  460. """
  461.  
  462.  
  463. def memoize(fn, slot=None):
  464. """ Запамети ја пресметаната вредност за која била листа од
  465. аргументи. Ако е специфициран slot, зачувај го резултатот во
  466. тој slot на првиот аргумент. Ако slot е None, зачувај ги
  467. резултатите во речник.
  468.  
  469. :param fn: зададена функција
  470. :param slot: име на атрибут во кој се чуваат резултатите од функцијата
  471. :return: функција со модификација за зачувување на резултатите
  472. """
  473. if slot:
  474. def memoized_fn(obj, *args):
  475. if hasattr(obj, slot):
  476. return getattr(obj, slot)
  477. else:
  478. val = fn(obj, *args)
  479. setattr(obj, slot, val)
  480. return val
  481. else:
  482. def memoized_fn(*args):
  483. if args not in memoized_fn.cache:
  484. memoized_fn.cache[args] = fn(*args)
  485. return memoized_fn.cache[args]
  486.  
  487. memoized_fn.cache = {}
  488. return memoized_fn
  489.  
  490.  
  491. def best_first_graph_search(problem, f):
  492. """Пребарувај низ следбениците на даден проблем за да најдеш цел. Користи
  493. функција за евалуација за да се одлучи кој е сосед најмногу ветува и
  494. потоа да се истражи. Ако до дадена состојба стигнат два пата, употреби
  495. го најдобриот пат.
  496.  
  497. :param problem: даден проблем
  498. :param f: дадена функција за евристика
  499. :return: Node or None
  500. """
  501. f = memoize(f, 'f')
  502. node = Node(problem.initial)
  503. if problem.goal_test(node.state):
  504. return node
  505. frontier = PriorityQueue(min, f)
  506. frontier.append(node)
  507. explored = set()
  508. while frontier:
  509. node = frontier.pop()
  510. if problem.goal_test(node.state):
  511. return node
  512. explored.add(node.state)
  513. for child in node.expand(problem):
  514. if child.state not in explored and child not in frontier:
  515. frontier.append(child)
  516. elif child in frontier:
  517. incumbent = frontier[child]
  518. if f(child) < f(incumbent):
  519. del frontier[incumbent]
  520. frontier.append(child)
  521. return None
  522.  
  523.  
  524. def greedy_best_first_graph_search(problem, h=None):
  525. """ Greedy best-first пребарување се остварува ако се специфицира дека f(n) = h(n).
  526.  
  527. :param problem: даден проблем
  528. :param h: дадена функција за евристика
  529. :return: Node or None
  530. """
  531. h = memoize(h or problem.h, 'h')
  532. return best_first_graph_search(problem, h)
  533.  
  534.  
  535. def astar_search(problem, h=None):
  536. """ A* пребарување е best-first graph пребарување каде f(n) = g(n) + h(n).
  537.  
  538. :param problem: даден проблем
  539. :param h: дадена функција за евристика
  540. :return: Node or None
  541. """
  542. h = memoize(h or problem.h, 'h')
  543. return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
  544.  
  545.  
  546. def recursive_best_first_search(problem, h=None):
  547. """Recursive best first search - ја ограничува рекурзијата
  548. преку следење на f-вредноста на најдобриот алтернативен пат
  549. од било кој јазел предок (еден чекор гледање нанапред).
  550.  
  551. :param problem: даден проблем
  552. :param h: дадена функција за евристика
  553. :return: Node or None
  554. """
  555. h = memoize(h or problem.h, 'h')
  556.  
  557. def RBFS(problem, node, flimit):
  558. if problem.goal_test(node.state):
  559. return node, 0 # (втората вредност е неважна)
  560. successors = node.expand(problem)
  561. if len(successors) == 0:
  562. return None, infinity
  563. for s in successors:
  564. s.f = max(s.path_cost + h(s), node.f)
  565. while True:
  566. # Подреди ги според најниската f вредност
  567. successors.sort(key=lambda x: x.f)
  568. best = successors[0]
  569. if best.f > flimit:
  570. return None, best.f
  571. if len(successors) > 1:
  572. alternative = successors[1].f
  573. else:
  574. alternative = infinity
  575. result, best.f = RBFS(problem, best, min(flimit, alternative))
  576. if result is not None:
  577. return result, best.f
  578.  
  579. node = Node(problem.initial)
  580. node.f = h(node)
  581. result, bestf = RBFS(problem, node, infinity)
  582. return result
  583.  
  584.  
  585. """
  586. Пребарување низ проблем дефиниран како конечен граф
  587. """
  588.  
  589.  
  590. def distance(a, b):
  591. """Растојание помеѓу две (x, y) точки."""
  592. return math.hypot((a[0] - b[0]), (a[1] - b[1]))
  593.  
  594.  
  595. class Graph:
  596. def __init__(self, dictionary=None, directed=True):
  597. self.dict = dictionary or {}
  598. self.directed = directed
  599. if not directed:
  600. self.make_undirected()
  601. else:
  602. # додади празен речник за линковите на оние јазли кои немаат
  603. # насочени врски и не се дадени како клучеви во речникот
  604. nodes_no_edges = list({y for x in self.dict.values()
  605. for y in x if y not in self.dict})
  606. for node in nodes_no_edges:
  607. self.dict[node] = {}
  608.  
  609. def make_undirected(self):
  610. """Ориентираниот граф претвори го во неориентиран со додавање
  611. на симетричните ребра."""
  612. for a in list(self.dict.keys()):
  613. for (b, dist) in self.dict[a].items():
  614. self.connect1(b, a, dist)
  615.  
  616. def connect(self, node_a, node_b, distance_val=1):
  617. """Додади ребро од A до B со дадено растојание, а додади го и
  618. обратното ребро (од B до A) ако графот е неориентиран."""
  619. self.connect1(node_a, node_b, distance_val)
  620. if not self.directed:
  621. self.connect1(node_b, node_a, distance_val)
  622.  
  623. def connect1(self, node_a, node_b, distance_val):
  624. """Додади ребро од A до B со дадено растојание, но само во
  625. едната насока."""
  626. self.dict.setdefault(node_a, {})[node_b] = distance_val
  627.  
  628. def get(self, a, b=None):
  629. """Врати растојание придружено на ребро или пак врати речник
  630. чии елементи се од обликот {јазол : растојание}.
  631. .get(a,b) го враќа растојанието или пак враќа None
  632. .get(a) враќа речник со елементи од обликот {јазол : растојание},
  633. кој може да биде и празен – {}."""
  634. links = self.dict.get(a)
  635. if b is None:
  636. return links
  637. else:
  638. return links.get(b)
  639.  
  640. def nodes(self):
  641. """Врати листа од јазлите во графот."""
  642. return list(self.dict.keys())
  643.  
  644.  
  645. def UndirectedGraph(dictionary=None):
  646. """Изгради Graph во кој што секое ребро (вклучувајќи ги и идните
  647. ребра) е двонасочно."""
  648. return Graph(dictionary=dictionary, directed=False)
  649.  
  650.  
  651. def RandomGraph(nodes=list(range(10)), min_links=2, width=400, height=300,
  652. curvature=lambda: random.uniform(1.1, 1.5)):
  653. """Construct a random graph, with the specified nodes, and random links.
  654. The nodes are laid out randomly on a (width x height) rectangle.
  655. Then each node is connected to the min_links nearest neighbors.
  656. Because inverse links are added, some nodes will have more connections.
  657. The distance between nodes is the hypotenuse times curvature(),
  658. where curvature() defaults to a random number between 1.1 and 1.5."""
  659. g = UndirectedGraph()
  660. g.locations = {}
  661. # Build the cities
  662. for node in nodes:
  663. g.locations[node] = (random.randrange(width), random.randrange(height))
  664. # Build roads from each city to at least min_links nearest neighbors.
  665. for i in range(min_links):
  666. for node in nodes:
  667. if len(g.get(node)) < min_links:
  668. here = g.locations[node]
  669.  
  670. def distance_to_node(n):
  671. if n is node or g.get(node, n):
  672. return math.inf
  673. return distance(g.locations[n], here)
  674.  
  675. neighbor = nodes.index(min(nodes, key=distance_to_node))
  676. d = distance(g.locations[neighbor], here) * curvature()
  677. g.connect(node, neighbor, int(d))
  678. return g
  679.  
  680.  
  681. class GraphProblem(Problem):
  682. """Проблем на пребарување на граф од еден до друг јазол."""
  683.  
  684. def __init__(self, initial, goal, graph):
  685. super().__init__(initial, goal)
  686. self.graph = graph
  687.  
  688. def successor(self, state):
  689.  
  690. recnik = dict()
  691. pom = self.graph.get(state[0])
  692.  
  693. for el in pom:
  694. listState = [state[0],list(state[1])]
  695. if el in listState[1]:
  696. listState[1].remove(el)
  697. listState[0] = el
  698. recnik[el] = (el,tuple(listState[1]))
  699. return recnik
  700.  
  701. def actions(self, state):
  702. """Акциите кај јазол во граф се едноставно - неговите соседи."""
  703. return self.successor(state).keys()
  704.  
  705. def result(self, state, action):
  706. """Резултат на одењето кон сосед е самиот тој сосед."""
  707. return self.successor(state)[action]
  708.  
  709. def path_cost(self, c, state1, action, state2):
  710. return c + (self.graph.get(state1[0], state2[0]) or math.inf)
  711.  
  712. def goal_test(self, state):
  713. if len(state[1]) == 0 and state[0] == self.goal :
  714. return True
  715. return False
  716.  
  717. def h(self, node):
  718. """Функцијата h е праволиниско растојание од состојбата зачувана
  719. во тековниот јазол до целната состојба."""
  720. locs = getattr(self.graph, 'locations', None)
  721. if locs:
  722. return int(distance(locs[node.state[0]], locs[self.goal]))
  723. else:
  724. return math.inf
  725.  
  726.  
  727. if __name__ == '__main__':
  728. romania_map = UndirectedGraph(dict(
  729. Arad=dict(Zerind=75, Sibiu=140, Timisoara=118),
  730. Bucharest=dict(Urziceni=85, Pitesti=101, Giurgiu=90, Fagaras=211),
  731. Craiova=dict(Drobeta=120, Rimnicu=146, Pitesti=138),
  732. Drobeta=dict(Mehadia=75),
  733. Eforie=dict(Hirsova=86),
  734. Fagaras=dict(Sibiu=99),
  735. Hirsova=dict(Urziceni=98),
  736. Iasi=dict(Vaslui=92, Neamt=87),
  737. Lugoj=dict(Timisoara=111, Mehadia=70),
  738. Oradea=dict(Zerind=71, Sibiu=151),
  739. Pitesti=dict(Rimnicu=97),
  740. Rimnicu=dict(Sibiu=80),
  741. Urziceni=dict(Vaslui=142)))
  742.  
  743. romania_map.locations = dict(
  744. Arad=(91, 492), Bucharest=(400, 327), Craiova=(253, 288),
  745. Drobeta=(165, 299), Eforie=(562, 293), Fagaras=(305, 449),
  746. Giurgiu=(375, 270), Hirsova=(534, 350), Iasi=(473, 506),
  747. Lugoj=(165, 379), Mehadia=(168, 339), Neamt=(406, 537),
  748. Oradea=(131, 571), Pitesti=(320, 368), Rimnicu=(233, 410),
  749. Sibiu=(207, 457), Timisoara=(94, 410), Urziceni=(456, 350),
  750. Vaslui=(509, 444), Zerind=(108, 531))
  751.  
  752. pocetok = "Oradea"
  753. kraj = "Neamt"
  754. torka = ("Timisoara","Lugoj","Craiova","Rimnicu")
  755.  
  756. problem = GraphProblem((pocetok,torka),kraj,romania_map)
  757.  
  758. answer = astar_search(problem)
  759.  
  760. print(answer.solution())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement