Created
June 19, 2016 05:21
-
-
Save matts1/c5146a74e425ea3d66cb4414dbc45d82 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# create a new city (the 0th city), and set distance to every other city to be 0 | |
from copy import deepcopy | |
# just a fancy way of saying that the best function is cached. ignore this if you don't understand | |
def memoize(fn): | |
CACHE = {} | |
def newfn(*args): | |
if tuple(args) not in CACHE: | |
CACHE[tuple(args)] = fn(*args) | |
return CACHE[tuple(args)] | |
return newfn | |
# returns (best distance, set of nodes traversed by first, set of nodes traversed by second) | |
@memoize | |
def best(first, second): | |
if first == 0 and second == 1: return (0, set(), set([1])) | |
low = (float('inf'), set(), set()) | |
check = [(i, second) for i in range(first)] | |
if first != second - 1: | |
check.append(first, second - 1) | |
for oldfirst, oldsecond in check: | |
if oldfirst < oldsecond: dist, firstset, secondset = best(oldfirst, oldsecond) | |
else: dist, secondset, firstset = best(oldsecond, oldfirst) | |
if oldfirst != first: dist += distances[oldfirst][first] | |
if oldsecond != second: dist += distances[oldsecond][second] | |
if dist < low[0]: | |
low = (dist, deepcopy(firstset), deepcopy(secondset)) | |
return low | |
print(min([best(i, n) for i in range(n)])[0]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment