<p>因为你没有那么多的观点,你可以很容易地使用一种尝试各种可能性的解决方案。在</p>
<p>以下是您可以做的:</p>
<p>首先获取所有组合:</p>
<pre><code>>>> list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
>>> list(itertools.permutations(list_of_points))
[((1, 2), (2, 5), (6, 7), (9, 3)),
((1, 2), (2, 5), (9, 3), (6, 7)),
((1, 2), (6, 7), (2, 5), (9, 3)),
((1, 2), (6, 7), (9, 3), (2, 5)),
((1, 2), (9, 3), (2, 5), (6, 7)),
((1, 2), (9, 3), (6, 7), (2, 5)),
((2, 5), (1, 2), (6, 7), (9, 3)),
((2, 5), (1, 2), (9, 3), (6, 7)),
((2, 5), (6, 7), (1, 2), (9, 3)),
((2, 5), (6, 7), (9, 3), (1, 2)),
((2, 5), (9, 3), (1, 2), (6, 7)),
((2, 5), (9, 3), (6, 7), (1, 2)),
((6, 7), (1, 2), (2, 5), (9, 3)),
((6, 7), (1, 2), (9, 3), (2, 5)),
((6, 7), (2, 5), (1, 2), (9, 3)),
((6, 7), (2, 5), (9, 3), (1, 2)),
((6, 7), (9, 3), (1, 2), (2, 5)),
((6, 7), (9, 3), (2, 5), (1, 2)),
((9, 3), (1, 2), (2, 5), (6, 7)),
((9, 3), (1, 2), (6, 7), (2, 5)),
((9, 3), (2, 5), (1, 2), (6, 7)),
((9, 3), (2, 5), (6, 7), (1, 2)),
((9, 3), (6, 7), (1, 2), (2, 5)),
((9, 3), (6, 7), (2, 5), (1, 2))]
</code></pre>
<p>然后创建一个函数,给出组合的长度:</p>
^{pr2}$
<p>最后是一个测试所有可能性的函数:</p>
<pre><code>def get_shortest_path(start_point, list_of_point):
min = sys.maxint
combination_min = None
list_of_combinations = list(itertools.permutations(list_of_points))
for combination in list_of_combination:
length = combination_length(start_point, combination)
if length < min:
min = length
combination_min = combination
return combination_min
</code></pre>
<p>最后你可以:</p>
<pre><code>import sys, itertools
def combination_length(start_point, combination):
lenght = 0
previous = start_point
for elem in combination:
lenght += manhattanDistance(previous, elem)
return length
def get_shortest_path(start_point, list_of_point):
min = sys.maxint
combination_min = None
list_of_combinations = list(itertools.permutations(list_of_points))
for combination in list_of_combination:
length = combination_length(start_point, combination)
if length < min:
min = length
combination_min = combination
return combination_min
list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
print get_shortest_path((2,1), list_of_points)
</code></pre>