Posts pythonTip 105 勇气的挑战
Post
Cancel

pythonTip 105 勇气的挑战

题目描述: 给定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))
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 104 Python之殇

pythonTip 106 LTC-男人八题之一:连通图

Trending Tags