如何在Python中为TSP实现动态编程算法? [英] How to implement a dynamic programming algorithms to TSP in Python?
问题描述
我想使用Python中的动态编程算法解决TSP问题,问题是:
I want to solve the TSP problem using a dynamic programming algorithm in Python.The problem is:
- 输入:用a表示的城市点列表。例如,[(1,2,3,(0.3,4.5),(9,3)...]。城市之间的距离定义为欧几里得距离。
- 输出:在这种情况下,旅行推销员旅行的最低费用,四舍五入到最接近的整数。
伪代码为:
Let A = 2-D array, indexed by subsets of {1, 2, ,3, ..., n} that contains 1 and destinations j belongs to {1, 2, 3,...n}
1. Base case:
2. if S = {0}, then A[S, 1] = 0;
3. else, A[S, 1] = Infinity.
4.for m = 2, 3, ..., n: // m = subproblem size
5. for each subset of {1, 2,...,n} of size m that contains 1:
6. for each j belongs to S and j != 1:
7. A[S, j] = the least value of A[S-{j},k]+the distance of k and j for every k belongs to S that doesn't equal to j
8.Return the least value of A[{1,2..n},j]+the distance between j and 1 for every j = 2, 3,...n.
我的困惑是:
如何使用子集为列表建立索引,这就是如何有效地在伪代码中实现第5行。
How to index a list using subset, that is how to implement line 5 in the pseudo-code efficiently.
推荐答案
您可以将集合编码为整数:整数的第i个位将代表第i个城市的状态(即是否将其包含在子集中)。
例如35 10 = 100011 2 将代表城市{1、2、6}。在这里,我从代表城市1的最右边的位开始计数。
You can encode sets as integers: i'th bit of the integer will represent the state of i'th city (i.e. do we take it in the subset or not).
For example, 3510 = 1000112 will represent cities {1, 2, 6}. Here I count from the rightmost bit, which represents city 1.
为了使用子集的这种表示方法对列表进行索引,您应该创建长度为的2D数组> 2 n :
In order to index a list using such representation of a subset, you should create 2D array of length 2n:
# Assuming n is given.
A = [[0 for i in xrange(n)] for j in xrange(2 ** n)]
这是因为使用n位整数可以表示{1、2,...,n}的每个子集(请记住,每个位恰好对应一个城市)。
This comes from the fact that with n-bit integer you can represent every subset of {1, 2, ..., n} (remember, each bit corresponds to exactly one city).
这种表示形式为您提供了许多不错的可能性:
This representation gives you a number of nice possibilities:
# Check whether some city (1-indexed) is inside subset.
if (1 << (i - 1)) & x:
print 'city %d is inside subset!' % i
# In particular, checking for city #1 is super-easy:
if x & 1:
print 'city 1 is inside subset!'
# Iterate over subsets with increasing cardinality:
subsets = range(1, 2 ** n)
for subset in sorted(subsets, key=lambda x: bin(x).count('1')):
print subset,
# For n=4 prints "1 2 4 8 3 5 6 9 10 12 7 11 13 14 15"
# Obtain a subset y, which is the same as x,
# except city #j (1-indexed) is removed:
y = x ^ (1 << (j - 1)) # Note that city #j must be inside x.
这就是我实现伪代码的方式(警告:未进行测试):
This is how I would implement your pseudocode (warning: no testing was done):
# INFINITY and n are defined somewhere above.
A = [[INFINITY for i in xrange(n)] for j in xrange(2 ** n)]
# Base case (I guess it should read "if S = {1}, then A[S, 1] = 0",
because otherwise S = {0} is not a valid index to A, according to line #1)
A[1][1] = 0
# Iterate over all subsets:
subsets = range(1, 2 ** n)
for subset in sorted(subsets, key=lambda x: bin(x).count('1')):
if not subset & 1:
# City #1 is not presented.
continue
for j in xrange(2, n + 1):
if not (1 << (j - 1)) & subset:
# City #j is not presented.
continue
for k in xrange(1, n + 1):
if k == j or not (1 << (k - 1)) & subset:
continue
A[subset][j] = min(A[subset][j], A[subset ^ (1 << (j - 1))][k] + get_dist(j, k))
除了具有实现伪代码所需的所有功能之外,这种方法还将继续比使用tuplesdict更快。
Besides having all needed functionality to implement your pseudocode, this approach is going to be faster than with tuples\dicts.
这篇关于如何在Python中为TSP实现动态编程算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!