This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!

Finished!!

By: loubot on May 2nd, 2013  |  syntax: Python  |  size: 2.43 KB  |  views: 616  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. def bruteForceSearch(graph,start,end,maxTotalDist,maxDistOutdoors,visited = [],dist =0,outDist = 0):
  2.     """
  3.    Finds the shortest path from start to end using brute-force approach.
  4.    The total distance travelled on the path must not exceed maxTotalDist, and
  5.    the distance spent outdoor on this path must not exceed maxDisOutdoors.
  6.  
  7.    Parameters:
  8.        digraph: instance of class Digraph or its subclass
  9.        start, end: start & end building numbers (strings)
  10.        maxTotalDist : maximum total distance on a path (integer)
  11.        maxDistOutdoors: maximum distance spent outdoors on a path (integer)
  12.  
  13.    Assumes:
  14.        start and end are numbers for existing buildings in graph
  15.  
  16.    Returns:
  17.        The shortest-path from start to end, represented by
  18.        a list of building numbers (in strings), [n_1, n_2, ..., n_k],
  19.        where there exists an edge from n_i to n_(i+1) in digraph,
  20.        for all 1 <= i < k.
  21.  
  22.        If there exists no path that satisfies maxTotalDist and
  23.        maxDistOutdoors constraints, then raises a ValueError.
  24.    """
  25.     path = [str(start)]
  26.     pathDist = [str(dist)]
  27.     pathOut = [str(outDist)]
  28.     if MITNode(start) == MITNode(end):
  29.         return path, dist,outDist
  30.     shortest = None
  31.     if visited == []:
  32.         visited = [str(start)]
  33.     for edge in graph.childrenOf(MITNode(start)):
  34.         if str(edge.getDestination()) not in visited:
  35.             visited = visited + [str(edge.getDestination())]
  36.  
  37.             possPath, possDist,possOutDist = bruteForceSearch(graph,edge.getDestination(),\
  38.                   end,maxTotalDist,maxDistOutdoors,visited, edge.getDistance(),edge.getOutDist())
  39.  
  40.  
  41.             if possPath == None:
  42.                 continue
  43.             if maxDistOutdoors == 0:
  44.                 if possOutDist != 0:
  45.                     continue
  46.             if shortest == None or possDist < bestDist:
  47.                 shortest = possPath
  48.                 bestDist = possDist
  49.                 bestOutDist = possOutDist
  50.     if shortest == None:
  51.         path = None
  52.         retPathDist = [str(0)]
  53.         retOutDist = [str(0)]
  54.     elif (dist + bestDist) > maxTotalDist or (outDist + bestOutDist) > maxDistOutdoors:
  55.         path = None
  56.         retPathDist = [str(0)]
  57.         retOutDist = [str(0)]
  58.  
  59.     else:
  60.         path = path + shortest
  61.         retPathDist = dist + bestDist
  62.         retOutDist = outDist + bestOutDist
  63.     return path, retPathDist,retOutDist
clone this paste RAW Paste Data