Advertisement
Guest User

Untitled

a guest
May 22nd, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 123.56 KB | None | 0 0
  1. **********Patuvanje niz germ************
  2. # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
  3.  
  4. # ______________________________________________________________________________________________
  5. # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
  6.  
  7. import sys
  8. import bisect
  9.  
  10. infinity = float('inf') # sistemski definirana vrednost za beskonecnost
  11.  
  12.  
  13. # ______________________________________________________________________________________________
  14. # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
  15.  
  16. class Queue:
  17. """Queue is an abstract class/interface. There are three types:
  18. Stack(): A Last In First Out Queue.
  19. FIFOQueue(): A First In First Out Queue.
  20. PriorityQueue(order, f): Queue in sorted order (default min-first).
  21. Each type supports the following methods and functions:
  22. q.append(item) -- add an item to the queue
  23. q.extend(items) -- equivalent to: for item in items: q.append(item)
  24. q.pop() -- return the top item from the queue
  25. len(q) -- number of items in q (also q.__len())
  26. item in q -- does q contain item?
  27. Note that isinstance(Stack(), Queue) is false, because we implement stacks
  28. as lists. If Python ever gets interfaces, Queue will be an interface."""
  29.  
  30. def __init__(self):
  31. raise NotImplementedError
  32.  
  33. def extend(self, items):
  34. for item in items:
  35. self.append(item)
  36.  
  37.  
  38. def Stack():
  39. """A Last-In-First-Out Queue."""
  40. return []
  41.  
  42.  
  43. class FIFOQueue(Queue):
  44. """A First-In-First-Out Queue."""
  45.  
  46. def __init__(self):
  47. self.A = []
  48. self.start = 0
  49.  
  50. def append(self, item):
  51. self.A.append(item)
  52.  
  53. def __len__(self):
  54. return len(self.A) - self.start
  55.  
  56. def extend(self, items):
  57. self.A.extend(items)
  58.  
  59. def pop(self):
  60. e = self.A[self.start]
  61. self.start += 1
  62. if self.start > 5 and self.start > len(self.A) / 2:
  63. self.A = self.A[self.start:]
  64. self.start = 0
  65. return e
  66.  
  67. def __contains__(self, item):
  68. return item in self.A[self.start:]
  69.  
  70.  
  71. class PriorityQueue(Queue):
  72. """A queue in which the minimum (or maximum) element (as determined by f and
  73. order) is returned first. If order is min, the item with minimum f(x) is
  74. returned first; if order is max, then it is the item with maximum f(x).
  75. Also supports dict-like lookup. This structure will be most useful in informed searches"""
  76.  
  77. def __init__(self, order=min, f=lambda x: x):
  78. self.A = []
  79. self.order = order
  80. self.f = f
  81.  
  82. def append(self, item):
  83. bisect.insort(self.A, (self.f(item), item))
  84.  
  85. def __len__(self):
  86. return len(self.A)
  87.  
  88. def pop(self):
  89. if self.order == min:
  90. return self.A.pop(0)[1]
  91. else:
  92. return self.A.pop()[1]
  93.  
  94. def __contains__(self, item):
  95. return any(item == pair[1] for pair in self.A)
  96.  
  97. def __getitem__(self, key):
  98. for _, item in self.A:
  99. if item == key:
  100. return item
  101.  
  102. def __delitem__(self, key):
  103. for i, (value, item) in enumerate(self.A):
  104. if item == key:
  105. self.A.pop(i)
  106.  
  107.  
  108. # ______________________________________________________________________________________________
  109. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  110. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  111. # na sekoj eden problem sto sakame da go resime
  112.  
  113.  
  114. class Problem:
  115. """The abstract class for a formal problem. You should subclass this and
  116. implement the method successor, and possibly __init__, goal_test, and
  117. path_cost. Then you will create instances of your subclass and solve them
  118. with the various search functions."""
  119.  
  120. def __init__(self, initial, goal=None):
  121. """The constructor specifies the initial state, and possibly a goal
  122. state, if there is a unique goal. Your subclass's constructor can add
  123. other arguments."""
  124. self.initial = initial
  125. self.goal = goal
  126.  
  127. def successor(self, state):
  128. """Given a state, return a dictionary of {action : state} pairs reachable
  129. from this state. If there are many successors, consider an iterator
  130. that yields the successors one at a time, rather than building them
  131. all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  132. raise NotImplementedError
  133.  
  134. def actions(self, state):
  135. """Given a state, return a list of all actions possible from that state"""
  136. raise NotImplementedError
  137.  
  138. def result(self, state, action):
  139. """Given a state and action, return the resulting state"""
  140. raise NotImplementedError
  141.  
  142. def goal_test(self, state):
  143. """Return True if the state is a goal. The default method compares the
  144. state to self.goal, as specified in the constructor. Implement this
  145. method if checking against a single self.goal is not enough."""
  146. return state == self.goal
  147.  
  148. def path_cost(self, c, state1, action, state2):
  149. """Return the cost of a solution path that arrives at state2 from
  150. state1 via action, assuming cost c to get up to state1. If the problem
  151. is such that the path doesn't matter, this function will only look at
  152. state2. If the path does matter, it will consider c and maybe state1
  153. and action. The default method costs 1 for every step in the path."""
  154. return c + 1
  155.  
  156. def value(self):
  157. """For optimization problems, each state has a value. Hill-climbing
  158. and related algorithms try to maximize this value."""
  159. raise NotImplementedError
  160.  
  161.  
  162. # ______________________________________________________________________________
  163. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  164. # Klasata Node ne se nasleduva
  165.  
  166. class Node:
  167. """A node in a search tree. Contains a pointer to the parent (the node
  168. that this is a successor of) and to the actual state for this node. Note
  169. that if a state is arrived at by two paths, then there are two nodes with
  170. the same state. Also includes the action that got us to this state, and
  171. the total path_cost (also known as g) to reach the node. Other functions
  172. may add an f and h value; see best_first_graph_search and astar_search for
  173. an explanation of how the f and h values are handled. You will not need to
  174. subclass this class."""
  175.  
  176. def __init__(self, state, parent=None, action=None, path_cost=0):
  177. "Create a search tree Node, derived from a parent by an action."
  178. self.state = state
  179. self.parent = parent
  180. self.action = action
  181. self.path_cost = path_cost
  182. self.depth = 0
  183. if parent:
  184. self.depth = parent.depth + 1
  185.  
  186. def __repr__(self):
  187. return "<Node %s>" % (self.state,)
  188.  
  189. def __lt__(self, node):
  190. return self.state < node.state
  191.  
  192. def expand(self, problem):
  193. "List the nodes reachable in one step from this node."
  194. return [self.child_node(problem, action)
  195. for action in problem.actions(self.state)]
  196.  
  197. def child_node(self, problem, action):
  198. "Return a child node from this node"
  199. next = problem.result(self.state, action)
  200. return Node(next, self, action,
  201. problem.path_cost(self.path_cost, self.state,
  202. action, next))
  203.  
  204. def solution(self):
  205. "Return the sequence of actions to go from the root to this node."
  206. return [node.action for node in self.path()[1:]]
  207.  
  208. def solve(self):
  209. "Return the sequence of states to go from the root to this node."
  210. return [node.state for node in self.path()[0:]]
  211.  
  212. def path(self):
  213. "Return a list of nodes forming the path from the root to this node."
  214. x, result = self, []
  215. while x:
  216. result.append(x)
  217. x = x.parent
  218. return list(reversed(result))
  219.  
  220. # We want for a queue of nodes in breadth_first_search or
  221. # astar_search to have no duplicated states, so we treat nodes
  222. # with the same state as equal. [Problem: this may not be what you
  223. # want in other contexts.]
  224.  
  225. def __eq__(self, other):
  226. return isinstance(other, Node) and self.state == other.state
  227.  
  228. def __hash__(self):
  229. return hash(self.state)
  230.  
  231.  
  232. # ________________________________________________________________________________________________________
  233. #Neinformirano prebaruvanje vo ramki na drvo
  234. #Vo ramki na drvoto ne razresuvame jamki
  235.  
  236. def tree_search(problem, fringe):
  237. """Search through the successors of a problem to find a goal.
  238. The argument fringe should be an empty queue."""
  239. fringe.append(Node(problem.initial))
  240. while fringe:
  241. node = fringe.pop()
  242.  
  243. if problem.goal_test(node.state):
  244. return node
  245. fringe.extend(node.expand(problem))
  246. return None
  247.  
  248.  
  249. def breadth_first_tree_search(problem):
  250. "Search the shallowest nodes in the search tree first."
  251. return tree_search(problem, FIFOQueue())
  252.  
  253.  
  254. def depth_first_tree_search(problem):
  255. "Search the deepest nodes in the search tree first."
  256. return tree_search(problem, Stack())
  257.  
  258.  
  259. # ________________________________________________________________________________________________________
  260. #Neinformirano prebaruvanje vo ramki na graf
  261. #Osnovnata razlika e vo toa sto ovde ne dozvoluvame jamki t.e. povtoruvanje na sostojbi
  262.  
  263. def graph_search(problem, fringe):
  264. """Search through the successors of a problem to find a goal.
  265. The argument fringe should be an empty queue.
  266. If two paths reach a state, only use the best one."""
  267. closed = {}
  268. fringe.append(Node(problem.initial))
  269. while fringe:
  270. node = fringe.pop()
  271. if problem.goal_test(node.state):
  272. return node
  273. if node.state not in closed:
  274. closed[node.state] = True
  275. fringe.extend(node.expand(problem))
  276. return None
  277.  
  278.  
  279. def breadth_first_graph_search(problem):
  280. "Search the shallowest nodes in the search tree first."
  281. return graph_search(problem, FIFOQueue())
  282.  
  283.  
  284. def depth_first_graph_search(problem):
  285. "Search the deepest nodes in the search tree first."
  286. return graph_search(problem, Stack())
  287.  
  288.  
  289. def uniform_cost_search(problem):
  290. "Search the nodes in the search tree with lowest cost first."
  291. return graph_search(problem, PriorityQueue(lambda a, b: a.path_cost < b.path_cost))
  292.  
  293.  
  294. def depth_limited_search(problem, limit=50):
  295. "depth first search with limited depth"
  296.  
  297. def recursive_dls(node, problem, limit):
  298. "helper function for depth limited"
  299. cutoff_occurred = False
  300. if problem.goal_test(node.state):
  301. return node
  302. elif node.depth == limit:
  303. return 'cutoff'
  304. else:
  305. for successor in node.expand(problem):
  306. result = recursive_dls(successor, problem, limit)
  307. if result == 'cutoff':
  308. cutoff_occurred = True
  309. elif result != None:
  310. return result
  311. if cutoff_occurred:
  312. return 'cutoff'
  313. else:
  314. return None
  315.  
  316. # Body of depth_limited_search:
  317. return recursive_dls(Node(problem.initial), problem, limit)
  318.  
  319.  
  320. def iterative_deepening_search(problem):
  321.  
  322. for depth in xrange(sys.maxint):
  323. result = depth_limited_search(problem, depth)
  324. if result is not 'cutoff':
  325. return result
  326.  
  327.  
  328. # ________________________________________________________________________________________________________
  329. #Pomosna funkcija za informirani prebaruvanja
  330. #So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
  331.  
  332. def memoize(fn, slot=None):
  333. """Memoize fn: make it remember the computed value for any argument list.
  334. If slot is specified, store result in that slot of first argument.
  335. If slot is false, store results in a dictionary."""
  336. if slot:
  337. def memoized_fn(obj, *args):
  338. if hasattr(obj, slot):
  339. return getattr(obj, slot)
  340. else:
  341. val = fn(obj, *args)
  342. setattr(obj, slot, val)
  343. return val
  344. else:
  345. def memoized_fn(*args):
  346. if not memoized_fn.cache.has_key(args):
  347. memoized_fn.cache[args] = fn(*args)
  348. return memoized_fn.cache[args]
  349.  
  350. memoized_fn.cache = {}
  351. return memoized_fn
  352.  
  353.  
  354. # ________________________________________________________________________________________________________
  355. #Informirano prebaruvanje vo ramki na graf
  356.  
  357. def best_first_graph_search(problem, f):
  358. """Search the nodes with the lowest f scores first.
  359. You specify the function f(node) that you want to minimize; for example,
  360. if f is a heuristic estimate to the goal, then we have greedy best
  361. first search; if f is node.depth then we have breadth-first search.
  362. There is a subtlety: the line "f = memoize(f, 'f')" means that the f
  363. values will be cached on the nodes as they are computed. So after doing
  364. a best first search you can examine the f values of the path returned."""
  365.  
  366. f = memoize(f, 'f')
  367. node = Node(problem.initial)
  368. if problem.goal_test(node.state):
  369. return node
  370. frontier = PriorityQueue(min, f)
  371. frontier.append(node)
  372. explored = set()
  373. while frontier:
  374. node = frontier.pop()
  375. if problem.goal_test(node.state):
  376. return node
  377. explored.add(node.state)
  378. for child in node.expand(problem):
  379. if child.state not in explored and child not in frontier:
  380. frontier.append(child)
  381. elif child in frontier:
  382. incumbent = frontier[child]
  383. if f(child) < f(incumbent):
  384. del frontier[incumbent]
  385. frontier.append(child)
  386. return None
  387.  
  388.  
  389. def greedy_best_first_graph_search(problem, h=None):
  390. "Greedy best-first search is accomplished by specifying f(n) = h(n)"
  391. h = memoize(h or problem.h, 'h')
  392. return best_first_graph_search(problem, h)
  393.  
  394.  
  395. def astar_search(problem, h=None):
  396. "A* search is best-first graph search with f(n) = g(n)+h(n)."
  397. h = memoize(h or problem.h, 'h')
  398. return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
  399.  
  400.  
  401. # ________________________________________________________________________________________________________
  402. #Dopolnitelni prebaruvanja
  403. #Recursive_best_first_search e implementiran
  404. #Kako zadaca za studentite da gi implementiraat SMA* i IDA*
  405.  
  406. def recursive_best_first_search(problem, h=None):
  407. h = memoize(h or problem.h, 'h')
  408.  
  409. def RBFS(problem, node, flimit):
  410. if problem.goal_test(node.state):
  411. return node, 0 # (The second value is immaterial)
  412. successors = node.expand(problem)
  413. if len(successors) == 0:
  414. return None, infinity
  415. for s in successors:
  416. s.f = max(s.path_cost + h(s), node.f)
  417. while True:
  418. # Order by lowest f value
  419. successors.sort(key=lambda x: x.f)
  420. best = successors[0]
  421. if best.f > flimit:
  422. return None, best.f
  423. if len(successors) > 1:
  424. alternative = successors[1].f
  425. else:
  426. alternative = infinity
  427. result, best.f = RBFS(problem, best, min(flimit, alternative))
  428. if result is not None:
  429. return result, best.f
  430.  
  431. node = Node(problem.initial)
  432. node.f = h(node)
  433. result, bestf = RBFS(problem, node, infinity)
  434. return result
  435.  
  436.  
  437. # Graphs and Graph Problems
  438. import math
  439.  
  440. def distance(a, b):
  441. """The distance between two (x, y) points."""
  442. return math.hypot((a[0] - b[0]), (a[1] - b[1]))
  443.  
  444.  
  445. class Graph:
  446.  
  447. """A graph connects nodes (verticies) by edges (links). Each edge can also
  448. have a length associated with it. The constructor call is something like:
  449. g = Graph({'A': {'B': 1, 'C': 2})
  450. this makes a graph with 3 nodes, A, B, and C, with an edge of length 1 from
  451. A to B, and an edge of length 2 from A to C. You can also do:
  452. g = Graph({'A': {'B': 1, 'C': 2}, directed=False)
  453. This makes an undirected graph, so inverse links are also added. The graph
  454. stays undirected; if you add more links with g.connect('B', 'C', 3), then
  455. inverse link is also added. You can use g.nodes() to get a list of nodes,
  456. g.get('A') to get a dict of links out of A, and g.get('A', 'B') to get the
  457. length of the link from A to B. 'Lengths' can actually be any object at
  458. all, and nodes can be any hashable object."""
  459.  
  460. def __init__(self, dict=None, directed=True):
  461. self.dict = dict or {}
  462. self.directed = directed
  463. if not directed:
  464. self.make_undirected()
  465.  
  466. def make_undirected(self):
  467. """Make a digraph into an undirected graph by adding symmetric edges."""
  468. for a in list(self.dict.keys()):
  469. for (b, dist) in self.dict[a].items():
  470. self.connect1(b, a, dist)
  471.  
  472. def connect(self, A, B, distance=1):
  473. """Add a link from A and B of given distance, and also add the inverse
  474. link if the graph is undirected."""
  475. self.connect1(A, B, distance)
  476. if not self.directed:
  477. self.connect1(B, A, distance)
  478.  
  479. def connect1(self, A, B, distance):
  480. """Add a link from A to B of given distance, in one direction only."""
  481. self.dict.setdefault(A, {})[B] = distance
  482.  
  483. def get(self, a, b=None):
  484. """Return a link distance or a dict of {node: distance} entries.
  485. .get(a,b) returns the distance or None;
  486. .get(a) returns a dict of {node: distance} entries, possibly {}."""
  487. links = self.dict.setdefault(a, {})
  488. if b is None:
  489. return links
  490. else:
  491. return links.get(b)
  492.  
  493. def nodes(self):
  494. """Return a list of nodes in the graph."""
  495. return list(self.dict.keys())
  496.  
  497.  
  498. def UndirectedGraph(dict=None):
  499. """Build a Graph where every edge (including future ones) goes both ways."""
  500. return Graph(dict=dict, directed=False)
  501.  
  502.  
  503. def RandomGraph(nodes=list(range(10)), min_links=2, width=400, height=300,
  504. curvature=lambda: random.uniform(1.1, 1.5)):
  505. """Construct a random graph, with the specified nodes, and random links.
  506. The nodes are laid out randomly on a (width x height) rectangle.
  507. Then each node is connected to the min_links nearest neighbors.
  508. Because inverse links are added, some nodes will have more connections.
  509. The distance between nodes is the hypotenuse times curvature(),
  510. where curvature() defaults to a random number between 1.1 and 1.5."""
  511. g = UndirectedGraph()
  512. g.locations = {}
  513. # Build the cities
  514. for node in nodes:
  515. g.locations[node] = (random.randrange(width), random.randrange(height))
  516. # Build roads from each city to at least min_links nearest neighbors.
  517. for i in range(min_links):
  518. for node in nodes:
  519. if len(g.get(node)) < min_links:
  520. here = g.locations[node]
  521.  
  522. def distance_to_node(n):
  523. if n is node or g.get(node, n):
  524. return infinity
  525. return distance(g.locations[n], here)
  526. neighbor = argmin(nodes, key=distance_to_node)
  527. d = distance(g.locations[neighbor], here) * curvature()
  528. g.connect(node, neighbor, int(d))
  529. return g
  530.  
  531.  
  532.  
  533. class GraphProblem(Problem):
  534.  
  535. """The problem of searching a graph from one node to another."""
  536.  
  537. def __init__(self, initial, goal, graph):
  538. Problem.__init__(self, initial, goal)
  539. self.graph = graph
  540.  
  541. def actions(self, A):
  542. """The actions at a graph node are just its neighbors."""
  543. return list(self.graph.get(A).keys())
  544.  
  545. def result(self, state, action):
  546. """The result of going to a neighbor is just that neighbor."""
  547. return action
  548.  
  549. def path_cost(self, cost_so_far, A, action, B):
  550. return cost_so_far + (self.graph.get(A, B) or infinity)
  551.  
  552. def h(self, node):
  553. """h function is straight-line distance from a node's state to goal."""
  554. locs = getattr(self.graph, 'locations', None)
  555. if locs:
  556. return int(distance(locs[node.state], locs[self.goal]))
  557. else:
  558. return 0
  559.  
  560. Pocetok = input()
  561. Kraj = input()
  562.  
  563. germania_map=UndirectedGraph(dict(
  564. Frankfurt=dict(Mannheim=85, Wurzburg=217, Kassel=173),
  565. Mannheim=dict(Karlsruhe=80),
  566. Wurzburg=dict(Erfurt=186, Nurnberg=103),
  567. Nurnberg=dict(Stuttgart=183, Munchen=167),
  568. Kassel=dict(Munchen=502),
  569. Karlsruhe=dict(Augsburg=250),
  570. Augsburg=dict(Munchen=84)))
  571.  
  572. germania_problem=GraphProblem(Pocetok,Kraj,germania_map)
  573.  
  574. answer=astar_search(germania_problem)
  575. print answer.path_cost
  576.  
  577.  
  578. ****graf*******
  579. # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
  580.  
  581. # ______________________________________________________________________________________________
  582. # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
  583.  
  584. import sys
  585. import bisect
  586.  
  587. infinity = float('inf') # sistemski definirana vrednost za beskonecnost
  588.  
  589.  
  590. # ______________________________________________________________________________________________
  591. # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
  592.  
  593. class Queue:
  594. """Queue is an abstract class/interface. There are three types:
  595. Stack(): A Last In First Out Queue.
  596. FIFOQueue(): A First In First Out Queue.
  597. PriorityQueue(order, f): Queue in sorted order (default min-first).
  598. Each type supports the following methods and functions:
  599. q.append(item) -- add an item to the queue
  600. q.extend(items) -- equivalent to: for item in items: q.append(item)
  601. q.pop() -- return the top item from the queue
  602. len(q) -- number of items in q (also q.__len())
  603. item in q -- does q contain item?
  604. Note that isinstance(Stack(), Queue) is false, because we implement stacks
  605. as lists. If Python ever gets interfaces, Queue will be an interface."""
  606.  
  607. def __init__(self):
  608. raise NotImplementedError
  609.  
  610. def extend(self, items):
  611. for item in items:
  612. self.append(item)
  613.  
  614.  
  615. def Stack():
  616. """A Last-In-First-Out Queue."""
  617. return []
  618.  
  619.  
  620. class FIFOQueue(Queue):
  621. """A First-In-First-Out Queue."""
  622.  
  623. def __init__(self):
  624. self.A = []
  625. self.start = 0
  626.  
  627. def append(self, item):
  628. self.A.append(item)
  629.  
  630. def __len__(self):
  631. return len(self.A) - self.start
  632.  
  633. def extend(self, items):
  634. self.A.extend(items)
  635.  
  636. def pop(self):
  637. e = self.A[self.start]
  638. self.start += 1
  639. if self.start > 5 and self.start > len(self.A) / 2:
  640. self.A = self.A[self.start:]
  641. self.start = 0
  642. return e
  643.  
  644. def __contains__(self, item):
  645. return item in self.A[self.start:]
  646.  
  647.  
  648. class PriorityQueue(Queue):
  649. """A queue in which the minimum (or maximum) element (as determined by f and
  650. order) is returned first. If order is min, the item with minimum f(x) is
  651. returned first; if order is max, then it is the item with maximum f(x).
  652. Also supports dict-like lookup. This structure will be most useful in informed searches"""
  653.  
  654. def __init__(self, order=min, f=lambda x: x):
  655. self.A = []
  656. self.order = order
  657. self.f = f
  658.  
  659. def append(self, item):
  660. bisect.insort(self.A, (self.f(item), item))
  661.  
  662. def __len__(self):
  663. return len(self.A)
  664.  
  665. def pop(self):
  666. if self.order == min:
  667. return self.A.pop(0)[1]
  668. else:
  669. return self.A.pop()[1]
  670.  
  671. def __contains__(self, item):
  672. return any(item == pair[1] for pair in self.A)
  673.  
  674. def __getitem__(self, key):
  675. for _, item in self.A:
  676. if item == key:
  677. return item
  678.  
  679. def __delitem__(self, key):
  680. for i, (value, item) in enumerate(self.A):
  681. if item == key:
  682. self.A.pop(i)
  683.  
  684.  
  685. # ______________________________________________________________________________________________
  686. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  687. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  688. # na sekoj eden problem sto sakame da go resime
  689.  
  690.  
  691. class Problem:
  692. """The abstract class for a formal problem. You should subclass this and
  693. implement the method successor, and possibly __init__, goal_test, and
  694. path_cost. Then you will create instances of your subclass and solve them
  695. with the various search functions."""
  696.  
  697. def __init__(self, initial, goal=None):
  698. """The constructor specifies the initial state, and possibly a goal
  699. state, if there is a unique goal. Your subclass's constructor can add
  700. other arguments."""
  701. self.initial = initial
  702. self.goal = goal
  703.  
  704. def successor(self, state):
  705. """Given a state, return a dictionary of {action : state} pairs reachable
  706. from this state. If there are many successors, consider an iterator
  707. that yields the successors one at a time, rather than building them
  708. all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  709. raise NotImplementedError
  710.  
  711. def actions(self, state):
  712. """Given a state, return a list of all actions possible from that state"""
  713. raise NotImplementedError
  714.  
  715. def result(self, state, action):
  716. """Given a state and action, return the resulting state"""
  717. raise NotImplementedError
  718.  
  719. def goal_test(self, state):
  720. """Return True if the state is a goal. The default method compares the
  721. state to self.goal, as specified in the constructor. Implement this
  722. method if checking against a single self.goal is not enough."""
  723. return state == self.goal
  724.  
  725. def path_cost(self, c, state1, action, state2):
  726. """Return the cost of a solution path that arrives at state2 from
  727. state1 via action, assuming cost c to get up to state1. If the problem
  728. is such that the path doesn't matter, this function will only look at
  729. state2. If the path does matter, it will consider c and maybe state1
  730. and action. The default method costs 1 for every step in the path."""
  731. return c + 1
  732.  
  733. def value(self):
  734. """For optimization problems, each state has a value. Hill-climbing
  735. and related algorithms try to maximize this value."""
  736. raise NotImplementedError
  737.  
  738.  
  739. # ______________________________________________________________________________
  740. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  741. # Klasata Node ne se nasleduva
  742.  
  743. class Node:
  744. """A node in a search tree. Contains a pointer to the parent (the node
  745. that this is a successor of) and to the actual state for this node. Note
  746. that if a state is arrived at by two paths, then there are two nodes with
  747. the same state. Also includes the action that got us to this state, and
  748. the total path_cost (also known as g) to reach the node. Other functions
  749. may add an f and h value; see best_first_graph_search and astar_search for
  750. an explanation of how the f and h values are handled. You will not need to
  751. subclass this class."""
  752.  
  753. def __init__(self, state, parent=None, action=None, path_cost=0):
  754. "Create a search tree Node, derived from a parent by an action."
  755. self.state = state
  756. self.parent = parent
  757. self.action = action
  758. self.path_cost = path_cost
  759. self.depth = 0
  760. if parent:
  761. self.depth = parent.depth + 1
  762.  
  763. def __repr__(self):
  764. return "<Node %s>" % (self.state,)
  765.  
  766. def __lt__(self, node):
  767. return self.state < node.state
  768.  
  769. def expand(self, problem):
  770. "List the nodes reachable in one step from this node."
  771. return [self.child_node(problem, action)
  772. for action in problem.actions(self.state)]
  773.  
  774. def child_node(self, problem, action):
  775. "Return a child node from this node"
  776. next = problem.result(self.state, action)
  777. return Node(next, self, action,
  778. problem.path_cost(self.path_cost, self.state,
  779. action, next))
  780.  
  781. def solution(self):
  782. "Return the sequence of actions to go from the root to this node."
  783. return [node.action for node in self.path()[1:]]
  784.  
  785. def solve(self):
  786. "Return the sequence of states to go from the root to this node."
  787. return [node.state for node in self.path()[0:]]
  788.  
  789. def path(self):
  790. "Return a list of nodes forming the path from the root to this node."
  791. x, result = self, []
  792. while x:
  793. result.append(x)
  794. x = x.parent
  795. return list(reversed(result))
  796.  
  797. # We want for a queue of nodes in breadth_first_search or
  798. # astar_search to have no duplicated states, so we treat nodes
  799. # with the same state as equal. [Problem: this may not be what you
  800. # want in other contexts.]
  801.  
  802. def __eq__(self, other):
  803. return isinstance(other, Node) and self.state == other.state
  804.  
  805. def __hash__(self):
  806. return hash(self.state)
  807.  
  808.  
  809. # ________________________________________________________________________________________________________
  810. #Neinformirano prebaruvanje vo ramki na drvo
  811. #Vo ramki na drvoto ne razresuvame jamki
  812.  
  813. def tree_search(problem, fringe):
  814. """Search through the successors of a problem to find a goal.
  815. The argument fringe should be an empty queue."""
  816. fringe.append(Node(problem.initial))
  817. while fringe:
  818. node = fringe.pop()
  819.  
  820. if problem.goal_test(node.state):
  821. return node
  822. fringe.extend(node.expand(problem))
  823. return None
  824.  
  825.  
  826. def breadth_first_tree_search(problem):
  827. "Search the shallowest nodes in the search tree first."
  828. return tree_search(problem, FIFOQueue())
  829.  
  830.  
  831. def depth_first_tree_search(problem):
  832. "Search the deepest nodes in the search tree first."
  833. return tree_search(problem, Stack())
  834.  
  835.  
  836. # ________________________________________________________________________________________________________
  837. #Neinformirano prebaruvanje vo ramki na graf
  838. #Osnovnata razlika e vo toa sto ovde ne dozvoluvame jamki t.e. povtoruvanje na sostojbi
  839.  
  840. def graph_search(problem, fringe):
  841. """Search through the successors of a problem to find a goal.
  842. The argument fringe should be an empty queue.
  843. If two paths reach a state, only use the best one."""
  844. closed = {}
  845. fringe.append(Node(problem.initial))
  846. while fringe:
  847. node = fringe.pop()
  848. if problem.goal_test(node.state):
  849. return node
  850. if node.state not in closed:
  851. closed[node.state] = True
  852. fringe.extend(node.expand(problem))
  853. return None
  854.  
  855.  
  856. def breadth_first_graph_search(problem):
  857. "Search the shallowest nodes in the search tree first."
  858. return graph_search(problem, FIFOQueue())
  859.  
  860.  
  861. def depth_first_graph_search(problem):
  862. "Search the deepest nodes in the search tree first."
  863. return graph_search(problem, Stack())
  864.  
  865.  
  866. def uniform_cost_search(problem):
  867. "Search the nodes in the search tree with lowest cost first."
  868. return graph_search(problem, PriorityQueue(lambda a, b: a.path_cost < b.path_cost))
  869.  
  870.  
  871. def depth_limited_search(problem, limit=50):
  872. "depth first search with limited depth"
  873.  
  874. def recursive_dls(node, problem, limit):
  875. "helper function for depth limited"
  876. cutoff_occurred = False
  877. if problem.goal_test(node.state):
  878. return node
  879. elif node.depth == limit:
  880. return 'cutoff'
  881. else:
  882. for successor in node.expand(problem):
  883. result = recursive_dls(successor, problem, limit)
  884. if result == 'cutoff':
  885. cutoff_occurred = True
  886. elif result != None:
  887. return result
  888. if cutoff_occurred:
  889. return 'cutoff'
  890. else:
  891. return None
  892.  
  893. # Body of depth_limited_search:
  894. return recursive_dls(Node(problem.initial), problem, limit)
  895.  
  896.  
  897. def iterative_deepening_search(problem):
  898.  
  899. for depth in xrange(sys.maxint):
  900. result = depth_limited_search(problem, depth)
  901. if result is not 'cutoff':
  902. return result
  903.  
  904.  
  905. # ________________________________________________________________________________________________________
  906. #Pomosna funkcija za informirani prebaruvanja
  907. #So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
  908.  
  909. def memoize(fn, slot=None):
  910. """Memoize fn: make it remember the computed value for any argument list.
  911. If slot is specified, store result in that slot of first argument.
  912. If slot is false, store results in a dictionary."""
  913. if slot:
  914. def memoized_fn(obj, *args):
  915. if hasattr(obj, slot):
  916. return getattr(obj, slot)
  917. else:
  918. val = fn(obj, *args)
  919. setattr(obj, slot, val)
  920. return val
  921. else:
  922. def memoized_fn(*args):
  923. if not memoized_fn.cache.has_key(args):
  924. memoized_fn.cache[args] = fn(*args)
  925. return memoized_fn.cache[args]
  926.  
  927. memoized_fn.cache = {}
  928. return memoized_fn
  929.  
  930.  
  931. # ________________________________________________________________________________________________________
  932. #Informirano prebaruvanje vo ramki na graf
  933.  
  934. def best_first_graph_search(problem, f):
  935. """Search the nodes with the lowest f scores first.
  936. You specify the function f(node) that you want to minimize; for example,
  937. if f is a heuristic estimate to the goal, then we have greedy best
  938. first search; if f is node.depth then we have breadth-first search.
  939. There is a subtlety: the line "f = memoize(f, 'f')" means that the f
  940. values will be cached on the nodes as they are computed. So after doing
  941. a best first search you can examine the f values of the path returned."""
  942.  
  943. f = memoize(f, 'f')
  944. node = Node(problem.initial)
  945. if problem.goal_test(node.state):
  946. return node
  947. frontier = PriorityQueue(min, f)
  948. frontier.append(node)
  949. explored = set()
  950. while frontier:
  951. node = frontier.pop()
  952. if problem.goal_test(node.state):
  953. return node
  954. explored.add(node.state)
  955. for child in node.expand(problem):
  956. if child.state not in explored and child not in frontier:
  957. frontier.append(child)
  958. elif child in frontier:
  959. incumbent = frontier[child]
  960. if f(child) < f(incumbent):
  961. del frontier[incumbent]
  962. frontier.append(child)
  963. return None
  964.  
  965.  
  966. def greedy_best_first_graph_search(problem, h=None):
  967. "Greedy best-first search is accomplished by specifying f(n) = h(n)"
  968. h = memoize(h or problem.h, 'h')
  969. return best_first_graph_search(problem, h)
  970.  
  971.  
  972. def astar_search(problem, h=None):
  973. "A* search is best-first graph search with f(n) = g(n)+h(n)."
  974. h = memoize(h or problem.h, 'h')
  975. return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
  976.  
  977.  
  978. # ________________________________________________________________________________________________________
  979. #Dopolnitelni prebaruvanja
  980. #Recursive_best_first_search e implementiran
  981. #Kako zadaca za studentite da gi implementiraat SMA* i IDA*
  982.  
  983. def recursive_best_first_search(problem, h=None):
  984. h = memoize(h or problem.h, 'h')
  985.  
  986. def RBFS(problem, node, flimit):
  987. if problem.goal_test(node.state):
  988. return node, 0 # (The second value is immaterial)
  989. successors = node.expand(problem)
  990. if len(successors) == 0:
  991. return None, infinity
  992. for s in successors:
  993. s.f = max(s.path_cost + h(s), node.f)
  994. while True:
  995. # Order by lowest f value
  996. successors.sort(key=lambda x: x.f)
  997. best = successors[0]
  998. if best.f > flimit:
  999. return None, best.f
  1000. if len(successors) > 1:
  1001. alternative = successors[1].f
  1002. else:
  1003. alternative = infinity
  1004. result, best.f = RBFS(problem, best, min(flimit, alternative))
  1005. if result is not None:
  1006. return result, best.f
  1007.  
  1008. node = Node(problem.initial)
  1009. node.f = h(node)
  1010. result, bestf = RBFS(problem, node, infinity)
  1011. return result
  1012.  
  1013.  
  1014. # Graphs and Graph Problems
  1015. import math
  1016.  
  1017. def distance(a, b):
  1018. """The distance between two (x, y) points."""
  1019. return math.hypot((a[0] - b[0]), (a[1] - b[1]))
  1020.  
  1021.  
  1022. class Graph:
  1023.  
  1024. """A graph connects nodes (verticies) by edges (links). Each edge can also
  1025. have a length associated with it. The constructor call is something like:
  1026. g = Graph({'A': {'B': 1, 'C': 2})
  1027. this makes a graph with 3 nodes, A, B, and C, with an edge of length 1 from
  1028. A to B, and an edge of length 2 from A to C. You can also do:
  1029. g = Graph({'A': {'B': 1, 'C': 2}, directed=False)
  1030. This makes an undirected graph, so inverse links are also added. The graph
  1031. stays undirected; if you add more links with g.connect('B', 'C', 3), then
  1032. inverse link is also added. You can use g.nodes() to get a list of nodes,
  1033. g.get('A') to get a dict of links out of A, and g.get('A', 'B') to get the
  1034. length of the link from A to B. 'Lengths' can actually be any object at
  1035. all, and nodes can be any hashable object."""
  1036.  
  1037. def __init__(self, dict=None, directed=True):
  1038. self.dict = dict or {}
  1039. self.directed = directed
  1040. if not directed:
  1041. self.make_undirected()
  1042.  
  1043. def make_undirected(self):
  1044. """Make a digraph into an undirected graph by adding symmetric edges."""
  1045. for a in list(self.dict.keys()):
  1046. for (b, dist) in self.dict[a].items():
  1047. self.connect1(b, a, dist)
  1048.  
  1049. def connect(self, A, B, distance=1):
  1050. """Add a link from A and B of given distance, and also add the inverse
  1051. link if the graph is undirected."""
  1052. self.connect1(A, B, distance)
  1053. if not self.directed:
  1054. self.connect1(B, A, distance)
  1055.  
  1056. def connect1(self, A, B, distance):
  1057. """Add a link from A to B of given distance, in one direction only."""
  1058. self.dict.setdefault(A, {})[B] = distance
  1059.  
  1060. def get(self, a, b=None):
  1061. """Return a link distance or a dict of {node: distance} entries.
  1062. .get(a,b) returns the distance or None;
  1063. .get(a) returns a dict of {node: distance} entries, possibly {}."""
  1064. links = self.dict.setdefault(a, {})
  1065. if b is None:
  1066. return links
  1067. else:
  1068. return links.get(b)
  1069.  
  1070. def nodes(self):
  1071. """Return a list of nodes in the graph."""
  1072. return list(self.dict.keys())
  1073.  
  1074.  
  1075. def UndirectedGraph(dict=None):
  1076. """Build a Graph where every edge (including future ones) goes both ways."""
  1077. return Graph(dict=dict, directed=False)
  1078.  
  1079.  
  1080. def RandomGraph(nodes=list(range(10)), min_links=2, width=400, height=300,
  1081. curvature=lambda: random.uniform(1.1, 1.5)):
  1082. """Construct a random graph, with the specified nodes, and random links.
  1083. The nodes are laid out randomly on a (width x height) rectangle.
  1084. Then each node is connected to the min_links nearest neighbors.
  1085. Because inverse links are added, some nodes will have more connections.
  1086. The distance between nodes is the hypotenuse times curvature(),
  1087. where curvature() defaults to a random number between 1.1 and 1.5."""
  1088. g = UndirectedGraph()
  1089. g.locations = {}
  1090. # Build the cities
  1091. for node in nodes:
  1092. g.locations[node] = (random.randrange(width), random.randrange(height))
  1093. # Build roads from each city to at least min_links nearest neighbors.
  1094. for i in range(min_links):
  1095. for node in nodes:
  1096. if len(g.get(node)) < min_links:
  1097. here = g.locations[node]
  1098.  
  1099. def distance_to_node(n):
  1100. if n is node or g.get(node, n):
  1101. return infinity
  1102. return distance(g.locations[n], here)
  1103. neighbor = argmin(nodes, key=distance_to_node)
  1104. d = distance(g.locations[neighbor], here) * curvature()
  1105. g.connect(node, neighbor, int(d))
  1106. return g
  1107.  
  1108.  
  1109.  
  1110. class GraphProblem(Problem):
  1111.  
  1112. """The problem of searching a graph from one node to another."""
  1113.  
  1114. def __init__(self, initial, goal, graph):
  1115. Problem.__init__(self, initial, goal)
  1116. self.graph = graph
  1117.  
  1118. def actions(self, A):
  1119. """The actions at a graph node are just its neighbors."""
  1120. return list(self.graph.get(A).keys())
  1121.  
  1122. def result(self, state, action):
  1123. """The result of going to a neighbor is just that neighbor."""
  1124. return action
  1125.  
  1126. def path_cost(self, cost_so_far, A, action, B):
  1127. return cost_so_far + (self.graph.get(A, B) or infinity)
  1128.  
  1129. def h(self, node):
  1130. """h function is straight-line distance from a node's state to goal."""
  1131. locs = getattr(self.graph, 'locations', None)
  1132. if locs:
  1133. return int(distance(locs[node.state], locs[self.goal]))
  1134. else:
  1135. return infinity
  1136.  
  1137. Pocetok = input()
  1138. Stanica1 = input()
  1139. Stanica2 = input()
  1140. Kraj = input()
  1141.  
  1142. ABdistance=distance((2,1),(2,4))
  1143. BIdistance=distance((2,4),(8,5))
  1144. BCdistance=distance((2,4),(2,10))
  1145. HIdistance=distance((8,1),(8,5))
  1146. IJdistance=distance((8,5),(8,8))
  1147. FCdistance=distance((5,9),(2,10))
  1148. GCdistance=distance((4,11),(2,10))
  1149. CDdistance=distance((2,10),(2,15))
  1150. FGdistance=distance((5,9),(4,11))
  1151. FJdistance=distance((5,9),(8,8))
  1152. KGdistance=distance((8,13),(4,11))
  1153. LKdistance=distance((8,15),(8,13))
  1154. DEdistance=distance((2,15),(2,19))
  1155. DLdistance=distance((2,15),(8,15))
  1156. LMdistance=distance((8,15),(8,19))
  1157.  
  1158. graph = UndirectedGraph({
  1159. "B": {"A": ABdistance, "I": BIdistance, "C": BCdistance},
  1160. "I": {"H": HIdistance, "J": IJdistance},
  1161. "C": {"F": FCdistance, "G": GCdistance, "D": CDdistance},
  1162. "F": {"G": FGdistance, "J": FJdistance},
  1163. "K": {"G": KGdistance, "L": LKdistance},
  1164. "D": {"E": DEdistance, "L": DLdistance},
  1165. "M": {"L": LMdistance}
  1166. })
  1167.  
  1168.  
  1169. graph.locations = dict(
  1170. A = (2,1) , B = (2,4) , C = (2,10) ,
  1171. D = (2,15) , E = (2,19) , F = (5,9) ,
  1172. G = (4,11) , H = (8,1) , I = (8,5),
  1173. J = (8,8) , K = (8,13) , L = (8,15),
  1174. M = (8,19))
  1175.  
  1176. graphproblem1=GraphProblem(Pocetok,Stanica1,graph)
  1177. rez1=astar_search(graphproblem1).solve()
  1178. graphproblem2=GraphProblem(Stanica1, Kraj,graph)
  1179. rez2=astar_search(graphproblem2).solve()
  1180.  
  1181. pat1=rez1+rez2[1:len(rez2)]
  1182.  
  1183. graphproblem1=GraphProblem(Pocetok,Stanica2,graph)
  1184. rez1=astar_search(graphproblem1).solve()
  1185. graphproblem2=GraphProblem(Stanica2, Kraj,graph)
  1186. rez2=astar_search(graphproblem2).solve()
  1187.  
  1188. pat2=rez1+rez2[1:len(rez2)]
  1189.  
  1190. if len(pat1)<=len(pat2):
  1191. if Stanica2 in pat1:
  1192. print pat2
  1193. else:
  1194. print pat1
  1195. else:
  1196. print pat2
  1197. **********drva na odluka*************
  1198. trainingData=[
  1199. [6.3,2.9,5.6,1.8,'I. virginica'],
  1200. [6.5,3.0,5.8,2.2,'I. virginica'],
  1201. [7.6,3.0,6.6,2.1,'I. virginica'],
  1202. [4.9,2.5,4.5,1.7,'I. virginica'],
  1203. [7.3,2.9,6.3,1.8,'I. virginica'],
  1204. [6.7,2.5,5.8,1.8,'I. virginica'],
  1205. [7.2,3.6,6.1,2.5,'I. virginica'],
  1206. [6.5,3.2,5.1,2.0,'I. virginica'],
  1207. [6.4,2.7,5.3,1.9,'I. virginica'],
  1208. [6.8,3.0,5.5,2.1,'I. virginica'],
  1209. [5.7,2.5,5.0,2.0,'I. virginica'],
  1210. [5.8,2.8,5.1,2.4,'I. virginica'],
  1211. [6.4,3.2,5.3,2.3,'I. virginica'],
  1212. [6.5,3.0,5.5,1.8,'I. virginica'],
  1213. [7.7,3.8,6.7,2.2,'I. virginica'],
  1214. [7.7,2.6,6.9,2.3,'I. virginica'],
  1215. [6.0,2.2,5.0,1.5,'I. virginica'],
  1216. [6.9,3.2,5.7,2.3,'I. virginica'],
  1217. [5.6,2.8,4.9,2.0,'I. virginica'],
  1218. [7.7,2.8,6.7,2.0,'I. virginica'],
  1219. [6.3,2.7,4.9,1.8,'I. virginica'],
  1220. [6.7,3.3,5.7,2.1,'I. virginica'],
  1221. [7.2,3.2,6.0,1.8,'I. virginica'],
  1222. [6.2,2.8,4.8,1.8,'I. virginica'],
  1223. [6.1,3.0,4.9,1.8,'I. virginica'],
  1224. [6.4,2.8,5.6,2.1,'I. virginica'],
  1225. [7.2,3.0,5.8,1.6,'I. virginica'],
  1226. [7.4,2.8,6.1,1.9,'I. virginica'],
  1227. [7.9,3.8,6.4,2.0,'I. virginica'],
  1228. [6.4,2.8,5.6,2.2,'I. virginica'],
  1229. [6.3,2.8,5.1,1.5,'I. virginica'],
  1230. [6.1,2.6,5.6,1.4,'I. virginica'],
  1231. [7.7,3.0,6.1,2.3,'I. virginica'],
  1232. [6.3,3.4,5.6,2.4,'I. virginica'],
  1233. [5.1,3.5,1.4,0.2,'I. setosa'],
  1234. [4.9,3.0,1.4,0.2,'I. setosa'],
  1235. [4.7,3.2,1.3,0.2,'I. setosa'],
  1236. [4.6,3.1,1.5,0.2,'I. setosa'],
  1237. [5.0,3.6,1.4,0.2,'I. setosa'],
  1238. [5.4,3.9,1.7,0.4,'I. setosa'],
  1239. [4.6,3.4,1.4,0.3,'I. setosa'],
  1240. [5.0,3.4,1.5,0.2,'I. setosa'],
  1241. [4.4,2.9,1.4,0.2,'I. setosa'],
  1242. [4.9,3.1,1.5,0.1,'I. setosa'],
  1243. [5.4,3.7,1.5,0.2,'I. setosa'],
  1244. [4.8,3.4,1.6,0.2,'I. setosa'],
  1245. [4.8,3.0,1.4,0.1,'I. setosa'],
  1246. [4.3,3.0,1.1,0.1,'I. setosa'],
  1247. [5.8,4.0,1.2,0.2,'I. setosa'],
  1248. [5.7,4.4,1.5,0.4,'I. setosa'],
  1249. [5.4,3.9,1.3,0.4,'I. setosa'],
  1250. [5.1,3.5,1.4,0.3,'I. setosa'],
  1251. [5.7,3.8,1.7,0.3,'I. setosa'],
  1252. [5.1,3.8,1.5,0.3,'I. setosa'],
  1253. [5.4,3.4,1.7,0.2,'I. setosa'],
  1254. [5.1,3.7,1.5,0.4,'I. setosa'],
  1255. [4.6,3.6,1.0,0.2,'I. setosa'],
  1256. [5.1,3.3,1.7,0.5,'I. setosa'],
  1257. [4.8,3.4,1.9,0.2,'I. setosa'],
  1258. [5.0,3.0,1.6,0.2,'I. setosa'],
  1259. [5.0,3.4,1.6,0.4,'I. setosa'],
  1260. [5.2,3.5,1.5,0.2,'I. setosa'],
  1261. [5.2,3.4,1.4,0.2,'I. setosa'],
  1262. [5.5,2.3,4.0,1.3,'I. versicolor'],
  1263. [6.5,2.8,4.6,1.5,'I. versicolor'],
  1264. [5.7,2.8,4.5,1.3,'I. versicolor'],
  1265. [6.3,3.3,4.7,1.6,'I. versicolor'],
  1266. [4.9,2.4,3.3,1.0,'I. versicolor'],
  1267. [6.6,2.9,4.6,1.3,'I. versicolor'],
  1268. [5.2,2.7,3.9,1.4,'I. versicolor'],
  1269. [5.0,2.0,3.5,1.0,'I. versicolor'],
  1270. [5.9,3.0,4.2,1.5,'I. versicolor'],
  1271. [6.0,2.2,4.0,1.0,'I. versicolor'],
  1272. [6.1,2.9,4.7,1.4,'I. versicolor'],
  1273. [5.6,2.9,3.6,1.3,'I. versicolor'],
  1274. [6.7,3.1,4.4,1.4,'I. versicolor'],
  1275. [5.6,3.0,4.5,1.5,'I. versicolor'],
  1276. [5.8,2.7,4.1,1.0,'I. versicolor'],
  1277. [6.2,2.2,4.5,1.5,'I. versicolor'],
  1278. [5.6,2.5,3.9,1.1,'I. versicolor'],
  1279. [5.9,3.2,4.8,1.8,'I. versicolor'],
  1280. [6.1,2.8,4.0,1.3,'I. versicolor'],
  1281. [6.3,2.5,4.9,1.5,'I. versicolor'],
  1282. [6.1,2.8,4.7,1.2,'I. versicolor'],
  1283. [6.4,2.9,4.3,1.3,'I. versicolor'],
  1284. [6.6,3.0,4.4,1.4,'I. versicolor'],
  1285. [6.8,2.8,4.8,1.4,'I. versicolor'],
  1286. [6.7,3.0,5.0,1.7,'I. versicolor'],
  1287. [6.0,2.9,4.5,1.5,'I. versicolor'],
  1288. [5.7,2.6,3.5,1.0,'I. versicolor'],
  1289. [5.5,2.4,3.8,1.1,'I. versicolor'],
  1290. [5.5,2.4,3.7,1.0,'I. versicolor'],
  1291. [5.8,2.7,3.9,1.2,'I. versicolor'],
  1292. [6.0,2.7,5.1,1.6,'I. versicolor'],
  1293. [5.4,3.0,4.5,1.5,'I. versicolor'],
  1294. [6.0,3.4,4.5,1.6,'I. versicolor'],
  1295. [6.7,3.1,4.7,1.5,'I. versicolor'],
  1296. [6.3,2.3,4.4,1.3,'I. versicolor'],
  1297. [5.6,3.0,4.1,1.3,'I. versicolor'],
  1298. [5.5,2.5,4.0,1.3,'I. versicolor'],
  1299. [5.5,2.6,4.4,1.2,'I. versicolor'],
  1300. [6.1,3.0,4.6,1.4,'I. versicolor'],
  1301. [5.8,2.6,4.0,1.2,'I. versicolor'],
  1302. [5.0,2.3,3.3,1.0,'I. versicolor'],
  1303. [5.6,2.7,4.2,1.3,'I. versicolor'],
  1304. [5.7,3.0,4.2,1.2,'I. versicolor'],
  1305. [5.7,2.9,4.2,1.3,'I. versicolor'],
  1306. [6.2,2.9,4.3,1.3,'I. versicolor'],
  1307. [5.1,2.5,3.0,1.1,'I. versicolor'],
  1308. [5.7,2.8,4.1,1.3,'I. versicolor'],
  1309. [6.4,3.1,5.5,1.8,'I. virginica'],
  1310. [6.0,3.0,4.8,1.8,'I. virginica'],
  1311. [6.9,3.1,5.4,2.1,'I. virginica'],
  1312. [6.7,3.1,5.6,2.4,'I. virginica'],
  1313. [6.9,3.1,5.1,2.3,'I. virginica'],
  1314. [5.8,2.7,5.1,1.9,'I. virginica'],
  1315. [6.8,3.2,5.9,2.3,'I. virginica'],
  1316. [6.7,3.3,5.7,2.5,'I. virginica'],
  1317. [6.7,3.0,5.2,2.3,'I. virginica'],
  1318. [6.3,2.5,5.0,1.9,'I. virginica'],
  1319. [6.5,3.0,5.2,2.0,'I. virginica'],
  1320. [6.2,3.4,5.4,2.3,'I. virginica'],
  1321. [4.7,3.2,1.6,0.2,'I. setosa'],
  1322. [4.8,3.1,1.6,0.2,'I. setosa'],
  1323. [5.4,3.4,1.5,0.4,'I. setosa'],
  1324. [5.2,4.1,1.5,0.1,'I. setosa'],
  1325. [5.5,4.2,1.4,0.2,'I. setosa'],
  1326. [4.9,3.1,1.5,0.2,'I. setosa'],
  1327. [5.0,3.2,1.2,0.2,'I. setosa'],
  1328. [5.5,3.5,1.3,0.2,'I. setosa'],
  1329. [4.9,3.6,1.4,0.1,'I. setosa'],
  1330. [4.4,3.0,1.3,0.2,'I. setosa'],
  1331. [5.1,3.4,1.5,0.2,'I. setosa'],
  1332. [5.0,3.5,1.3,0.3,'I. setosa'],
  1333. [4.5,2.3,1.3,0.3,'I. setosa'],
  1334. [4.4,3.2,1.3,0.2,'I. setosa'],
  1335. [5.0,3.5,1.6,0.6,'I. setosa'],
  1336. [5.1,3.8,1.9,0.4,'I. setosa'],
  1337. [4.8,3.0,1.4,0.3,'I. setosa'],
  1338. [5.1,3.8,1.6,0.2,'I. setosa'],
  1339. [5.9,3.0,5.1,1.8,'I. virginica']
  1340. ]
  1341.  
  1342.  
  1343.  
  1344.  
  1345. class decisionnode:
  1346. def __init__(self,col=-1,value=None,results=None,tb=None,fb=None, level=0):
  1347. self.col=col
  1348. self.value=value
  1349. self.results=results
  1350. self.tb=tb
  1351. self.fb=fb
  1352. self.level=level
  1353.  
  1354.  
  1355. def sporedi_broj(row,column,value):
  1356. return row[column]>=value
  1357.  
  1358. def sporedi_string(row,column,value):
  1359. return row[column]==value
  1360.  
  1361. # Divides a set on a specific column. Can handle numeric
  1362. # or nominal values
  1363. def divideset(rows,column,value):
  1364. # Make a function that tells us if a row is in
  1365. # the first group (true) or the second group (false)
  1366. split_function=None
  1367. if isinstance(value,int) or isinstance(value,float): # ako vrednosta so koja sporeduvame e od tip int ili float
  1368. #split_function=lambda row:row[column]>=value # togas vrati funkcija cij argument e row i vrakja vrednost true ili false
  1369. split_function=sporedi_broj
  1370. else:
  1371. # split_function=lambda row:row[column]==value # ako vrednosta so koja sporeduvame e od drug tip (string)
  1372. split_function=sporedi_string
  1373.  
  1374. # Divide the rows into two sets and return them
  1375. # set1=[row for row in rows if split_function(row)] # za sekoj row od rows za koj split_function vrakja true
  1376. # set2=[row for row in rows if not split_function(row)] # za sekoj row od rows za koj split_function vrakja false
  1377. set1=[row for row in rows if split_function(row,column,value)] # za sekoj row od rows za koj split_function vrakja true
  1378. set2=[row for row in rows if not split_function(row,column,value)] # za sekoj row od rows za koj split_function vrakja false
  1379. return (set1,set2)
  1380.  
  1381. # Create counts of possible results (the last column of
  1382. # each row is the result)
  1383. def uniquecounts(rows):
  1384. results={}
  1385. for row in rows:
  1386. # The result is the last column
  1387. r=row[len(row)-1]
  1388. if r not in results: results[r]=0
  1389. results[r]+=1
  1390. return results
  1391.  
  1392. # Probability that a randomly placed item will
  1393. # be in the wrong category
  1394. def giniimpurity(rows):
  1395. total=len(rows)
  1396. counts=uniquecounts(rows)
  1397. imp=0
  1398. for k1 in counts:
  1399. p1=float(counts[k1])/total
  1400. for k2 in counts:
  1401. if k1==k2: continue
  1402. p2=float(counts[k2])/total
  1403. imp+=p1*p2
  1404. return imp
  1405.  
  1406.  
  1407. # Entropy is the sum of p(x)log(p(x)) across all
  1408. # the different possible results
  1409. def entropy(rows):
  1410. from math import log
  1411. log2=lambda x:log(x)/log(2)
  1412. results=uniquecounts(rows)
  1413. # Now calculate the entropy
  1414. ent=0.0
  1415. for r in results.keys():
  1416. p=float(results[r])/len(rows)
  1417. ent=ent-p*log2(p)
  1418. return ent
  1419.  
  1420. def buildtree(rows,scoref=entropy,level=0):
  1421. if len(rows)==0: return decisionnode()
  1422. current_score=scoref(rows)
  1423. # Set up some variables to track the best criteria
  1424. best_gain=0.0
  1425. best_criteria=None
  1426. best_sets=None
  1427. column_count=len(rows[0])-1
  1428. for col in range(0,column_count):
  1429. # Generate the list of different values in
  1430. # this column
  1431. column_values={}
  1432. for row in rows:
  1433. column_values[row[col]]=1
  1434. # Now try dividing the rows up for each value
  1435. # in this column
  1436. for value in column_values.keys():
  1437. (set1,set2)=divideset(rows,col,value)
  1438. # Information gain
  1439. p=float(len(set1))/len(rows)
  1440. gain=current_score-p*scoref(set1)-(1-p)*scoref(set2)
  1441. if gain>best_gain and len(set1)>0 and len(set2)>0:
  1442. best_gain=gain
  1443. best_criteria=(col,value)
  1444. best_sets=(set1,set2)
  1445. # Create the subbranches
  1446. if best_gain>0:
  1447. trueBranch=buildtree(best_sets[0], level=level+1)
  1448. falseBranch=buildtree(best_sets[1], level=level+1)
  1449. return decisionnode(col=best_criteria[0],value=best_criteria[1],
  1450. tb=trueBranch, fb=falseBranch, level=level)
  1451. else:
  1452. return decisionnode(results=uniquecounts(rows))
  1453.  
  1454. def printtree(tree,indent=''):
  1455. # Is this a leaf node?
  1456. if tree.results!=None:
  1457. print (str(tree.results))
  1458. else:
  1459. # Print the criteria
  1460. print (str(tree.col)+':'+str(tree.value)+'? ' + 'Level='+ str(tree.level))
  1461. # Print the branches
  1462. print (indent+'T->',
  1463. printtree(tree.tb,indent+' '))
  1464. print (indent+'F->',
  1465. printtree(tree.fb,indent+' '))
  1466.  
  1467. def classify(observation, tree):
  1468. if tree.results != None:
  1469. if len(tree.results.keys()) == 1: #edna klasa
  1470. return tree.results.keys()[0]
  1471. else: #so njgolem br instanci
  1472. max = 0
  1473. best = None
  1474. for i in tree.results.keys():
  1475. if tree.results[i] > max:
  1476. max = tree.results[i]
  1477. best = i
  1478. elif tree.results[i] == max and i < best:
  1479. best = i
  1480. return best
  1481.  
  1482. else:
  1483. vrednost = observation[tree.col]
  1484. branch = None
  1485.  
  1486. if isinstance(vrednost, int) or isinstance(vrednost, float):
  1487. if vrednost >= tree.value:
  1488. branch = tree.tb
  1489. else:
  1490. branch = tree.fb
  1491. else:
  1492. if vrednost == tree.value:
  1493. branch = tree.tb
  1494. else:
  1495. branch = tree.fb
  1496.  
  1497. return classify(observation, branch)
  1498.  
  1499.  
  1500.  
  1501. if __name__ == "__main__":
  1502.  
  1503.  
  1504. att1=input()
  1505. att2=input()
  1506. att3=input()
  1507. att4=input()
  1508. planttype=input()
  1509. testCase=[att1,att2,att3,att4,planttype]
  1510.  
  1511. t1=[]
  1512. lenght=len(trainingData)
  1513. for i in range (0,lenght/2):
  1514. t1.append(trainingData[i])
  1515. t2=[]
  1516. for i in range(lenght/2,lenght):
  1517. t2.append(trainingData[i])
  1518.  
  1519. tree1=buildtree(t1)
  1520. tree2=buildtree(t2)
  1521.  
  1522. tree1_class=classify(testCase,tree1)
  1523. tree2_class=classify(testCase,tree2)
  1524.  
  1525. if tree1_class==tree2_class:
  1526. print (tree1_class)
  1527. else:
  1528. print ("KONTRADIKCIJA")
  1529.  
  1530.  
  1531. *************informirano podvizni prepreki****
  1532. # Python modul vo koj se implementirani algoritmite za informirano prebaruvanje
  1533.  
  1534. # ______________________________________________________________________________________________
  1535. # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
  1536.  
  1537. import sys
  1538. import bisect
  1539.  
  1540. infinity = float('inf') # sistemski definirana vrednost za beskonecnost
  1541.  
  1542.  
  1543. # ______________________________________________________________________________________________
  1544. # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
  1545.  
  1546. class Queue:
  1547. """Queue is an abstract class/interface. There are three types:
  1548. Stack(): A Last In First Out Queue.
  1549. FIFOQueue(): A First In First Out Queue.
  1550. PriorityQueue(order, f): Queue in sorted order (default min-first).
  1551. Each type supports the following methods and functions:
  1552. q.append(item) -- add an item to the queue
  1553. q.extend(items) -- equivalent to: for item in items: q.append(item)
  1554. q.pop() -- return the top item from the queue
  1555. len(q) -- number of items in q (also q.__len())
  1556. item in q -- does q contain item?
  1557. Note that isinstance(Stack(), Queue) is false, because we implement stacks
  1558. as lists. If Python ever gets interfaces, Queue will be an interface."""
  1559.  
  1560. def __init__(self):
  1561. raise NotImplementedError
  1562.  
  1563. def extend(self, items):
  1564. for item in items:
  1565. self.append(item)
  1566.  
  1567.  
  1568. def Stack():
  1569. """A Last-In-First-Out Queue."""
  1570. return []
  1571.  
  1572.  
  1573. class FIFOQueue(Queue):
  1574. """A First-In-First-Out Queue."""
  1575.  
  1576. def __init__(self):
  1577. self.A = []
  1578. self.start = 0
  1579.  
  1580. def append(self, item):
  1581. self.A.append(item)
  1582.  
  1583. def __len__(self):
  1584. return len(self.A) - self.start
  1585.  
  1586. def extend(self, items):
  1587. self.A.extend(items)
  1588.  
  1589. def pop(self):
  1590. e = self.A[self.start]
  1591. self.start += 1
  1592. if self.start > 5 and self.start > len(self.A) / 2:
  1593. self.A = self.A[self.start:]
  1594. self.start = 0
  1595. return e
  1596.  
  1597. def __contains__(self, item):
  1598. return item in self.A[self.start:]
  1599.  
  1600.  
  1601. class PriorityQueue(Queue):
  1602. """A queue in which the minimum (or maximum) element (as determined by f and
  1603. order) is returned first. If order is min, the item with minimum f(x) is
  1604. returned first; if order is max, then it is the item with maximum f(x).
  1605. Also supports dict-like lookup. This structure will be most useful in informed searches"""
  1606.  
  1607. def __init__(self, order=min, f=lambda x: x):
  1608. self.A = []
  1609. self.order = order
  1610. self.f = f
  1611.  
  1612. def append(self, item):
  1613. bisect.insort(self.A, (self.f(item), item))
  1614.  
  1615. def __len__(self):
  1616. return len(self.A)
  1617.  
  1618. def pop(self):
  1619. if self.order == min:
  1620. return self.A.pop(0)[1]
  1621. else:
  1622. return self.A.pop()[1]
  1623.  
  1624. def __contains__(self, item):
  1625. return any(item == pair[1] for pair in self.A)
  1626.  
  1627. def __getitem__(self, key):
  1628. for _, item in self.A:
  1629. if item == key:
  1630. return item
  1631.  
  1632. def __delitem__(self, key):
  1633. for i, (value, item) in enumerate(self.A):
  1634. if item == key:
  1635. self.A.pop(i)
  1636.  
  1637.  
  1638. # ______________________________________________________________________________________________
  1639. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  1640. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  1641. # na sekoj eden problem sto sakame da go resime
  1642.  
  1643.  
  1644. class Problem:
  1645. """The abstract class for a formal problem. You should subclass this and
  1646. implement the method successor, and possibly __init__, goal_test, and
  1647. path_cost. Then you will create instances of your subclass and solve them
  1648. with the various search functions."""
  1649.  
  1650. def __init__(self, initial, goal=None):
  1651. """The constructor specifies the initial state, and possibly a goal
  1652. state, if there is a unique goal. Your subclass's constructor can add
  1653. other arguments."""
  1654. self.initial = initial
  1655. self.goal = goal
  1656.  
  1657. def successor(self, state):
  1658. """Given a state, return a dictionary of {action : state} pairs reachable
  1659. from this state. If there are many successors, consider an iterator
  1660. that yields the successors one at a time, rather than building them
  1661. all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  1662. raise NotImplementedError
  1663.  
  1664. def actions(self, state):
  1665. """Given a state, return a list of all actions possible from that state"""
  1666. raise NotImplementedError
  1667.  
  1668. def result(self, state, action):
  1669. """Given a state and action, return the resulting state"""
  1670. raise NotImplementedError
  1671.  
  1672. def goal_test(self, state):
  1673. """Return True if the state is a goal. The default method compares the
  1674. state to self.goal, as specified in the constructor. Implement this
  1675. method if checking against a single self.goal is not enough."""
  1676. return state == self.goal
  1677.  
  1678. def path_cost(self, c, state1, action, state2):
  1679. """Return the cost of a solution path that arrives at state2 from
  1680. state1 via action, assuming cost c to get up to state1. If the problem
  1681. is such that the path doesn't matter, this function will only look at
  1682. state2. If the path does matter, it will consider c and maybe state1
  1683. and action. The default method costs 1 for every step in the path."""
  1684. return c + 1
  1685.  
  1686. def value(self):
  1687. """For optimization problems, each state has a value. Hill-climbing
  1688. and related algorithms try to maximize this value."""
  1689. raise NotImplementedError
  1690.  
  1691.  
  1692. # ______________________________________________________________________________
  1693. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  1694. # Klasata Node ne se nasleduva
  1695.  
  1696. class Node:
  1697. """A node in a search tree. Contains a pointer to the parent (the node
  1698. that this is a successor of) and to the actual state for this node. Note
  1699. that if a state is arrived at by two paths, then there are two nodes with
  1700. the same state. Also includes the action that got us to this state, and
  1701. the total path_cost (also known as g) to reach the node. Other functions
  1702. may add an f and h value; see best_first_graph_search and astar_search for
  1703. an explanation of how the f and h values are handled. You will not need to
  1704. subclass this class."""
  1705.  
  1706. def __init__(self, state, parent=None, action=None, path_cost=0):
  1707. "Create a search tree Node, derived from a parent by an action."
  1708. self.state = state
  1709. self.parent = parent
  1710. self.action = action
  1711. self.path_cost = path_cost
  1712. self.depth = 0
  1713. if parent:
  1714. self.depth = parent.depth + 1
  1715.  
  1716. def __repr__(self):
  1717. return "<Node %s>" % (self.state,)
  1718.  
  1719. def __lt__(self, node):
  1720. return self.state < node.state
  1721.  
  1722. def expand(self, problem):
  1723. "List the nodes reachable in one step from this node."
  1724. return [self.child_node(problem, action)
  1725. for action in problem.actions(self.state)]
  1726.  
  1727. def child_node(self, problem, action):
  1728. "Return a child node from this node"
  1729. next = problem.result(self.state, action)
  1730. return Node(next, self, action,
  1731. problem.path_cost(self.path_cost, self.state,
  1732. action, next))
  1733.  
  1734. def solution(self):
  1735. "Return the sequence of actions to go from the root to this node."
  1736. return [node.action for node in self.path()[1:]]
  1737.  
  1738. def solve(self):
  1739. "Return the sequence of states to go from the root to this node."
  1740. return [node.state for node in self.path()[0:]]
  1741.  
  1742. def path(self):
  1743. "Return a list of nodes forming the path from the root to this node."
  1744. x, result = self, []
  1745. while x:
  1746. result.append(x)
  1747. x = x.parent
  1748. return list(reversed(result))
  1749.  
  1750. # We want for a queue of nodes in breadth_first_search or
  1751. # astar_search to have no duplicated states, so we treat nodes
  1752. # with the same state as equal. [Problem: this may not be what you
  1753. # want in other contexts.]
  1754.  
  1755. def __eq__(self, other):
  1756. return isinstance(other, Node) and self.state == other.state
  1757.  
  1758. def __hash__(self):
  1759. return hash(self.state)
  1760.  
  1761.  
  1762.  
  1763. # ________________________________________________________________________________________________________
  1764. #Pomosna funkcija za informirani prebaruvanja
  1765. #So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
  1766.  
  1767. def memoize(fn, slot=None):
  1768. """Memoize fn: make it remember the computed value for any argument list.
  1769. If slot is specified, store result in that slot of first argument.
  1770. If slot is false, store results in a dictionary."""
  1771. if slot:
  1772. def memoized_fn(obj, *args):
  1773. if hasattr(obj, slot):
  1774. return getattr(obj, slot)
  1775. else:
  1776. val = fn(obj, *args)
  1777. setattr(obj, slot, val)
  1778. return val
  1779. else:
  1780. def memoized_fn(*args):
  1781. if not memoized_fn.cache.has_key(args):
  1782. memoized_fn.cache[args] = fn(*args)
  1783. return memoized_fn.cache[args]
  1784.  
  1785. memoized_fn.cache = {}
  1786. return memoized_fn
  1787.  
  1788.  
  1789. # ________________________________________________________________________________________________________
  1790. #Informirano prebaruvanje vo ramki na graf
  1791.  
  1792. def best_first_graph_search(problem, f):
  1793. """Search the nodes with the lowest f scores first.
  1794. You specify the function f(node) that you want to minimize; for example,
  1795. if f is a heuristic estimate to the goal, then we have greedy best
  1796. first search; if f is node.depth then we have breadth-first search.
  1797. There is a subtlety: the line "f = memoize(f, 'f')" means that the f
  1798. values will be cached on the nodes as they are computed. So after doing
  1799. a best first search you can examine the f values of the path returned."""
  1800.  
  1801. f = memoize(f, 'f')
  1802. node = Node(problem.initial)
  1803. if problem.goal_test(node.state):
  1804. return node
  1805. frontier = PriorityQueue(min, f)
  1806. frontier.append(node)
  1807. explored = set()
  1808. while frontier:
  1809. node = frontier.pop()
  1810. if problem.goal_test(node.state):
  1811. return node
  1812. explored.add(node.state)
  1813. for child in node.expand(problem):
  1814. if child.state not in explored and child not in frontier:
  1815. frontier.append(child)
  1816. elif child in frontier:
  1817. incumbent = frontier[child]
  1818. if f(child) < f(incumbent):
  1819. del frontier[incumbent]
  1820. frontier.append(child)
  1821. return None
  1822.  
  1823.  
  1824. def greedy_best_first_graph_search(problem, h=None):
  1825. "Greedy best-first search is accomplished by specifying f(n) = h(n)"
  1826. h = memoize(h or problem.h, 'h')
  1827. return best_first_graph_search(problem, h)
  1828.  
  1829.  
  1830. def astar_search(problem, h=None):
  1831. "A* search is best-first graph search with f(n) = g(n)+h(n)."
  1832. h = memoize(h or problem.h, 'h')
  1833. return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
  1834.  
  1835.  
  1836. # ________________________________________________________________________________________________________
  1837. #Dopolnitelni prebaruvanja
  1838. #Recursive_best_first_search e implementiran
  1839. #Kako zadaca za studentite da gi implementiraat SMA* i IDA*
  1840.  
  1841. def recursive_best_first_search(problem, h=None):
  1842. h = memoize(h or problem.h, 'h')
  1843.  
  1844. def RBFS(problem, node, flimit):
  1845. if problem.goal_test(node.state):
  1846. return node, 0 # (The second value is immaterial)
  1847. successors = node.expand(problem)
  1848. if len(successors) == 0:
  1849. return None, infinity
  1850. for s in successors:
  1851. s.f = max(s.path_cost + h(s), node.f)
  1852. while True:
  1853. # Order by lowest f value
  1854. successors.sort(key=lambda x: x.f)
  1855. best = successors[0]
  1856. if best.f > flimit:
  1857. return None, best.f
  1858. if len(successors) > 1:
  1859. alternative = successors[1].f
  1860. else:
  1861. alternative = infinity
  1862. result, best.f = RBFS(problem, best, min(flimit, alternative))
  1863. if result is not None:
  1864. return result, best.f
  1865.  
  1866. node = Node(problem.initial)
  1867. node.f = h(node)
  1868. result, bestf = RBFS(problem, node, infinity)
  1869. return result
  1870.  
  1871.  
  1872.  
  1873. # _________________________________________________________________________________________________________
  1874. #PRIMER 2 : PROBLEM NA SLOZUVALKA
  1875. #OPIS: Dadena e slozuvalka 3x3 na koja ima polinja so brojki od 1 do 8 i edno prazno pole
  1876. # Praznoto pole e obelezano so *. Eden primer na slozuvalka e daden vo prodolzenie:
  1877. # -------------
  1878. # | * | 3 | 2 |
  1879. # |---|---|---|
  1880. # | 4 | 1 | 5 |
  1881. # |---|---|---|
  1882. # | 6 | 7 | 8 |
  1883. # -------------
  1884. #Problemot e kako da se stigne do nekoja pocetna raspredelba na polinjata do nekoja posakuvana, na primer do:
  1885. # -------------
  1886. # | * | 1 | 2 |
  1887. # |---|---|---|
  1888. # | 3 | 4 | 5 |
  1889. # |---|---|---|
  1890. # | 6 | 7 | 8 |
  1891. # -------------
  1892. #AKCII: Akciite ke gi gledame kako dvizenje na praznoto pole, pa mozni akcii se : gore, dole, levo i desno.
  1893. #Pri definiranjeto na akciite mora da se vnimava dali akciite voopsto mozat da se prevzemat vo dadenata slozuvalka
  1894. #STATE: Sostojbata ke ja definirame kako string koj ke ima 9 karakteri (po eden za sekoe brojce plus za *)
  1895. #pri sto stringot ke se popolnuva so izminuvanje na slozuvalkata od prviot kon tretiot red, od levo kon desno.
  1896. # Na primer sostojbata za pocetnata slozuvalka e: '*32415678'
  1897. # Sostojbata za finalnata slozuvalka e: '*12345678'
  1898. # ________________________________________________________________________________________________________
  1899. #
  1900.  
  1901. default_goal = '*12345678' #predefinirana cel
  1902.  
  1903. #Ke definirame 3 klasi za problemot
  1904. #Prvata klasa nema implementirano nikakva hevristika
  1905.  
  1906. class P8(Problem):
  1907.  
  1908. name = 'No Heuristic'
  1909.  
  1910. def __init__(self, goal=default_goal, initial=None, N=20):
  1911. self.goal = goal
  1912. self.initial = initial
  1913.  
  1914. def successor(self, state):
  1915. return successor8(state)
  1916.  
  1917. def actions(self, state):
  1918. return self.successor(state).keys()
  1919.  
  1920. def h(self, node):
  1921. """Heuristic for 8 puzzle: returns 0"""
  1922. return 0
  1923.  
  1924. def result(self, state, action):
  1925. possible = self.successor(state)
  1926. return possible[action]
  1927.  
  1928. #Slednite klasi ke nasleduvaat od prethodnata bez hevristika so toa sto ovde ke ja definirame i hevristikata
  1929.  
  1930. class P8_h1(P8):
  1931. """ Slozuvalka so hevristika
  1932. HEVRISTIKA: Brojot na polinja koi ne se na vistinskoto mesto"""
  1933.  
  1934. name = 'Out of Place Heuristic'
  1935.  
  1936. def h(self, node):
  1937. """Funkcija koja ja presmetuva hevristikata,
  1938. t.e. razlikata pomegu nekoj tekoven jazel od prebaruvanjeto i celniot jazel"""
  1939. matches = 0
  1940. for (t1, t2) in zip(node.state, self.goal):
  1941. #zip funkcijata od dve listi na vlez pravi edna lista od parovi (torki)
  1942. #primer: zip(['a','b','c'],[1,2,3]) == [('a',1),('b',2),('c',3)]
  1943. # zip('abc','123') == [('a','1'),('b','2'),('c','3')]
  1944. if t1 != t2:
  1945. matches = + 1
  1946. return matches
  1947.  
  1948.  
  1949. class P8_h2(P8):
  1950. """ Slozuvalka so hevristika
  1951. HEVRISTIKA: Menheten rastojanie do celna sostojba"""
  1952.  
  1953. name = 'Manhattan Distance Heuristic (MHD)'
  1954.  
  1955. def h(self, node):
  1956. """Funkcija koja ja presmetuva hevristikata,
  1957. t.e. Menheten rastojanieto pomegu nekoj tekoven jazel od prebaruvanjeto i celniot jazel, pri sto
  1958. Menheten rastojanieto megu jazlite e zbir od Menheten rastojanijata pomegu istite broevi vo dvata jazli"""
  1959. sum = 0
  1960. for c in '12345678':
  1961. sum = + mhd(node.state.index(c), self.goal.index(c)) #pomosna funkcija definirana vo prodolzenie
  1962. return sum
  1963.  
  1964.  
  1965. # Za da mozeme da go definirame rastojanieto treba da definirame koordinaten sistem
  1966. # Pozetokot na koordinatniot sistem e postaven vo gorniot lev agol na slozuvalkata
  1967. # Definirame recnik za koordinatite na sekoe pole od slozuvalkata
  1968. coordinates = {0: (0, 0), 1: (1, 0), 2: (2, 0),
  1969. 3: (0, 1), 4: (1, 1), 5: (2, 1),
  1970. 6: (0, 2), 7: (1, 2), 8: (2, 2)}
  1971.  
  1972. #Funkcija koja presmetuva Menheten rastojanie za slozuvalkata
  1973. #Na vlez dobiva dva celi broja koi odgovaraat na dve polinja na koi se naogaat broevite za koi treba da presmetame rastojanie
  1974. def mhd(n, m):
  1975. x1, y1 = coordinates[n]
  1976. x2, y2 = coordinates[m]
  1977. return abs(x1 - x2) + abs(y1 - y2)
  1978.  
  1979.  
  1980.  
  1981. def successor8(S):
  1982. """Pomosna funkcija koja generira recnik za sledbenicite na daden jazel"""
  1983.  
  1984. blank = S.index('*') #kade se naoga praznoto pole
  1985.  
  1986. succs = {}
  1987.  
  1988. # GORE: Ako praznoto pole ne e vo prviot red, togas vo sostojbata napravi swap
  1989. # na praznoto pole so brojceto koe se naoga na poleto nad nego
  1990. if blank > 2:
  1991. swap = blank - 3
  1992. succs['GORE'] = S[0:swap] + '*' + S[swap + 1:blank] + S[swap] + S[blank + 1:]
  1993.  
  1994. # DOLE: Ako praznoto pole ne e vo posledniot red, togas vo sostojbata napravi swap
  1995. # na praznoto pole so brojceto koe se naoga na poleto pod nego
  1996. if blank < 6:
  1997. swap = blank + 3
  1998. succs['DOLE'] = S[0:blank] + S[swap] + S[blank + 1:swap] + '*' + S[swap + 1:]
  1999.  
  2000. # LEVO: Ako praznoto pole ne e vo prvata kolona, togas vo sostojbata napravi swap
  2001. # na praznoto pole so brojceto koe se naoga na poleto levo od nego
  2002. if blank % 3 > 0:
  2003. swap = blank - 1
  2004. succs['LEVO'] = S[0:swap] + '*' + S[swap] + S[blank + 1:]
  2005.  
  2006. # DESNO: Ako praznoto pole ne e vo poslednata kolona, togas vo sostojbata napravi swap
  2007. # na praznoto pole so brojceto koe se naoga na poleto desno od nego
  2008. if blank % 3 < 2:
  2009. swap = blank + 1
  2010. succs['DESNO'] = S[0:blank] + S[swap] + '*' + S[swap + 1:]
  2011.  
  2012. return succs
  2013.  
  2014. # So vaka definiraniot problem mozeme da gi koristime site informirani, no i neinformirani prebaruvanja
  2015. # Vo prodolzenie se dadeni mozni povici (vnimavajte za da moze da napravite povik mora da definirate problem)
  2016. #
  2017. # s='*32415678'
  2018. # p1=P8(initial=s)
  2019. # p2=P8_h1(initial=s)
  2020. # p3=P8_h2(initial=s)
  2021. #
  2022. # answer1 = greedy_best_first_graph_search(p1)
  2023. # print answer1.solve()
  2024. #
  2025. # answer2 = greedy_best_first_graph_search(p2)
  2026. # print answer2.solve()
  2027. #
  2028. # answer3 = greedy_best_first_graph_search(p3)
  2029. # print answer3.solve()
  2030. #
  2031. # answer4 = astar_search(p1)
  2032. # print answer4.solve()
  2033. #
  2034. # answer5 = astar_search(p2)
  2035. # print answer5.solve()
  2036. #
  2037. # answer6 = astar_search(p3)
  2038. # print answer6.solve()
  2039. #
  2040. # answer7 = recursive_best_first_search(p1)
  2041. # print answer7.solve()
  2042. #
  2043. # answer8 = recursive_best_first_search(p2)
  2044. # print answer8.solve()
  2045. #
  2046. # answer9 = recursive_best_first_search(p3)
  2047. # print answer9.solve()
  2048. def updateP1(P1):
  2049. x = P1[0]
  2050. y = P1[1]
  2051. n = P1[2]
  2052. if (y == 4 and n == 1):
  2053. n = n * (-1)
  2054. if (y == 0 and n == -1):
  2055. n = n * (-1)
  2056. ynew = y + n
  2057. return (x, ynew, n)
  2058.  
  2059.  
  2060. def updateP2(P2):
  2061. x = P2[0]
  2062. y = P2[1]
  2063. n = P2[2]
  2064. if (x == 5 and y == 4 and n == 1):
  2065. n = n * (-1)
  2066. if (y == 0 and x == 9 and n == -1):
  2067. n = n * (-1)
  2068. xnew = x - n
  2069. ynew = y + n
  2070. return (xnew, ynew, n)
  2071.  
  2072.  
  2073. def updateP3(P3):
  2074. x = P3[0]
  2075. y = P3[1]
  2076. n = P3[2]
  2077. if (x == 5 and n == -1):
  2078. n = n * (-1)
  2079. if (x == 9 and n == 1):
  2080. n = n * (-1)
  2081. xnew = x + n
  2082. return (xnew, y, n)
  2083.  
  2084.  
  2085. def isValid(x, y, P1, P2, P3):
  2086. t = 1
  2087. if (x == P1[0] and y == P1[1]) or (x == P1[0] and y == P1[1] + 1):
  2088. t = 0
  2089. 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 (
  2090. x == P2[0] + 1 and y == P2[1] + 1):
  2091. t = 0
  2092. if (x == P3[0] and y == P3[1]) or (x == P3[0] + 1 and y == P3[1]):
  2093. t = 0
  2094. return t
  2095.  
  2096.  
  2097.  
  2098. class Istrazuvac(Problem):
  2099. def __init__(self, initial, goal):
  2100. self.initial = initial
  2101. self.goal = goal
  2102.  
  2103. def successor(self, state):
  2104. successors = dict()
  2105. X = state[0]
  2106. Y = state[1]
  2107. P1 = state[2]
  2108. P2 = state[3]
  2109. P3 = state[4]
  2110. P1new = updateP1(P1)
  2111. P2new = updateP2(P2)
  2112. P3new = updateP3(P3)
  2113.  
  2114. # Levo
  2115. if Y - 1 >= 0:
  2116. Ynew = Y - 1
  2117. Xnew = X
  2118. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2119. successors['Levo'] = (Xnew, Ynew, P1new, P2new, P3new)
  2120. # Desno
  2121. if X < 5 and Y < 5:
  2122. Ynew = Y + 1
  2123. Xnew = X
  2124. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2125. successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  2126. elif X >= 5 and Y < 10:
  2127. Xnew = X
  2128. Ynew = Y + 1
  2129. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2130. successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  2131. # Dolu
  2132. if X < 10:
  2133. Xnew = X + 1
  2134. Ynew = Y
  2135. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2136. successors['Dolu'] = (Xnew, Ynew, P1new, P2new, P3new)
  2137. # Gore
  2138. if Y >= 6 and X > 5:
  2139. Xnew = X - 1
  2140. Ynew = Y
  2141. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2142. successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  2143. elif Y < 6 and X > 0:
  2144. Xnew = X - 1
  2145. Ynew = Y
  2146. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2147. successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  2148. return successors
  2149.  
  2150. def actions(self, state):
  2151. return self.successor(state).keys()
  2152.  
  2153. def result(self, state, action):
  2154. possible = self.successor(state)
  2155. return possible[action]
  2156.  
  2157. def goal_test(self, state):
  2158. g = self.goal
  2159. return (state[0] == g[0] and state[1] == g[1])
  2160.  
  2161. def h(self,node):
  2162. rez=abs(node.state[0]-self.goal[0])+abs(node.state[1]-self.goal[1])
  2163. return rez
  2164.  
  2165.  
  2166. #Vcituvanje na vleznite argumenti za test primerite
  2167.  
  2168. CoveceRedica = input()
  2169. CoveceKolona = input()
  2170. KukaRedica = input()
  2171. KukaKolona = input()
  2172.  
  2173. #Vasiot kod pisuvajte go pod ovoj komentar
  2174.  
  2175. # 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)
  2176. # prepreka 3 ima gore kvadrat na 8,7 odi nagore na pocetok(-1)
  2177. IstrazuvacInstance = Istrazuvac((CoveceRedica, CoveceKolona, (2, 2, -1), (7, 2, 1), (7, 8, 1)),(KukaRedica, KukaKolona))
  2178.  
  2179. answer=astar_search(IstrazuvacInstance).solution()
  2180. print(answer)
  2181.  
  2182. ***************informirano misioneri ********
  2183. #Vcituvanje na vleznite argumenti za test primerite
  2184.  
  2185. N = input()
  2186. K = input()
  2187.  
  2188. #Vasiot kod pisuvajte go pod ovoj komentar
  2189.  
  2190. # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
  2191.  
  2192. # ______________________________________________________________________________________________
  2193. # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
  2194.  
  2195. import math
  2196. import sys
  2197. import bisect
  2198.  
  2199. infinity = float('inf') # sistemski definirana vrednost za beskonecnost
  2200.  
  2201.  
  2202. # ______________________________________________________________________________________________
  2203. # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
  2204.  
  2205. class Queue:
  2206. """Queue is an abstract class/interface. There are three types:
  2207. Stack(): A Last In First Out Queue.
  2208. FIFOQueue(): A First In First Out Queue.
  2209. PriorityQueue(order, f): Queue in sorted order (default min-first).
  2210. Each type supports the following methods and functions:
  2211. q.append(item) -- add an item to the queue
  2212. q.extend(items) -- equivalent to: for item in items: q.append(item)
  2213. q.pop() -- return the top item from the queue
  2214. len(q) -- number of items in q (also q.__len())
  2215. item in q -- does q contain item?
  2216. Note that isinstance(Stack(), Queue) is false, because we implement stacks
  2217. as lists. If Python ever gets interfaces, Queue will be an interface."""
  2218.  
  2219. def __init__(self):
  2220. raise NotImplementedError
  2221.  
  2222. def extend(self, items):
  2223. for item in items:
  2224. self.append(item)
  2225.  
  2226. class PriorityQueue(Queue):
  2227. """A queue in which the minimum (or maximum) element (as determined by f and
  2228. order) is returned first. If order is min, the item with minimum f(x) is
  2229. returned first; if order is max, then it is the item with maximum f(x).
  2230. Also supports dict-like lookup. This structure will be most useful in informed searches"""
  2231.  
  2232. def __init__(self, order=min, f=lambda x: x):
  2233. self.A = []
  2234. self.order = order
  2235. self.f = f
  2236.  
  2237. def append(self, item):
  2238. bisect.insort(self.A, (self.f(item), item))
  2239.  
  2240. def __len__(self):
  2241. return len(self.A)
  2242.  
  2243. def pop(self):
  2244. if self.order == min:
  2245. return self.A.pop(0)[1]
  2246. else:
  2247. return self.A.pop()[1]
  2248.  
  2249. def __contains__(self, item):
  2250. return any(item == pair[1] for pair in self.A)
  2251.  
  2252. def __getitem__(self, key):
  2253. for _, item in self.A:
  2254. if item == key:
  2255. return item
  2256.  
  2257. def __delitem__(self, key):
  2258. for i, (value, item) in enumerate(self.A):
  2259. if item == key:
  2260. self.A.pop(i)
  2261.  
  2262.  
  2263. # ______________________________________________________________________________________________
  2264. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  2265. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  2266. # na sekoj eden problem sto sakame da go resime
  2267.  
  2268.  
  2269. class Problem:
  2270. """The abstract class for a formal problem. You should subclass this and
  2271. implement the method successor, and possibly __init__, goal_test, and
  2272. path_cost. Then you will create instances of your subclass and solve them
  2273. with the various search functions."""
  2274.  
  2275. def __init__(self, initial, goal=None):
  2276. """The constructor specifies the initial state, and possibly a goal
  2277. state, if there is a unique goal. Your subclass's constructor can add
  2278. other arguments."""
  2279. self.initial = initial
  2280. self.goal = goal
  2281.  
  2282. def successor(self, state):
  2283. """Given a state, return a dictionary of {action : state} pairs reachable
  2284. from this state. If there are many successors, consider an iterator
  2285. that yields the successors one at a time, rather than building them
  2286. all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  2287. raise NotImplementedError
  2288.  
  2289. def actions(self, state):
  2290. """Given a state, return a list of all actions possible from that state"""
  2291. raise NotImplementedError
  2292.  
  2293. def result(self, state, action):
  2294. """Given a state and action, return the resulting state"""
  2295. raise NotImplementedError
  2296.  
  2297. def goal_test(self, state):
  2298. """Return True if the state is a goal. The default method compares the
  2299. state to self.goal, as specified in the constructor. Implement this
  2300. method if checking against a single self.goal is not enough."""
  2301. return state == self.goal
  2302.  
  2303. def path_cost(self, c, state1, action, state2):
  2304. """Return the cost of a solution path that arrives at state2 from
  2305. state1 via action, assuming cost c to get up to state1. If the problem
  2306. is such that the path doesn't matter, this function will only look at
  2307. state2. If the path does matter, it will consider c and maybe state1
  2308. and action. The default method costs 1 for every step in the path."""
  2309. return c + 1
  2310.  
  2311. def value(self):
  2312. """For optimization problems, each state has a value. Hill-climbing
  2313. and related algorithms try to maximize this value."""
  2314. raise NotImplementedError
  2315.  
  2316.  
  2317. # ______________________________________________________________________________
  2318. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  2319. # Klasata Node ne se nasleduva
  2320.  
  2321. class Node:
  2322. """A node in a search tree. Contains a pointer to the parent (the node
  2323. that this is a successor of) and to the actual state for this node. Note
  2324. that if a state is arrived at by two paths, then there are two nodes with
  2325. the same state. Also includes the action that got us to this state, and
  2326. the total path_cost (also known as g) to reach the node. Other functions
  2327. may add an f and h value; see best_first_graph_search and astar_search for
  2328. an explanation of how the f and h values are handled. You will not need to
  2329. subclass this class."""
  2330.  
  2331. def __init__(self, state, parent=None, action=None, path_cost=0):
  2332. "Create a search tree Node, derived from a parent by an action."
  2333. self.state = state
  2334. self.parent = parent
  2335. self.action = action
  2336. self.path_cost = path_cost
  2337. self.depth = 0
  2338. if parent:
  2339. self.depth = parent.depth + 1
  2340.  
  2341. def __repr__(self):
  2342. return "<Node %s>" % (self.state,)
  2343.  
  2344. def __lt__(self, node):
  2345. return self.state < node.state
  2346.  
  2347. def expand(self, problem):
  2348. "List the nodes reachable in one step from this node."
  2349. return [self.child_node(problem, action)
  2350. for action in problem.actions(self.state)] # samo ednash se povikuva actions za momentalnata sostojba
  2351.  
  2352. def child_node(self, problem, action):
  2353. "Return a child node from this node"
  2354. next = problem.result(self.state, action)
  2355. return Node(next, self, action,
  2356. problem.path_cost(self.path_cost, self.state,
  2357. action, next))
  2358.  
  2359. def solution(self):
  2360. "Return the sequence of actions to go from the root to this node."
  2361. return [node.action for node in self.path()[1:]]
  2362.  
  2363. def solve(self):
  2364. "Return the sequence of states to go from the root to this node."
  2365. return [node.state for node in self.path()[0:]]
  2366.  
  2367. def path(self):
  2368. "Return a list of nodes forming the path from the root to this node."
  2369. x, result = self, []
  2370. while x:
  2371. result.append(x)
  2372. x = x.parent
  2373. return list(reversed(result))
  2374.  
  2375. # We want for a queue of nodes in breadth_first_search or
  2376. # astar_search to have no duplicated states, so we treat nodes
  2377. # with the same state as equal. [Problem: this may not be what you
  2378. # want in other contexts.]
  2379.  
  2380. def __eq__(self, other):
  2381. return isinstance(other, Node) and self.state == other.state
  2382.  
  2383. def __hash__(self):
  2384. return hash(self.state)
  2385. # ________________________________________________________________________________________________________
  2386. # Pomosna funkcija za informirani prebaruvanja
  2387. # So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
  2388.  
  2389. def memoize(fn, slot=None):
  2390. """Memoize fn: make it remember the computed value for any argument list.
  2391. If slot is specified, store result in that slot of first argument.
  2392. If slot is false, store results in a dictionary."""
  2393. if slot:
  2394. def memoized_fn(obj, *args):
  2395. if hasattr(obj, slot):
  2396. return getattr(obj, slot)
  2397. else:
  2398. val = fn(obj, *args)
  2399. setattr(obj, slot, val)
  2400. return val
  2401. else:
  2402. def memoized_fn(*args):
  2403. if not memoized_fn.cache.has_key(args):
  2404. memoized_fn.cache[args] = fn(*args)
  2405. return memoized_fn.cache[args]
  2406.  
  2407. memoized_fn.cache = {}
  2408. return memoized_fn
  2409.  
  2410.  
  2411. # ________________________________________________________________________________________________________
  2412. # Informirano prebaruvanje vo ramki na graf
  2413.  
  2414. def best_first_graph_search(problem, f):
  2415. """Search the nodes with the lowest f scores first.
  2416. You specify the function f(node) that you want to minimize; for example,
  2417. if f is a heuristic estimate to the goal, then we have greedy best
  2418. first search; if f is node.depth then we have breadth-first search.
  2419. There is a subtlety: the line "f = memoize(f, 'f')" means that the f
  2420. values will be cached on the nodes as they are computed. So after doing
  2421. a best first search you can examine the f values of the path returned."""
  2422.  
  2423. f = memoize(f, 'f')
  2424. node = Node(problem.initial)
  2425. if problem.goal_test(node.state):
  2426. return node
  2427. frontier = PriorityQueue(min, f)
  2428. frontier.append(node)
  2429. explored = set()
  2430. while frontier:
  2431. node = frontier.pop()
  2432. if problem.goal_test(node.state):
  2433. return node
  2434. explored.add(node.state)
  2435. for child in node.expand(problem):
  2436. #if node.state == (1, 1, 'D', 2, 2):
  2437. # print(child.state)
  2438. if child.state not in explored and child not in frontier:
  2439. frontier.append(child)
  2440. elif child in frontier:
  2441. incumbent = frontier[child]
  2442. if f(child) < f(incumbent):
  2443. del frontier[incumbent]
  2444. frontier.append(child)
  2445. return None
  2446.  
  2447.  
  2448. def greedy_best_first_graph_search(problem, h=None):
  2449. "Greedy best-first search is accomplished by specifying f(n) = h(n)"
  2450. h = memoize(h or problem.h, 'h')
  2451. return best_first_graph_search(problem, h)
  2452.  
  2453. class Mission(Problem):
  2454.  
  2455. def __init__(self,N,capacity):
  2456. self.initial=(N, N, 'L', 0, 0)
  2457. self.capacity=capacity
  2458.  
  2459. def goal_test(self, state):
  2460. return (state[0]==0 and state[1]==0)
  2461.  
  2462. def h(self,node):
  2463. missionaryLeft=node.state[0]
  2464. cannibalLeft=node.state[1]
  2465.  
  2466. return (missionaryLeft+cannibalLeft)/2
  2467.  
  2468.  
  2469. def is_valid(self,missionaryLeft, cannibalLeft,missionaryRight, cannibalRight):
  2470. return (missionaryLeft>=0 and missionaryRight>=0 and cannibalLeft>=0 and cannibalRight>=0 \
  2471. and (missionaryLeft ==0 or missionaryLeft >= cannibalLeft) and ( missionaryRight == 0 or missionaryRight >= cannibalRight))
  2472.  
  2473.  
  2474. def successor(self, state):
  2475. successors=dict()
  2476.  
  2477. missionaryLeft = state[0]
  2478. cannibalLeft = state[1]
  2479. boat = state[2]
  2480. missionaryRight = state[3]
  2481. cannibalRight = state[4]
  2482.  
  2483. if boat=='L':
  2484. for i in range(1,self.capacity+1):
  2485. for j in range(0, i+1):
  2486. newMissionaryLeft=missionaryLeft-(i-j)
  2487. newCannibalLeft=cannibalLeft-j
  2488. newMissionaryRight=missionaryRight+(i-j)
  2489. newCannibalRight=cannibalRight+j
  2490. if(self.is_valid(newMissionaryLeft,newCannibalLeft,newMissionaryRight,newCannibalRight)):
  2491. successors[str(i-j)+'M_'+str(j)+'K']=(newMissionaryLeft,newCannibalLeft,'D',newMissionaryRight,newCannibalRight)
  2492.  
  2493. if boat=='D':
  2494. for i in range(1,self.capacity+1):
  2495. for j in range(0, i+1):
  2496. newMissionaryRight = missionaryRight - (i-j)
  2497. newCannibalRight = cannibalRight - j
  2498. newMissionaryLeft=missionaryLeft+(i-j)
  2499. newCannibalLeft=cannibalLeft+j
  2500. if(self.is_valid(newMissionaryLeft,newCannibalLeft,newMissionaryRight,newCannibalRight)):
  2501. successors[str(i-j)+'M_'+str(j)+'K']=(newMissionaryLeft,newCannibalLeft,'L',newMissionaryRight,newCannibalRight)
  2502.  
  2503. return successors
  2504.  
  2505. def actions(self, state):
  2506. return self.successor(state).keys()
  2507.  
  2508. def result(self, state, action):
  2509. possible = self.successor(state)
  2510. return possible[action]
  2511.  
  2512. MissionInstance=Mission(int(N),int(K))
  2513. answer = greedy_best_first_graph_search(MissionInstance)
  2514. print(answer.solve())
  2515.  
  2516. *********podvizni neinf***
  2517. # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
  2518.  
  2519. # ______________________________________________________________________________________________
  2520. # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
  2521.  
  2522. import sys
  2523. import bisect
  2524.  
  2525. infinity = float('inf') # sistemski definirana vrednost za beskonecnost
  2526.  
  2527.  
  2528. # ______________________________________________________________________________________________
  2529. # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
  2530.  
  2531. class Queue:
  2532. """Queue is an abstract class/interface. There are three types:
  2533. Stack(): A Last In First Out Queue.
  2534. FIFOQueue(): A First In First Out Queue.
  2535. PriorityQueue(order, f): Queue in sorted order (default min-first).
  2536. Each type supports the following methods and functions:
  2537. q.append(item) -- add an item to the queue
  2538. q.extend(items) -- equivalent to: for item in items: q.append(item)
  2539. q.pop() -- return the top item from the queue
  2540. len(q) -- number of items in q (also q.__len())
  2541. item in q -- does q contain item?
  2542. Note that isinstance(Stack(), Queue) is false, because we implement stacks
  2543. as lists. If Python ever gets interfaces, Queue will be an interface."""
  2544.  
  2545. def __init__(self):
  2546. raise NotImplementedError
  2547.  
  2548. def extend(self, items):
  2549. for item in items:
  2550. self.append(item)
  2551.  
  2552.  
  2553. class FIFOQueue(Queue):
  2554. """A First-In-First-Out Queue."""
  2555.  
  2556. def __init__(self):
  2557. self.A = []
  2558. self.start = 0
  2559.  
  2560. def append(self, item):
  2561. self.A.append(item)
  2562.  
  2563. def __len__(self):
  2564. return len(self.A) - self.start
  2565.  
  2566. def extend(self, items):
  2567. self.A.extend(items)
  2568.  
  2569. def pop(self):
  2570. e = self.A[self.start]
  2571. self.start += 1
  2572. if self.start > 5 and self.start > len(self.A) / 2:
  2573. self.A = self.A[self.start:]
  2574. self.start = 0
  2575. return e
  2576.  
  2577. def __contains__(self, item):
  2578. return item in self.A[self.start:]
  2579.  
  2580.  
  2581. # ______________________________________________________________________________________________
  2582. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  2583. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  2584. # na sekoj eden problem sto sakame da go resime
  2585.  
  2586.  
  2587. class Problem:
  2588. """The abstract class for a formal problem. You should subclass this and
  2589. implement the method successor, and possibly __init__, goal_test, and
  2590. path_cost. Then you will create instances of your subclass and solve them
  2591. with the various search functions."""
  2592.  
  2593. def __init__(self, initial, goal=None):
  2594. """The constructor specifies the initial state, and possibly a goal
  2595. state, if there is a unique goal. Your subclass's constructor can add
  2596. other arguments."""
  2597. self.initial = initial
  2598. self.goal = goal
  2599.  
  2600. def successor(self, state):
  2601. """Given a state, return a dictionary of {action : state} pairs reachable
  2602. from this state. If there are many successors, consider an iterator
  2603. that yields the successors one at a time, rather than building them
  2604. all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  2605. raise NotImplementedError
  2606.  
  2607. def actions(self, state):
  2608. """Given a state, return a list of all actions possible from that state"""
  2609. raise NotImplementedError
  2610.  
  2611. def result(self, state, action):
  2612. """Given a state and action, return the resulting state"""
  2613. raise NotImplementedError
  2614.  
  2615. def goal_test(self, state):
  2616. """Return True if the state is a goal. The default method compares the
  2617. state to self.goal, as specified in the constructor. Implement this
  2618. method if checking against a single self.goal is not enough."""
  2619. return state == self.goal
  2620.  
  2621. def path_cost(self, c, state1, action, state2):
  2622. """Return the cost of a solution path that arrives at state2 from
  2623. state1 via action, assuming cost c to get up to state1. If the problem
  2624. is such that the path doesn't matter, this function will only look at
  2625. state2. If the path does matter, it will consider c and maybe state1
  2626. and action. The default method costs 1 for every step in the path."""
  2627. return c + 1
  2628.  
  2629. def value(self):
  2630. """For optimization problems, each state has a value. Hill-climbing
  2631. and related algorithms try to maximize this value."""
  2632. raise NotImplementedError
  2633.  
  2634.  
  2635. # ______________________________________________________________________________
  2636. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  2637. # Klasata Node ne se nasleduva
  2638.  
  2639. class Node:
  2640. """A node in a search tree. Contains a pointer to the parent (the node
  2641. that this is a successor of) and to the actual state for this node. Note
  2642. that if a state is arrived at by two paths, then there are two nodes with
  2643. the same state. Also includes the action that got us to this state, and
  2644. the total path_cost (also known as g) to reach the node. Other functions
  2645. may add an f and h value; see best_first_graph_search and astar_search for
  2646. an explanation of how the f and h values are handled. You will not need to
  2647. subclass this class."""
  2648.  
  2649. def __init__(self, state, parent=None, action=None, path_cost=0):
  2650. "Create a search tree Node, derived from a parent by an action."
  2651. self.state = state
  2652. self.parent = parent
  2653. self.action = action
  2654. self.path_cost = path_cost
  2655. self.depth = 0
  2656. if parent:
  2657. self.depth = parent.depth + 1
  2658.  
  2659. def __repr__(self):
  2660. return "<Node %s>" % (self.state,)
  2661.  
  2662. def __lt__(self, node):
  2663. return self.state < node.state
  2664.  
  2665. def expand(self, problem):
  2666. "List the nodes reachable in one step from this node."
  2667. return [self.child_node(problem, action)
  2668. for action in problem.actions(self.state)]
  2669.  
  2670. def child_node(self, problem, action):
  2671. "Return a child node from this node"
  2672. next = problem.result(self.state, action)
  2673. return Node(next, self, action,
  2674. problem.path_cost(self.path_cost, self.state,
  2675. action, next))
  2676.  
  2677. def solution(self):
  2678. "Return the sequence of actions to go from the root to this node."
  2679. return [node.action for node in self.path()[1:]]
  2680.  
  2681. def solve(self):
  2682. "Return the sequence of states to go from the root to this node."
  2683. return [node.state for node in self.path()[0:]]
  2684.  
  2685. def path(self):
  2686. "Return a list of nodes forming the path from the root to this node."
  2687. x, result = self, []
  2688. while x:
  2689. result.append(x)
  2690. x = x.parent
  2691. return list(reversed(result))
  2692.  
  2693. # We want for a queue of nodes in breadth_first_search or
  2694. # astar_search to have no duplicated states, so we treat nodes
  2695. # with the same state as equal. [Problem: this may not be what you
  2696. # want in other contexts.]
  2697.  
  2698. def __eq__(self, other):
  2699. return isinstance(other, Node) and self.state == other.state
  2700.  
  2701. def __hash__(self):
  2702. return hash(self.state)
  2703.  
  2704.  
  2705. def graph_search(problem, fringe):
  2706. """Search through the successors of a problem to find a goal.
  2707. The argument fringe should be an empty queue.
  2708. If two paths reach a state, only use the best one."""
  2709. closed = {}
  2710. fringe.append(Node(problem.initial))
  2711. while fringe:
  2712. node = fringe.pop()
  2713. if problem.goal_test(node.state):
  2714. return node
  2715. if node.state not in closed:
  2716. closed[node.state] = True
  2717. fringe.extend(node.expand(problem))
  2718. return None
  2719.  
  2720.  
  2721. def breadth_first_graph_search(problem):
  2722. "Search the shallowest nodes in the search tree first."
  2723. return graph_search(problem, FIFOQueue())
  2724.  
  2725.  
  2726. def updateP1(P1):
  2727. x = P1[0]
  2728. y = P1[1]
  2729. n = P1[2]
  2730. if (y == 4 and n == 1):
  2731. n = n * (-1)
  2732. if (y == 0 and n == -1):
  2733. n = n * (-1)
  2734. ynew = y + n
  2735. return (x, ynew, n)
  2736.  
  2737.  
  2738. def updateP2(P2):
  2739. x = P2[0]
  2740. y = P2[1]
  2741. n = P2[2]
  2742. if (x == 5 and y == 4 and n == 1):
  2743. n = n * (-1)
  2744. if (y == 0 and x == 9 and n == -1):
  2745. n = n * (-1)
  2746. xnew = x - n
  2747. ynew = y + n
  2748. return (xnew, ynew, n)
  2749.  
  2750.  
  2751. def updateP3(P3):
  2752. x = P3[0]
  2753. y = P3[1]
  2754. n = P3[2]
  2755. if (x == 5 and n == -1):
  2756. n = n * (-1)
  2757. if (x == 9 and n == 1):
  2758. n = n * (-1)
  2759. xnew = x + n
  2760. return (xnew, y, n)
  2761.  
  2762.  
  2763. def isValid(x, y, P1, P2, P3):
  2764. t = 1
  2765. if (x == P1[0] and y == P1[1]) or (x == P1[0] and y == P1[1] + 1):
  2766. t = 0
  2767. 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 (
  2768. x == P2[0] + 1 and y == P2[1] + 1):
  2769. t = 0
  2770. if (x == P3[0] and y == P3[1]) or (x == P3[0] + 1 and y == P3[1]):
  2771. t = 0
  2772. return t
  2773.  
  2774.  
  2775. class Istrazuvac(Problem):
  2776. def __init__(self, initial, goal):
  2777. self.initial = initial
  2778. self.goal = goal
  2779.  
  2780. def successor(self, state):
  2781. successors = dict()
  2782. X = state[0]
  2783. Y = state[1]
  2784. P1 = state[2]
  2785. P2 = state[3]
  2786. P3 = state[4]
  2787. P1new = updateP1(P1)
  2788. P2new = updateP2(P2)
  2789. P3new = updateP3(P3)
  2790.  
  2791. # Levo
  2792. if Y - 1 >= 0:
  2793. Ynew = Y - 1
  2794. Xnew = X
  2795. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2796. successors['Levo'] = (Xnew, Ynew, P1new, P2new, P3new)
  2797. # Desno
  2798. if X < 5 and Y < 5:
  2799. Ynew = Y + 1
  2800. Xnew = X
  2801. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2802. successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  2803. elif X >= 5 and Y < 10:
  2804. Xnew = X
  2805. Ynew = Y + 1
  2806. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2807. successors['Desno'] = (Xnew, Ynew, P1new, P2new, P3new)
  2808. # Dolu
  2809. if X < 10:
  2810. Xnew = X + 1
  2811. Ynew = Y
  2812. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2813. successors['Dolu'] = (Xnew, Ynew, P1new, P2new, P3new)
  2814. # Gore
  2815. if Y >= 6 and X > 5:
  2816. Xnew = X - 1
  2817. Ynew = Y
  2818. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2819. successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  2820. elif Y < 6 and X > 0:
  2821. Xnew = X - 1
  2822. Ynew = Y
  2823. if (isValid(Xnew, Ynew, P1new, P2new, P3new)):
  2824. successors['Gore'] = (Xnew, Ynew, P1new, P2new, P3new)
  2825. return successors
  2826.  
  2827. def actions(self, state):
  2828. return self.successor(state).keys()
  2829.  
  2830. def result(self, state, action):
  2831. possible = self.successor(state)
  2832. return possible[action]
  2833.  
  2834. def goal_test(self, state):
  2835. g = self.goal
  2836. return (state[0] == g[0] and state[1] == g[1])
  2837.  
  2838.  
  2839. CoveceRedica = int(input())
  2840. CoveceKolona = int(input())
  2841. KukaRedica = int(input())
  2842. KukaKolona = int(input())
  2843.  
  2844. # 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)
  2845. # prepreka 3 ima gore kvadrat na 8,7 odi nagore na pocetok(-1)
  2846. IstrazuvacInstance = Istrazuvac((CoveceRedica, CoveceKolona, (2, 2, -1), (7, 2, 1), (7, 8, 1)),(KukaRedica, KukaKolona))
  2847.  
  2848. answer = breadth_first_graph_search(IstrazuvacInstance)
  2849. print(answer.solution())
  2850. ****molekula neinf***
  2851. # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
  2852.  
  2853. # ______________________________________________________________________________________________
  2854. # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
  2855.  
  2856. import sys
  2857. import bisect
  2858.  
  2859. infinity = float('inf') # sistemski definirana vrednost za beskonecnost
  2860.  
  2861.  
  2862. # ______________________________________________________________________________________________
  2863. # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
  2864.  
  2865. class Queue:
  2866. """Queue is an abstract class/interface. There are three types:
  2867. Stack(): A Last In First Out Queue.
  2868. FIFOQueue(): A First In First Out Queue.
  2869. PriorityQueue(order, f): Queue in sorted order (default min-first).
  2870. Each type supports the following methods and functions:
  2871. q.append(item) -- add an item to the queue
  2872. q.extend(items) -- equivalent to: for item in items: q.append(item)
  2873. q.pop() -- return the top item from the queue
  2874. len(q) -- number of items in q (also q.__len())
  2875. item in q -- does q contain item?
  2876. Note that isinstance(Stack(), Queue) is false, because we implement stacks
  2877. as lists. If Python ever gets interfaces, Queue will be an interface."""
  2878.  
  2879. def __init__(self):
  2880. raise NotImplementedError
  2881.  
  2882. def extend(self, items):
  2883. for item in items:
  2884. self.append(item)
  2885.  
  2886.  
  2887. def Stack():
  2888. """A Last-In-First-Out Queue."""
  2889. return []
  2890.  
  2891.  
  2892. class FIFOQueue(Queue):
  2893. """A First-In-First-Out Queue."""
  2894.  
  2895. def __init__(self):
  2896. self.A = []
  2897. self.start = 0
  2898.  
  2899. def append(self, item):
  2900. self.A.append(item)
  2901.  
  2902. def __len__(self):
  2903. return len(self.A) - self.start
  2904.  
  2905. def extend(self, items):
  2906. self.A.extend(items)
  2907.  
  2908. def pop(self):
  2909. e = self.A[self.start]
  2910. self.start += 1
  2911. if self.start > 5 and self.start > len(self.A) / 2:
  2912. self.A = self.A[self.start:]
  2913. self.start = 0
  2914. return e
  2915.  
  2916. def __contains__(self, item):
  2917. return item in self.A[self.start:]
  2918.  
  2919.  
  2920. class PriorityQueue(Queue):
  2921. """A queue in which the minimum (or maximum) element (as determined by f and
  2922. order) is returned first. If order is min, the item with minimum f(x) is
  2923. returned first; if order is max, then it is the item with maximum f(x).
  2924. Also supports dict-like lookup. This structure will be most useful in informed searches"""
  2925.  
  2926. def __init__(self, order=min, f=lambda x: x):
  2927. self.A = []
  2928. self.order = order
  2929. self.f = f
  2930.  
  2931. def append(self, item):
  2932. bisect.insort(self.A, (self.f(item), item))
  2933.  
  2934. def __len__(self):
  2935. return len(self.A)
  2936.  
  2937. def pop(self):
  2938. if self.order == min:
  2939. return self.A.pop(0)[1]
  2940. else:
  2941. return self.A.pop()[1]
  2942.  
  2943. def __contains__(self, item):
  2944. return any(item == pair[1] for pair in self.A)
  2945.  
  2946. def __getitem__(self, key):
  2947. for _, item in self.A:
  2948. if item == key:
  2949. return item
  2950.  
  2951. def __delitem__(self, key):
  2952. for i, (value, item) in enumerate(self.A):
  2953. if item == key:
  2954. self.A.pop(i)
  2955.  
  2956.  
  2957. # ______________________________________________________________________________________________
  2958. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  2959. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  2960. # na sekoj eden problem sto sakame da go resime
  2961.  
  2962.  
  2963. class Problem:
  2964. """The abstract class for a formal problem. You should subclass this and
  2965. implement the method successor, and possibly __init__, goal_test, and
  2966. path_cost. Then you will create instances of your subclass and solve them
  2967. with the various search functions."""
  2968.  
  2969. def __init__(self, initial, goal=None):
  2970. """The constructor specifies the initial state, and possibly a goal
  2971. state, if there is a unique goal. Your subclass's constructor can add
  2972. other arguments."""
  2973. self.initial = initial
  2974. self.goal = goal
  2975.  
  2976. def successor(self, state):
  2977. """Given a state, return a dictionary of {action : state} pairs reachable
  2978. from this state. If there are many successors, consider an iterator
  2979. that yields the successors one at a time, rather than building them
  2980. all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  2981. raise NotImplementedError
  2982.  
  2983. def actions(self, state):
  2984. """Given a state, return a list of all actions possible from that state"""
  2985. raise NotImplementedError
  2986.  
  2987. def result(self, state, action):
  2988. """Given a state and action, return the resulting state"""
  2989. raise NotImplementedError
  2990.  
  2991. def goal_test(self, state):
  2992. """Return True if the state is a goal. The default method compares the
  2993. state to self.goal, as specified in the constructor. Implement this
  2994. method if checking against a single self.goal is not enough."""
  2995. return state == self.goal
  2996.  
  2997. def path_cost(self, c, state1, action, state2):
  2998. """Return the cost of a solution path that arrives at state2 from
  2999. state1 via action, assuming cost c to get up to state1. If the problem
  3000. is such that the path doesn't matter, this function will only look at
  3001. state2. If the path does matter, it will consider c and maybe state1
  3002. and action. The default method costs 1 for every step in the path."""
  3003. return c + 1
  3004.  
  3005. def value(self):
  3006. """For optimization problems, each state has a value. Hill-climbing
  3007. and related algorithms try to maximize this value."""
  3008. raise NotImplementedError
  3009.  
  3010.  
  3011. # ______________________________________________________________________________
  3012. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  3013. # Klasata Node ne se nasleduva
  3014.  
  3015. class Node:
  3016. """A node in a search tree. Contains a pointer to the parent (the node
  3017. that this is a successor of) and to the actual state for this node. Note
  3018. that if a state is arrived at by two paths, then there are two nodes with
  3019. the same state. Also includes the action that got us to this state, and
  3020. the total path_cost (also known as g) to reach the node. Other functions
  3021. may add an f and h value; see best_first_graph_search and astar_search for
  3022. an explanation of how the f and h values are handled. You will not need to
  3023. subclass this class."""
  3024.  
  3025. def __init__(self, state, parent=None, action=None, path_cost=0):
  3026. "Create a search tree Node, derived from a parent by an action."
  3027. self.state = state
  3028. self.parent = parent
  3029. self.action = action
  3030. self.path_cost = path_cost
  3031. self.depth = 0
  3032. if parent:
  3033. self.depth = parent.depth + 1
  3034.  
  3035. def __repr__(self):
  3036. return "<Node %s>" % (self.state,)
  3037.  
  3038. def __lt__(self, node):
  3039. return self.state < node.state
  3040.  
  3041. def expand(self, problem):
  3042. "List the nodes reachable in one step from this node."
  3043. return [self.child_node(problem, action)
  3044. for action in problem.actions(self.state)]
  3045.  
  3046. def child_node(self, problem, action):
  3047. "Return a child node from this node"
  3048. next = problem.result(self.state, action)
  3049. return Node(next, self, action,
  3050. problem.path_cost(self.path_cost, self.state,
  3051. action, next))
  3052.  
  3053. def solution(self):
  3054. "Return the sequence of actions to go from the root to this node."
  3055. return [node.action for node in self.path()[1:]]
  3056.  
  3057. def solve(self):
  3058. "Return the sequence of states to go from the root to this node."
  3059. return [node.state for node in self.path()[0:]]
  3060.  
  3061. def path(self):
  3062. "Return a list of nodes forming the path from the root to this node."
  3063. x, result = self, []
  3064. while x:
  3065. result.append(x)
  3066. x = x.parent
  3067. return list(reversed(result))
  3068.  
  3069. # We want for a queue of nodes in breadth_first_search or
  3070. # astar_search to have no duplicated states, so we treat nodes
  3071. # with the same state as equal. [Problem: this may not be what you
  3072. # want in other contexts.]
  3073.  
  3074. def __eq__(self, other):
  3075. return isinstance(other, Node) and self.state == other.state
  3076.  
  3077. def __hash__(self):
  3078. return hash(self.state)
  3079.  
  3080.  
  3081. # ________________________________________________________________________________________________________
  3082. #Neinformirano prebaruvanje vo ramki na drvo
  3083. #Vo ramki na drvoto ne razresuvame jamki
  3084.  
  3085. def tree_search(problem, fringe):
  3086. """Search through the successors of a problem to find a goal.
  3087. The argument fringe should be an empty queue."""
  3088. fringe.append(Node(problem.initial))
  3089. while fringe:
  3090. node = fringe.pop()
  3091. print (node.state)
  3092. if problem.goal_test(node.state):
  3093. return node
  3094. fringe.extend(node.expand(problem))
  3095. return None
  3096.  
  3097.  
  3098. def breadth_first_tree_search(problem):
  3099. "Search the shallowest nodes in the search tree first."
  3100. return tree_search(problem, FIFOQueue())
  3101.  
  3102.  
  3103. def depth_first_tree_search(problem):
  3104. "Search the deepest nodes in the search tree first."
  3105. return tree_search(problem, Stack())
  3106.  
  3107.  
  3108. # ________________________________________________________________________________________________________
  3109. #Neinformirano prebaruvanje vo ramki na graf
  3110. #Osnovnata razlika e vo toa sto ovde ne dozvoluvame jamki t.e. povtoruvanje na sostojbi
  3111.  
  3112. def graph_search(problem, fringe):
  3113. """Search through the successors of a problem to find a goal.
  3114. The argument fringe should be an empty queue.
  3115. If two paths reach a state, only use the best one."""
  3116. closed = {}
  3117. fringe.append(Node(problem.initial))
  3118. while fringe:
  3119. node = fringe.pop()
  3120. if problem.goal_test(node.state):
  3121. return node
  3122. if node.state not in closed:
  3123. closed[node.state] = True
  3124. fringe.extend(node.expand(problem))
  3125. return None
  3126.  
  3127.  
  3128. def breadth_first_graph_search(problem):
  3129. "Search the shallowest nodes in the search tree first."
  3130. return graph_search(problem, FIFOQueue())
  3131.  
  3132.  
  3133. def depth_first_graph_search(problem):
  3134. "Search the deepest nodes in the search tree first."
  3135. return graph_search(problem, Stack())
  3136.  
  3137.  
  3138. def uniform_cost_search(problem):
  3139. "Search the nodes in the search tree with lowest cost first."
  3140. return graph_search(problem, PriorityQueue(lambda a, b: a.path_cost < b.path_cost))
  3141.  
  3142.  
  3143. def depth_limited_search(problem, limit=50):
  3144. "depth first search with limited depth"
  3145.  
  3146. def recursive_dls(node, problem, limit):
  3147. "helper function for depth limited"
  3148. cutoff_occurred = False
  3149. if problem.goal_test(node.state):
  3150. return node
  3151. elif node.depth == limit:
  3152. return 'cutoff'
  3153. else:
  3154. for successor in node.expand(problem):
  3155. result = recursive_dls(successor, problem, limit)
  3156. if result == 'cutoff':
  3157. cutoff_occurred = True
  3158. elif result != None:
  3159. return result
  3160. if cutoff_occurred:
  3161. return 'cutoff'
  3162. else:
  3163. return None
  3164.  
  3165. # Body of depth_limited_search:
  3166. return recursive_dls(Node(problem.initial), problem, limit)
  3167.  
  3168.  
  3169. #def iterative_deepening_search(problem):
  3170. #
  3171. # for depth in xrange(sys.maxint):
  3172. # result = depth_limited_search(problem, depth)
  3173. # if result is not 'cutoff':
  3174. # return result
  3175.  
  3176.  
  3177.  
  3178. # _________________________________________________________________________________________________________
  3179. #PRIMER 1 : PROBLEM SO DVA SADA SO VODA
  3180. #OPIS: Dadeni se dva sada J0 i J1 so kapaciteti C0 i C1
  3181. #Na pocetok dvata sada se polni. Inicijalnata sostojba moze da se prosledi na pocetok
  3182. #Problemot e kako da se stigne do sostojba vo koja J0 ke ima G0 litri, a J1 ke ima G1 litri
  3183. #AKCII: 1. Da se isprazni bilo koj od sadovite
  3184. #2. Da se prefrli tecnosta od eden sad vo drug so toa sto ne moze da se nadmine kapacitetot na sadovite
  3185. # Moze da ima i opcionalen tret vid na akcii 3. Napolni bilo koj od sadovite (studentite da ja implementiraat ovaa varijanta)
  3186. # ________________________________________________________________________________________________________
  3187.  
  3188. class WJ(Problem):
  3189. """STATE: Torka od oblik (3,2) if jug J0 has 3 liters and J1 2 liters
  3190. Opcionalno moze za nekoj od sadovite da se sretne i vrednost '*' sto znaci deka e nebitno kolku ima vo toj sad
  3191. GOAL: Predefinirana sostojba do kade sakame da stigneme. Ako ne interesira samo eden sad za drugiot mozeme da stavime '*'
  3192. PROBLEM: Se specificiraat kapacitetite na sadovite, pocetna sostojba i cel """
  3193.  
  3194. def __init__(self, capacities=(5, 2), initial=(5, 0), goal=(0, 1)):
  3195. self.capacities = capacities
  3196. self.initial = initial
  3197. self.goal = goal
  3198.  
  3199. def goal_test(self, state):
  3200. """ Vraka true ako sostojbata e celna """
  3201. g = self.goal
  3202. return (state[0] == g[0] or g[0] == '*') and \
  3203. (state[1] == g[1] or g[1] == '*')
  3204.  
  3205. def successor(self, J):
  3206. """Vraka recnik od sledbenici na sostojbata"""
  3207. successors = dict()
  3208. J0, J1 = J
  3209. #print (J)
  3210. (C0, C1) = self.capacities
  3211. if J0 > 0:
  3212. Jnew = 0, J1
  3213. successors['dump jug 0'] = Jnew
  3214. if J1 > 0:
  3215. Jnew = J0, 0
  3216. successors['dump jug 1'] = Jnew
  3217. if J1 < C1 and J0 > 0:
  3218. delta = min(J0, C1 - J1)
  3219. Jnew = J0 - delta, J1 + delta
  3220. successors['pour jug 0 into jug 1'] = Jnew
  3221. if J0 < C0 and J1 > 0:
  3222. delta = min(J1, C0 - J0)
  3223. Jnew = J0 + delta, J1 - delta
  3224. successors['pour jug 1 into jug 0'] = Jnew
  3225. return successors
  3226.  
  3227. def actions(self, state):
  3228.  
  3229. return self.successor(state).keys()
  3230.  
  3231. def result(self, state, action):
  3232. possible = self.successor(state)
  3233. return possible[action]
  3234.  
  3235. # So vaka definiraniot problem mozeme da gi koristime site neinformirani prebaruvanja
  3236. # Vo prodolzenie se dadeni mozni povici (vnimavajte za da moze da napravite povik mora da definirate problem)
  3237. #
  3238. WJInstance = WJ((5, 2), (5, 2), ('*', 1))
  3239. #print (WJInstance)
  3240. #
  3241. #answer1 = breadth_first_tree_search(WJInstance)
  3242. #print (answer1.solve())
  3243. #
  3244. # answer2 = depth_first_tree_search(WJInstance) #vnimavajte na ovoj povik, moze da vleze vo beskonecna jamka
  3245. # print answer2.solve()
  3246. #
  3247. #
  3248. #answer3 = breadth_first_graph_search(WJInstance)
  3249. #print (answer3.solve())
  3250. #
  3251. # answer4 = depth_first_graph_search(WJInstance)
  3252. # print answer4.solve()
  3253. #
  3254. # answer5 = depth_limited_search(WJInstance)
  3255. # print answer5.solve()
  3256. #
  3257. # answer6 = iterative_deepening_search(WJInstance)
  3258. # print answer6.solve()
  3259.  
  3260.  
  3261.  
  3262.  
  3263. Prepreki = [(6, 1), (6, 2), (4, 2), (2, 3), (1, 4), (1, 6), (1, 8), \
  3264. (2, 9), (6, 4), (5, 5), (6, 7), (5, 7), (4, 7), (4, 8)]
  3265.  
  3266. def goreAtomH1(A):
  3267. while (A[0] > 0 and A[0] < 8 and A[1] > 0 and A[1] < 10 and \
  3268. ((A[0], A[1]) not in Prepreki) and \
  3269. ((A[0], A[1]) not in ((A[2], A[3]), (A[4], A[5])))):
  3270. X = A[0]
  3271. X = X - 1
  3272. A = X, A[1], A[2], A[3], A[4], A[5]
  3273. Anew = A[0] + 1, A[1]
  3274. return Anew
  3275.  
  3276. def doluAtomH1(A):
  3277. while(A[0]>0 and A[0] < 8 and A[1] > 0 and A[1] < 10 and((A[0], A[1]) not in Prepreki) and \
  3278. ((A[0], A[1]) not in ((A[2], A[3]), (A[4], A[5])))):
  3279. x = A[0]
  3280. x = x + 1
  3281. A = x, A[1], A[2], A[3], A[4], A[5]
  3282. Anew = A[0] - 1, A[1]
  3283. return Anew
  3284.  
  3285. def levoAtomH1(A):
  3286. while(A[0]>0 and A[0] < 8 and A[1] > 0 and A[1] < 10 and((A[0], A[1]) not in Prepreki) and \
  3287. ((A[0], A[1]) not in ((A[2], A[3]), (A[4], A[5])))):
  3288. y = A[1]
  3289. y = y - 1
  3290. A = A[0], y, A[2], A[3], A[4], A[5]
  3291. Anew = A[0], A[1] + 1
  3292. return Anew
  3293.  
  3294. def desnoAtomH1(A):
  3295. while(A[0]>0 and A[0] < 8 and A[1] > 0 and A[1] < 10 and((A[0], A[1]) not in Prepreki) and \
  3296. ((A[0], A[1]) not in ((A[2], A[3]), (A[4], A[5])))):
  3297. y = A[1]
  3298. y = y + 1
  3299. A = A[0], y, A[2], A[3], A[4], A[5]
  3300. Anew = A[0], A[1] - 1
  3301. return Anew
  3302.  
  3303.  
  3304.  
  3305. def doluAtomO(A):
  3306. while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and \
  3307. ((A[2], A[3]) not in Prepreki) and \
  3308. ((A[2], A[3]) not in ((A[0], A[1]), (A[4], A[5])))):
  3309. X = A[2]
  3310. X = X + 1
  3311. A = A[0], A[1], X, A[3], A[4], A[5]
  3312. Anew = A[2] - 1, A[3]
  3313. return Anew
  3314.  
  3315. def goreAtomO(A):
  3316. while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and \
  3317. ((A[2], A[3]) not in Prepreki) and \
  3318. ((A[2], A[3]) not in ((A[0], A[1]), (A[4], A[5])))):
  3319. X = A[2]
  3320. X = X - 1
  3321. A = A[0], A[1], X, A[3], A[4], A[5]
  3322. Anew = A[2] + 1, A[3]
  3323. return Anew
  3324.  
  3325. def desnoAtomO(A):
  3326. while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and \
  3327. ((A[2], A[3]) not in Prepreki) and \
  3328. ((A[2], A[3]) not in ((A[0], A[1]), (A[4], A[5])))):
  3329. Y = A[3]
  3330. Y = Y + 1
  3331. A = A[0], A[1], A[2], Y, A[4], A[5]
  3332. Anew = A[2], A[3] - 1
  3333. return Anew
  3334.  
  3335. def levoAtomO(A):
  3336. while (A[2] > 0 and A[2] < 8 and A[3] > 0 and A[3] < 10 and \
  3337. ((A[2], A[3]) not in Prepreki) and \
  3338. ((A[2], A[3]) not in ((A[0], A[1]), (A[4], A[5])))):
  3339. Y = A[3]
  3340. Y = Y - 1
  3341. A = A[0], A[1], A[2], Y, A[4], A[5]
  3342. Anew = A[2], A[3] + 1
  3343. return Anew
  3344.  
  3345.  
  3346. def goreAtomH2(A):
  3347. while (A[4] > 0 and A[4] < 8 and A[5] > 0 and A[5] < 10 and \
  3348. ((A[4], A[5]) not in Prepreki) and \
  3349. ((A[4], A[5]) not in ((A[2], A[3]), (A[0], A[1])))):
  3350. X = A[4]
  3351. X = X - 1
  3352. A = A[0], A[1], A[2], A[3], X, A[5]
  3353. Anew = A[4] + 1, A[5]
  3354. return Anew
  3355.  
  3356. def doluAtomH2(A):
  3357. while(A[4] > 0 and A[4] < 8 and A[5] > 0 and A[5] < 10 and((A[4], A[5]) not in Prepreki) and \
  3358. ((A[4], A[5]) not in ((A[2], A[3]), (A[0], A[1])))):
  3359. X = A[4]
  3360. X = X + 1
  3361. A = A[0], A[1], A[2], A[3], X, A[5]
  3362. Anew = A[4] - 1, A[5]
  3363. return Anew
  3364.  
  3365. def levoAtomH2(A):
  3366. while(A[4] > 0 and A[4] < 8 and A[5] > 0 and A[5] < 10 and((A[4], A[5]) not in Prepreki) and \
  3367. ((A[4], A[5]) not in ((A[2], A[3]), (A[0], A[1])))):
  3368. y = A[5]
  3369. y = y - 1
  3370. A = A[0], A[1], A[2], A[3], A[4], y
  3371. Anew = A[4], A[5] + 1
  3372. return Anew
  3373.  
  3374. def desnoAtomH2(A):
  3375. while(A[4] > 0 and A[4] < 8 and A[5] > 0 and A[5] < 10 and((A[4], A[5]) not in Prepreki) and \
  3376. ((A[4], A[5]) not in ((A[2], A[3]), (A[0], A[1])))):
  3377. y = A[5]
  3378. y = y + 1
  3379. A = A[0], A[1], A[2], A[3], A[4], y
  3380. Anew = A[4], A[5] - 1
  3381. return Anew
  3382.  
  3383. class Molekula(Problem):
  3384.  
  3385. def __init__(self, initial):
  3386. self.initial = initial
  3387.  
  3388. def goal_test(self, state):
  3389. H1x = state[0]
  3390. H1y = state[1]
  3391. Ox = state[2]
  3392. Oy = state[3]
  3393. H2x = state[4]
  3394. H2y = state[5]
  3395. return (H1x + 1 == Ox and Ox + 1 == H2x and Oy == H1y \
  3396. and H2y == Oy)
  3397.  
  3398. def successor(self, state):
  3399. successors = dict()
  3400. H1 = state[0], state[1]
  3401. O = state[2], state[3]
  3402. H2 = state[4], state[5]
  3403.  
  3404. H1new = goreAtomH1(state)
  3405. Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
  3406. successors['GoreH1'] = Statenew
  3407.  
  3408. H1new = doluAtomH1(state)
  3409. Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
  3410. successors['DoluH1'] = Statenew
  3411.  
  3412. H1new = desnoAtomH1(state)
  3413. Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
  3414. successors['DesnoH1'] = Statenew
  3415.  
  3416. H1new = levoAtomH1(state)
  3417. Statenew = (H1new[0], H1new[1], O[0], O[1], H2[0], H2[1])
  3418. successors['LevoH1'] = Statenew
  3419.  
  3420. Onew = goreAtomO(state)
  3421. Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
  3422. successors['GoreO'] = Statenew
  3423.  
  3424. Onew = doluAtomO(state)
  3425. Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
  3426. successors['DoluO'] = Statenew
  3427.  
  3428. Onew = levoAtomO(state)
  3429. Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
  3430. successors['LevoO'] = Statenew
  3431.  
  3432. Onew = desnoAtomO(state)
  3433. Statenew = (H1[0], H1[1], Onew[0], Onew[1], H2[0], H2[1])
  3434. successors['DesnoO'] = Statenew
  3435.  
  3436. H2new = goreAtomH2(state)
  3437. Statenew = (H1[0], H1[1], O[0], O[1], H2new[0], H2new[1])
  3438. successors['GoreH2'] = Statenew
  3439.  
  3440. H2new = doluAtomH2(state)
  3441. Statenew = (H1[0], H1[1], O[0], O[1], H2new[0], H2new[1])
  3442. successors['DoluH2'] = Statenew
  3443.  
  3444. H2new = desnoAtomH2(state)
  3445. Statenew = (H1[0], H1[1], O[0], O[1], H2new[0], H2new[1])
  3446. successors['DesnoH2'] = Statenew
  3447.  
  3448. H2new = levoAtomH2(state)
  3449. Statenew = (H1[0], H1[1], O[0], O[1], H2new[0], H2new[1])
  3450. successors['LevoH2'] = Statenew
  3451.  
  3452. return successors
  3453.  
  3454. def actions(self, state):
  3455. return self.successor(state).keys()
  3456.  
  3457. def result(self, state, action):
  3458. possible = self.successor(state)
  3459. return possible[action]
  3460.  
  3461. H1AtomRedica = int(input())
  3462. H1AtomKolona = int(input())
  3463. OAtomRedica = int(input())
  3464. OAtomKolona = int(input())
  3465. H2AtomRedica = int(input())
  3466. H2AtomKolona = int(input())
  3467.  
  3468. M = (H1AtomRedica, H1AtomKolona, OAtomRedica, OAtomKolona, H2AtomRedica, H2AtomKolona)
  3469. MolekulaInstance = Molekula(M)
  3470.  
  3471. answer = breadth_first_graph_search(MolekulaInstance)
  3472. print (answer.solution())
  3473.  
  3474. **********
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement