fork download
copy 
  1. # Graphs and Graph Problems
  2. import math
  3. # Python modul vo koj se implementirani algoritmite za neinformirano i informirano prebaruvanje
  4.  
  5. # ______________________________________________________________________________________________
  6. # Improtiranje na dopolnitelno potrebni paketi za funkcioniranje na kodovite
  7.  
  8. import sys
  9. import bisect
  10.  
  11. infinity = float('inf')  # sistemski definirana vrednost za beskonecnost
  12.  
  13.  
  14. # ______________________________________________________________________________________________
  15. # Definiranje na pomosni strukturi za cuvanje na listata na generirani, no neprovereni jazli
  16.  
  17. class Queue:
  18.     """Queue is an abstract class/interface. There are three types:
  19.         Stack(): A Last In First Out Queue.
  20.         FIFOQueue(): A First In First Out Queue.
  21.         PriorityQueue(order, f): Queue in sorted order (default min-first).
  22.     Each type supports the following methods and functions:
  23.         q.append(item)  -- add an item to the queue
  24.         q.extend(items) -- equivalent to: for item in items: q.append(item)
  25.         q.pop()         -- return the top item from the queue
  26.         len(q)          -- number of items in q (also q.__len())
  27.         item in q       -- does q contain item?
  28.     Note that isinstance(Stack(), Queue) is false, because we implement stacks
  29.     as lists.  If Python ever gets interfaces, Queue will be an interface."""
  30.  
  31.     def __init__(self):
  32.         raise NotImplementedError
  33.  
  34.     def extend(self, items):
  35.         for item in items:
  36.             self.append(item)
  37.  
  38.  
  39. def Stack():
  40.     """A Last-In-First-Out Queue."""
  41.     return []
  42.  
  43.  
  44. class FIFOQueue(Queue):
  45.     """A First-In-First-Out Queue."""
  46.  
  47.     def __init__(self):
  48.         self.A = []
  49.         self.start = 0
  50.  
  51.     def append(self, item):
  52.         self.A.append(item)
  53.  
  54.     def __len__(self):
  55.         return len(self.A) - self.start
  56.  
  57.     def extend(self, items):
  58.         self.A.extend(items)
  59.  
  60.     def pop(self):
  61.         e = self.A[self.start]
  62.         self.start += 1
  63.         if self.start > 5 and self.start > len(self.A) / 2:
  64.             self.A = self.A[self.start:]
  65.             self.start = 0
  66.         return e
  67.  
  68.     def __contains__(self, item):
  69.         return item in self.A[self.start:]
  70.  
  71.  
  72. class PriorityQueue(Queue):
  73.     """A queue in which the minimum (or maximum) element (as determined by f and
  74.     order) is returned first. If order is min, the item with minimum f(x) is
  75.     returned first; if order is max, then it is the item with maximum f(x).
  76.     Also supports dict-like lookup. This structure will be most useful in informed searches"""
  77.  
  78.     def __init__(self, order=min, f=lambda x: x):
  79.         self.A = []
  80.         self.order = order
  81.         self.f = f
  82.  
  83.     def append(self, item):
  84.         bisect.insort(self.A, (self.f(item), item))
  85.  
  86.     def __len__(self):
  87.         return len(self.A)
  88.  
  89.     def pop(self):
  90.         if self.order == min:
  91.             return self.A.pop(0)[1]
  92.         else:
  93.             return self.A.pop()[1]
  94.  
  95.     def __contains__(self, item):
  96.         return any(item == pair[1] for pair in self.A)
  97.  
  98.     def __getitem__(self, key):
  99.         for _, item in self.A:
  100.             if item == key:
  101.                 return item
  102.  
  103.     def __delitem__(self, key):
  104.         for i, (value, item) in enumerate(self.A):
  105.             if item == key:
  106.                 self.A.pop(i)
  107.  
  108.  
  109. # ______________________________________________________________________________________________
  110. # Definiranje na klasa za strukturata na problemot koj ke go resavame so prebaruvanje
  111. # Klasata Problem e apstraktna klasa od koja pravime nasleduvanje za definiranje na osnovnite karakteristiki
  112. # na sekoj eden problem sto sakame da go resime
  113.  
  114.  
  115. class Problem:
  116.     """The abstract class for a formal problem.  You should subclass this and
  117.     implement the method successor, and possibly __init__, goal_test, and
  118.     path_cost. Then you will create instances of your subclass and solve them
  119.     with the various search functions."""
  120.  
  121.     def __init__(self, initial, goal=None):
  122.         """The constructor specifies the initial state, and possibly a goal
  123.         state, if there is a unique goal.  Your subclass's constructor can add
  124.         other arguments."""
  125.         self.initial = initial
  126.         self.goal = goal
  127.  
  128.     def successor(self, state):
  129.         """Given a state, return a dictionary of {action : state} pairs reachable
  130.         from this state. If there are many successors, consider an iterator
  131.         that yields the successors one at a time, rather than building them
  132.         all at once. Iterators will work fine within the framework. Yielding is not supported in Python 2.7"""
  133.         raise NotImplementedError
  134.  
  135.     def actions(self, state):
  136.         """Given a state, return a list of all actions possible from that state"""
  137.         raise NotImplementedError
  138.  
  139.     def result(self, state, action):
  140.         """Given a state and action, return the resulting state"""
  141.         raise NotImplementedError
  142.  
  143.     def goal_test(self, state):
  144.         """Return True if the state is a goal. The default method compares the
  145.         state to self.goal, as specified in the constructor. Implement this
  146.         method if checking against a single self.goal is not enough."""
  147.         return state == self.goal
  148.  
  149.     def path_cost(self, c, state1, action, state2):
  150.         """Return the cost of a solution path that arrives at state2 from
  151.         state1 via action, assuming cost c to get up to state1. If the problem
  152.         is such that the path doesn't matter, this function will only look at
  153.         state2.  If the path does matter, it will consider c and maybe state1
  154.         and action. The default method costs 1 for every step in the path."""
  155.         return c + 1
  156.  
  157.     def value(self):
  158.         """For optimization problems, each state has a value.  Hill-climbing
  159.         and related algorithms try to maximize this value."""
  160.         raise NotImplementedError
  161.  
  162.  
  163. # ______________________________________________________________________________
  164. # Definiranje na klasa za strukturata na jazel od prebaruvanje
  165. # Klasata Node ne se nasleduva
  166.  
  167. class Node:
  168.     """A node in a search tree. Contains a pointer to the parent (the node
  169.     that this is a successor of) and to the actual state for this node. Note
  170.     that if a state is arrived at by two paths, then there are two nodes with
  171.     the same state.  Also includes the action that got us to this state, and
  172.     the total path_cost (also known as g) to reach the node.  Other functions
  173.     may add an f and h value; see best_first_graph_search and astar_search for
  174.     an explanation of how the f and h values are handled. You will not need to
  175.     subclass this class."""
  176.  
  177.     def __init__(self, state, parent=None, action=None, path_cost=0):
  178.         "Create a search tree Node, derived from a parent by an action."
  179.         self.state = state
  180.         self.parent = parent
  181.         self.action = action
  182.         self.path_cost = path_cost
  183.         self.depth = 0
  184.         if parent:
  185.             self.depth = parent.depth + 1
  186.  
  187.     def __repr__(self):
  188.         return "<Node %s>" % (self.state,)
  189.  
  190.     def __lt__(self, node):
  191.         return self.state < node.state
  192.  
  193.     def expand(self, problem):
  194.         "List the nodes reachable in one step from this node."
  195.         return [self.child_node(problem, action)
  196.                 for action in problem.actions(self.state)]
  197.  
  198.     def child_node(self, problem, action):
  199.         "Return a child node from this node"
  200.         next = problem.result(self.state, action)
  201.         return Node(next, self, action,
  202.                     problem.path_cost(self.path_cost, self.state,
  203.                                       action, next))
  204.  
  205.     def solution(self):
  206.         "Return the sequence of actions to go from the root to this node."
  207.         return [node.action for node in self.path()[1:]]
  208.  
  209.     def solve(self):
  210.         "Return the sequence of states to go from the root to this node."
  211.         return [node.state for node in self.path()[0:]]
  212.  
  213.     def path(self):
  214.         "Return a list of nodes forming the path from the root to this node."
  215.         x, result = self, []
  216.         while x:
  217.             result.append(x)
  218.             x = x.parent
  219.         return list(reversed(result))
  220.  
  221.     # We want for a queue of nodes in breadth_first_search or
  222.     # astar_search to have no duplicated states, so we treat nodes
  223.     # with the same state as equal. [Problem: this may not be what you
  224.     # want in other contexts.]
  225.  
  226.     def __eq__(self, other):
  227.         return isinstance(other, Node) and self.state == other.state
  228.  
  229.     def __hash__(self):
  230.         return hash(self.state)
  231.  
  232.  
  233. # ________________________________________________________________________________________________________
  234. #Neinformirano prebaruvanje vo ramki na drvo
  235. #Vo ramki na drvoto ne razresuvame jamki
  236.  
  237. def tree_search(problem, fringe):
  238.     """Search through the successors of a problem to find a goal.
  239.     The argument fringe should be an empty queue."""
  240.     fringe.append(Node(problem.initial))
  241.     while fringe:
  242.         node = fringe.pop()
  243.         print (node.state)
  244.         if problem.goal_test(node.state):
  245.             return node
  246.         fringe.extend(node.expand(problem))
  247.     return None
  248.  
  249.  
  250. def breadth_first_tree_search(problem):
  251.     "Search the shallowest nodes in the search tree first."
  252.     return tree_search(problem, FIFOQueue())
  253.  
  254.  
  255. def depth_first_tree_search(problem):
  256.     "Search the deepest nodes in the search tree first."
  257.     return tree_search(problem, Stack())
  258.  
  259.  
  260. # ________________________________________________________________________________________________________
  261. #Neinformirano prebaruvanje vo ramki na graf
  262. #Osnovnata razlika e vo toa sto ovde ne dozvoluvame jamki t.e. povtoruvanje na sostojbi
  263.  
  264. def graph_search(problem, fringe):
  265.     """Search through the successors of a problem to find a goal.
  266.     The argument fringe should be an empty queue.
  267.     If two paths reach a state, only use the best one."""
  268.     closed = {}
  269.     fringe.append(Node(problem.initial))
  270.     while fringe:
  271.         node = fringe.pop()
  272.         if problem.goal_test(node.state):
  273.             return node
  274.         if node.state not in closed:
  275.             closed[node.state] = True
  276.             fringe.extend(node.expand(problem))
  277.     return None
  278.  
  279.  
  280. def breadth_first_graph_search(problem):
  281.     "Search the shallowest nodes in the search tree first."
  282.     return graph_search(problem, FIFOQueue())
  283.  
  284.  
  285. def depth_first_graph_search(problem):
  286.     "Search the deepest nodes in the search tree first."
  287.     return graph_search(problem, Stack())
  288.  
  289.  
  290. def uniform_cost_search(problem):
  291.     "Search the nodes in the search tree with lowest cost first."
  292.     return graph_search(problem, PriorityQueue(lambda a, b: a.path_cost < b.path_cost))
  293.  
  294.  
  295. def depth_limited_search(problem, limit=50):
  296.     "depth first search with limited depth"
  297.  
  298.     def recursive_dls(node, problem, limit):
  299.         "helper function for depth limited"
  300.         cutoff_occurred = False
  301.         if problem.goal_test(node.state):
  302.             return node
  303.         elif node.depth == limit:
  304.             return 'cutoff'
  305.         else:
  306.             for successor in node.expand(problem):
  307.                 result = recursive_dls(successor, problem, limit)
  308.                 if result == 'cutoff':
  309.                     cutoff_occurred = True
  310.                 elif result != None:
  311.                     return result
  312.         if cutoff_occurred:
  313.             return 'cutoff'
  314.         else:
  315.             return None
  316.  
  317.     # Body of depth_limited_search:
  318.     return recursive_dls(Node(problem.initial), problem, limit)
  319.  
  320.  
  321. def iterative_deepening_search(problem):
  322.  
  323.     for depth in range(sys.maxint):
  324.         result = depth_limited_search(problem, depth)
  325.         if result is not 'cutoff':
  326.             return result
  327.  
  328.  
  329. # ________________________________________________________________________________________________________
  330. #Pomosna funkcija za informirani prebaruvanja
  331. #So pomos na ovaa funkcija gi keshirame rezultatite od funkcijata na evaluacija
  332.  
  333. def memoize(fn, slot=None):
  334.     """Memoize fn: make it remember the computed value for any argument list.
  335.     If slot is specified, store result in that slot of first argument.
  336.     If slot is false, store results in a dictionary."""
  337.     if slot:
  338.         def memoized_fn(obj, *args):
  339.             if hasattr(obj, slot):
  340.                 return getattr(obj, slot)
  341.             else:
  342.                 val = fn(obj, *args)
  343.                 setattr(obj, slot, val)
  344.                 return val
  345.     else:
  346.         def memoized_fn(*args):
  347.             if not memoized_fn.cache.has_key(args):
  348.                 memoized_fn.cache[args] = fn(*args)
  349.             return memoized_fn.cache[args]
  350.  
  351.         memoized_fn.cache = {}
  352.     return memoized_fn
  353.  
  354.  
  355. # ________________________________________________________________________________________________________
  356. #Informirano prebaruvanje vo ramki na graf
  357.  
  358. def best_first_graph_search(problem, f):
  359.     """Search the nodes with the lowest f scores first.
  360.     You specify the function f(node) that you want to minimize; for example,
  361.     if f is a heuristic estimate to the goal, then we have greedy best
  362.     first search; if f is node.depth then we have breadth-first search.
  363.     There is a subtlety: the line "f = memoize(f, 'f')" means that the f
  364.     values will be cached on the nodes as they are computed. So after doing
  365.     a best first search you can examine the f values of the path returned."""
  366.  
  367.     f = memoize(f, 'f')
  368.     node = Node(problem.initial)
  369.     if problem.goal_test(node.state):
  370.         return node
  371.     frontier = PriorityQueue(min, f)
  372.     frontier.append(node)
  373.     explored = set()
  374.     while frontier:
  375.         node = frontier.pop()
  376.         if problem.goal_test(node.state):
  377.             return node
  378.         explored.add(node.state)
  379.         for child in node.expand(problem):
  380.             if child.state not in explored and child not in frontier:
  381.                 frontier.append(child)
  382.             elif child in frontier:
  383.                 incumbent = frontier[child]
  384.                 if f(child) < f(incumbent):
  385.                     del frontier[incumbent]
  386.                     frontier.append(child)
  387.     return None
  388.  
  389.  
  390. def greedy_best_first_graph_search(problem, h=None):
  391.     "Greedy best-first search is accomplished by specifying f(n) = h(n)"
  392.     h = memoize(h or problem.h, 'h')
  393.     return best_first_graph_search(problem, h)
  394.  
  395.  
  396. def astar_search(problem, h=None):
  397.     "A* search is best-first graph search with f(n) = g(n)+h(n)."
  398.     h = memoize(h or problem.h, 'h')
  399.     return best_first_graph_search(problem, lambda n: n.path_cost + h(n))
  400.  
  401.  
  402. # ________________________________________________________________________________________________________
  403. #Dopolnitelni prebaruvanja
  404. #Recursive_best_first_search e implementiran
  405. #Kako zadaca za studentite da gi implementiraat SMA* i IDA*
  406.  
  407. def recursive_best_first_search(problem, h=None):
  408.     h = memoize(h or problem.h, 'h')
  409.  
  410.     def RBFS(problem, node, flimit):
  411.         if problem.goal_test(node.state):
  412.             return node, 0  # (The second value is immaterial)
  413.         successors = node.expand(problem)
  414.         if len(successors) == 0:
  415.             return None, infinity
  416.         for s in successors:
  417.             s.f = max(s.path_cost + h(s), node.f)
  418.         while True:
  419.             # Order by lowest f value
  420.             successors.sort(key=lambda x: x.f)
  421.             best = successors[0]
  422.             if best.f > flimit:
  423.                 return None, best.f
  424.             if len(successors) > 1:
  425.                 alternative = successors[1].f
  426.             else:
  427.                 alternative = infinity
  428.             result, best.f = RBFS(problem, best, min(flimit, alternative))
  429.             if result is not None:
  430.                 return result, best.f
  431.  
  432.     node = Node(problem.initial)
  433.     node.f = h(node)
  434.     result, bestf = RBFS(problem, node, infinity)
  435.     return result
  436.  
  437. def distance(a, b):
  438.     """The distance between two (x, y) points."""
  439.     return math.hypot((a[0] - b[0]), (a[1] - b[1]))
  440.  
  441.  
  442. class Graph:
  443.     """A graph connects nodes (verticies) by edges (links).  Each edge can also
  444.     have a length associated with it.  The constructor call is something like:
  445.         g = Graph({'A': {'B': 1, 'C': 2})
  446.     this makes a graph with 3 nodes, A, B, and C, with an edge of length 1 from
  447.     A to B,  and an edge of length 2 from A to C.  You can also do:
  448.         g = Graph({'A': {'B': 1, 'C': 2}, directed=False)
  449.     This makes an undirected graph, so inverse links are also added. The graph
  450.     stays undirected; if you add more links with g.connect('B', 'C', 3), then
  451.     inverse link is also added.  You can use g.nodes() to get a list of nodes,
  452.     g.get('A') to get a dict of links out of A, and g.get('A', 'B') to get the
  453.     length of the link from A to B.  'Lengths' can actually be any object at
  454.     all, and nodes can be any hashable object."""
  455.  
  456.     def __init__(self, dict=None, directed=True):
  457.         self.dict = dict or {}
  458.         self.directed = directed
  459.         if not directed:
  460.             self.make_undirected()
  461.  
  462.     def make_undirected(self):
  463.         """Make a digraph into an undirected graph by adding symmetric edges."""
  464.         for a in list(self.dict.keys()):
  465.             for (b, dist) in self.dict[a].items():
  466.                 self.connect1(b, a, dist)
  467.  
  468.     def connect(self, A, B, distance=1):
  469.         """Add a link from A and B of given distance, and also add the inverse
  470.         link if the graph is undirected."""
  471.         self.connect1(A, B, distance)
  472.         if not self.directed:
  473.             self.connect1(B, A, distance)
  474.  
  475.     def connect1(self, A, B, distance):
  476.         """Add a link from A to B of given distance, in one direction only."""
  477.         self.dict.setdefault(A, {})[B] = distance
  478.  
  479.     def get(self, a, b=None):
  480.         """Return a link distance or a dict of {node: distance} entries.
  481.         .get(a,b) returns the distance or None;
  482.         .get(a) returns a dict of {node: distance} entries, possibly {}."""
  483.         links = self.dict.setdefault(a, {})
  484.         if b is None:
  485.             return links
  486.         else:
  487.             return links.get(b)
  488.  
  489.     def nodes(self):
  490.         """Return a list of nodes in the graph."""
  491.         return list(self.dict.keys())
  492.  
  493.  
  494. def UndirectedGraph(dict=None):
  495.     """Build a Graph where every edge (including future ones) goes both ways."""
  496.     return Graph(dict=dict, directed=False)
  497.  
  498.  
  499. class GraphProblem(Problem):
  500.     """The problem of searching a graph from one node to another."""
  501.  
  502.     def __init__(self, initial, goal, graph):
  503.         Problem.__init__(self, initial, goal)
  504.         self.graph = graph
  505.  
  506.     def actions(self, A):
  507.         """The actions at a graph node are just its neighbors."""
  508.         return list(self.graph.get(A).keys())
  509.  
  510.     def result(self, state, action):
  511.         """The result of going to a neighbor is just that neighbor."""
  512.         return action
  513.  
  514.     def path_cost(self, cost_so_far, A, action, B):
  515.         return cost_so_far + (self.graph.get(A, B) or infinity)
  516.  
  517.     def h(self, node):
  518.         """h function is straight-line distance from a node's state to goal."""
  519.         locs = getattr(self.graph, 'locations', None)
  520.         if locs:
  521.             return int(distance(locs[node.state], locs[self.goal]))
  522.         else:
  523.             return infinity
  524.  
  525.  
  526. # Primer na definiranje na graf kako ekspliciten prostor na sostojbi vo koj ke se prebaruva
  527.  
  528. romania_map = UndirectedGraph(dict(
  529.     Arad=dict(Zerind=75, Sibiu=140, Timisoara=118),
  530.     Bucharest=dict(Urziceni=85, Pitesti=101, Giurgiu=90, Fagaras=211),
  531.     Craiova=dict(Drobeta=120, Rimnicu=146, Pitesti=138),
  532.     Drobeta=dict(Mehadia=75),
  533.     Eforie=dict(Hirsova=86),
  534.     Fagaras=dict(Sibiu=99),
  535.     Hirsova=dict(Urziceni=98),
  536.     Iasi=dict(Vaslui=92, Neamt=87),
  537.     Lugoj=dict(Timisoara=111, Mehadia=70),
  538.     Oradea=dict(Zerind=71, Sibiu=151),
  539.     Pitesti=dict(Rimnicu=97),
  540.     Rimnicu=dict(Sibiu=80),
  541.     Urziceni=dict(Vaslui=142)))
  542.  
  543. #	Sledniot del ne e zadolzitelen da se definiranje
  544. #	Definicijata na klasata kako podrazbirana opcija za hevristicka funkcija koristi pravolinisko rastojanie
  545. #
  546. #	Dokolku slednite informacii ne gi definirate ili ne mozete da gi definirate treba da ja promenite definicijata
  547. #	na funkcijata "h" vo ramki na klasata GraphProblem taka da na soodveten nacin presmetate hevristicka funkcija
  548.  
  549.  
  550. romania_map.locations = dict(
  551.     Arad=(91, 492), Bucharest=(400, 327), Craiova=(253, 288),
  552.     Drobeta=(165, 299), Eforie=(562, 293), Fagaras=(305, 449),
  553.     Giurgiu=(375, 270), Hirsova=(534, 350), Iasi=(473, 506),
  554.     Lugoj=(165, 379), Mehadia=(168, 339), Neamt=(406, 537),
  555.     Oradea=(131, 571), Pitesti=(320, 368), Rimnicu=(233, 410),
  556.     Sibiu=(207, 457), Timisoara=(94, 410), Urziceni=(456, 350),
  557.     Vaslui=(509, 444), Zerind=(108, 531))
  558.  
  559.  
  560. #	Primeri na povici so koi na primer moze da se izminuva grafot za gradovite vo Romanija
  561. #
  562. romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)
  563. #
  564. answer1=breadth_first_tree_search(romania_problem)
  565. print (answer1.solve())
  566. #
  567. #	answer2=breadth_first_search(romania_problem)
  568. #	print answer2.solve()
  569. #
  570. #	answer3=uniform_cost_search(romania_problem)
  571. #	print answer3.solve()
  572. #
  573. #	answer4=astar_search(romania_problem)
  574. #	print answer4.solve()
  575.  
Success #stdin #stdout 0.01s 7252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Arad
Timisoara
Zerind
Sibiu
Arad
Lugoj
Oradea
Arad
Oradea
Rimnicu
Fagaras
Arad
Timisoara
Zerind
Sibiu
Timisoara
Mehadia
Zerind
Sibiu
Timisoara
Zerind
Sibiu
Zerind
Sibiu
Craiova
Pitesti
Sibiu
Bucharest
['Arad', 'Sibiu', 'Fagaras', 'Bucharest']
https://ideone.com/EFFBxb
language:
Python (cpython 2.7.16)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!