题目描述： 给定n个点的坐标(x,y,z),且n<=50,从点1出发,怎么样才能走一条路径,访问每个点一次且仅一次,使走过的距离和最小? 现在给你一个list列表L，列表中每个元素是个三元组[x,y,z]（x,y,z都是整数）,表示坐标系上的一个点，列表长度不超过50. 请你输出从第一个点（即L[0])出发，走完L中每个点的最小距离（保留小数点后1位小数）。 例如： L = [[0,0,0], [1,1,0], [1,-1,0]] 则输出：3.4
示例： 输入： L = [[1, 7, 6], [2, 6, 4], [4, 9, 5], [11, 11, 11], [8, 4, 6]] 输出： 21.8
分析:
引用 QxyLearnCode 的话，“所谓勇气，就是再暴力的算法也敢上”。
直接上 深度优先。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import math
len_l = len(L)
# 求空间两点之间的距离
def distance(node_1, node_2):
d = 0
for i in range(3):
d += (node_1[i] - node_2[i]) * (node_1[i] - node_2[i])
return math.sqrt(d)
flag_lst = [0 for _ in range(len_l)]
min_value = 999999999
# dfs 深度优先，直接干
def dfs(pos, value, step):
global min_value
if step >= len_l:
# print(flag_lst, min_value)
min_value = min(min_value, value)
return
if value > min_value:
return
for i in range(len_l):
if not flag_lst[i] and pos != i:
flag_lst[i] = 1
dfs(i, value+distance(L[pos], L[i]), step+1)
flag_lst[i] = 0
flag_lst[0] = 1
dfs(0, 0, 1)
print("{:.1f}".format(min_value))