Skip to content

Instantly share code, notes, and snippets.

@majk-p
majk-p / dynamic_tsp.py
Created November 17, 2015 16:14 — forked from mlalevic/dynamic_tsp.py
Simple Python implementation of dynamic programming algorithm for the Traveling salesman problem
def solve_tsp_dynamic(points):
#calc all lengths
all_distances = [[length(x,y) for y in points] for x in points]
#initial value - just distance from 0 to every other point + keep the track of edges
A = {(frozenset([0, idx+1]), idx+1): (dist, [0,idx+1]) for idx,dist in enumerate(all_distances[0][1:])}
cnt = len(points)
for m in range(2, cnt):
B = {}
for S in [frozenset(C) | {0} for C in itertools.combinations(range(1, cnt), m)]:
for j in S - {0}:
/*
* robotNav.js
*
* The green key is located in a slightly more
* complicated room. You'll need to get the robot
* past these obstacles.
*/
function startLevel(map) {
// Hint: you can press R or 5 to "rest" and not move the
/*
* robotMaze.js
*
* The blue key is inside a labyrinth, and extracting
* it will not be easy.
*
* It's a good thing that you're a AI expert, or
* we would have to leave empty-handed.
*/
/**************************
* exceptionalCrossing.js *
**************************
*
* Sorry, old friend, but I'm afraid I can't share
* co-authorship on this paper. You've done a very
* good job getting this Algorithm for me. The bit
* with the keys was especially clever! I wouldn't
* have thought of it myself. But then, of course,
* that's why you were here in the first place.