Skip to content

Instantly share code, notes, and snippets.

@MoralCode

MoralCode/optimal_tsp.py

Forked from westphahl/optimal_tsp.py
Last active May 7, 2019 17:33
Show Gist options
  • Save MoralCode/15b893c738ea5eb96dee0d9d00d407d7 to your computer and use it in GitHub Desktop.
Save MoralCode/15b893c738ea5eb96dee0d9d00d407d7 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. MoralCode revised this gist May 7, 2019. 1 changed file with 8 additions and 7 deletions.
    15 changes: 8 additions & 7 deletions optimal_tsp.py
    View file
    Original file line number Diff line number Diff line change
    @@ -7,6 +7,7 @@
    routes = []



    def find_paths(node, cities, path, distance):
    # Add way point
    path.append(node)
    @@ -17,17 +18,17 @@ def find_paths(node, cities, path, distance):

    # If path contains all cities and is not a dead end,
    # add path from last to first city and return.
    if (len(cities) == len(path)) and (cities[path[-1]].has_key(path[0])):
    if (len(cities) == len(path)) and (path[0] in cities[path[-1]]):
    global routes
    path.append(path[0])
    distance += cities[path[-2]][path[0]]
    print path, distance
    print(path, distance)
    routes.append([distance, path])
    return

    # Fork paths for all possible cities not yet used
    for city in cities:
    if (city not in path) and (cities[city].has_key(node)):
    if (city not in path) and (node in cities[city]):
    find_paths(city, dict(cities), list(path), distance)


    @@ -46,11 +47,11 @@ def find_paths(node, cities, path, distance):
    'Z': {'BA': 120, 'BE': 85, 'RV': 91}
    }

    print "Start: RAVENSBURG"
    print("Start: RAVENSBURG")
    find_paths('RV', cities, [], 0)
    print "\n"
    print("\n")
    routes.sort()
    if len(routes) != 0:
    print "Shortest route: %s" % routes[0]
    print("Shortest route: %s" % routes[0])
    else:
    print "FAIL!"
    print("FAIL!")
  2. @westphahl westphahl revised this gist Jun 19, 2010. 1 changed file with 5 additions and 5 deletions.
    10 changes: 5 additions & 5 deletions optimal_tsp.py
    View file
    Original file line number Diff line number Diff line change
    @@ -11,7 +11,11 @@ def find_paths(node, cities, path, distance):
    # Add way point
    path.append(node)

    # If path contains all cities and is not a dead end,
    # Calculate path length from current to last node
    if len(path) > 1:
    distance += cities[path[-2]][node]

    # If path contains all cities and is not a dead end,
    # add path from last to first city and return.
    if (len(cities) == len(path)) and (cities[path[-1]].has_key(path[0])):
    global routes
    @@ -21,10 +25,6 @@ def find_paths(node, cities, path, distance):
    routes.append([distance, path])
    return

    # Calculate path length from current to last node
    if len(path) > 1:
    distance += cities[path[-2]][node]

    # Fork paths for all possible cities not yet used
    for city in cities:
    if (city not in path) and (cities[city].has_key(node)):
  3. @westphahl westphahl revised this gist Jun 14, 2010. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions optimal_tsp.py
    View file
    Original file line number Diff line number Diff line change
    @@ -11,8 +11,8 @@ def find_paths(node, cities, path, distance):
    # Add way point
    path.append(node)

    # If path contains all cities, add path from
    # last to first city and return.
    # If path contains all cities and is not a dead end,
    # add path from last to first city and return.
    if (len(cities) == len(path)) and (cities[path[-1]].has_key(path[0])):
    global routes
    path.append(path[0])
    @@ -25,7 +25,7 @@ def find_paths(node, cities, path, distance):
    if len(path) > 1:
    distance += cities[path[-2]][node]

    # Fork paths for all cities not yet used
    # Fork paths for all possible cities not yet used
    for city in cities:
    if (city not in path) and (cities[city].has_key(node)):
    find_paths(city, dict(cities), list(path), distance)
  4. @westphahl westphahl revised this gist Jun 14, 2010. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions optimal_tsp.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,7 @@
    """
    Author: Simon Westphahl <[email protected]>
    Description: Brute-force implementation for solving the
    travelling salesman problem.
    Description: Brute-force implementation for solving the TSP.
    http://en.wikipedia.org/wiki/Travelling_salesman_problem
    """

    routes = []
  5. @westphahl westphahl renamed this gist Jun 14, 2010. 1 changed file with 0 additions and 0 deletions.
    0 optimap_tsp.py → optimal_tsp.py
    View file
    File renamed without changes.
  6. @westphahl westphahl revised this gist Jun 14, 2010. 1 changed file with 17 additions and 23 deletions.
    40 changes: 17 additions & 23 deletions optimap_tsp.py
    View file
    Original file line number Diff line number Diff line change
    @@ -13,7 +13,7 @@ def find_paths(node, cities, path, distance):

    # If path contains all cities, add path from
    # last to first city and return.
    if len(cities) == len(path):
    if (len(cities) == len(path)) and (cities[path[-1]].has_key(path[0])):
    global routes
    path.append(path[0])
    distance += cities[path[-2]][path[0]]
    @@ -27,36 +27,30 @@ def find_paths(node, cities, path, distance):

    # Fork paths for all cities not yet used
    for city in cities:
    if city not in path:
    if (city not in path) and (cities[city].has_key(node)):
    find_paths(city, dict(cities), list(path), distance)


    if __name__ == '__main__':
    cities = {
    'RV': {
    'UL': 36,
    'A': 125,
    'MM': 67
    },
    'UL': {
    'RV': 36,
    'A': 35,
    'MM': 50
    },
    'A': {
    'RV': 125,
    'UL': 35,
    'MM': 65
    },
    'MM': {
    'RV': 67,
    'UL': 50,
    'A': 65
    },
    'RV': {'S': 195, 'UL': 86, 'M': 178, 'BA': 180, 'Z': 91},
    'UL': {'RV': 86, 'S': 107, 'N': 171, 'M': 123},
    'M': {'RV': 178, 'UL': 123, 'N': 170},
    'S': {'RV': 195, 'UL': 107, 'N': 210, 'F': 210, 'MA': 135, 'KA': 64},
    'N': {'S': 210, 'UL': 171, 'M': 170, 'MA': 230, 'F': 230},
    'F': {'N': 230, 'S': 210, 'MA': 85},
    'MA': {'F': 85, 'N': 230, 'S': 135, 'KA': 67},
    'KA': {'MA': 67, 'S': 64, 'BA': 191},
    'BA': {'KA': 191, 'RV': 180, 'Z': 85, 'BE': 91},
    'BE': {'BA': 91, 'Z': 120},
    'Z': {'BA': 120, 'BE': 85, 'RV': 91}
    }

    print "Start: RAVENSBURG"
    find_paths('RV', cities, [], 0)
    print "\n"
    routes.sort()
    print "Shortest route: %s" % routes[0]
    if len(routes) != 0:
    print "Shortest route: %s" % routes[0]
    else:
    print "FAIL!"
  7. @westphahl westphahl created this gist Jun 10, 2010.
    62 changes: 62 additions & 0 deletions optimap_tsp.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,62 @@
    """
    Author: Simon Westphahl <[email protected]>
    Description: Brute-force implementation for solving the
    travelling salesman problem.
    """

    routes = []


    def find_paths(node, cities, path, distance):
    # Add way point
    path.append(node)

    # If path contains all cities, add path from
    # last to first city and return.
    if len(cities) == len(path):
    global routes
    path.append(path[0])
    distance += cities[path[-2]][path[0]]
    print path, distance
    routes.append([distance, path])
    return

    # Calculate path length from current to last node
    if len(path) > 1:
    distance += cities[path[-2]][node]

    # Fork paths for all cities not yet used
    for city in cities:
    if city not in path:
    find_paths(city, dict(cities), list(path), distance)


    if __name__ == '__main__':
    cities = {
    'RV': {
    'UL': 36,
    'A': 125,
    'MM': 67
    },
    'UL': {
    'RV': 36,
    'A': 35,
    'MM': 50
    },
    'A': {
    'RV': 125,
    'UL': 35,
    'MM': 65
    },
    'MM': {
    'RV': 67,
    'UL': 50,
    'A': 65
    },
    }

    print "Start: RAVENSBURG"
    find_paths('RV', cities, [], 0)
    print "\n"
    routes.sort()
    print "Shortest route: %s" % routes[0]