今天在写维特比算法计算带权路径图的最短路径时候，用到了list这个python中的变量类型。

这里是根据给定的逆邻接表用动态规划算法中的维特比算法来计算一个最短路径的list

在下面的代码片段中调用calc_min_weight_path_back方法可以求出给定的逆邻接表的最短路径数组

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
def get_total_weight(list_input, index):
    if(list_input[index][0] == 0 and list_input[index][1] == 1): return 0
    else:
        return list_input[index][0] + get_total_weight(list_input, list_input[index][1])
def calc_min_weight_path_back(master_list):
    '''
    逆邻接表求最短路径
    '''
    len_master_list = len(master_list)
    tmp_min_list = [[None, None]] * len_master_list # 初始化给定长度的数组保存最短路径
    
    # tmp_min_list = [[None] * 2 for row in range(len_master_list)] # 初始化给定长度的数组保存最短路径
    tmp_min_list[0] = [0, 1] # 初始化第一个节点默认代表 最小值、来源
    for index in range(1, len_master_list):
        for key, value in master_list[index].items():
            if(tmp_min_list[index][0] == None):
                tmp_min_list[index][0] = value
                tmp_min_list[index][1] = key
            else:
                tmp_sum1 = get_total_weight(tmp_min_list, index) # 原来的结果
                tmp_sum2 = get_total_weight(tmp_min_list, tmp_min_list[key][1]) + value # 待插入的结果
                if(tmp_sum2 < tmp_sum1): # 新插入的值更小
                    tmp_min_list[index][0] = value
                    tmp_min_list[index][1] = key
        print(index)
        print(tmp_min_list)
    
    return tmp_min_list

代码片段中的tmp_min_list变量，我需要预先初始化成为如下的一个二维数组

01234567
0NoneNoneNoneNoneNoneNoneNone
1NoneNoneNoneNoneNoneNoneNone

于是我使用了``这种方法

In[1]:[[None, None]] * 8
Out[1]:
[[None, None],
[None, None],
[None, None],
[None, None],
[None, None],
[None, None],
[None, None],
[None, None]]

乍一看上去没有问题。。然后我就放心的写入了函数

运行时候出现了RuntimeError: maximum recursion depth exceeded in comparison的问题

查询了一下发现是递归超出限度的深度。。结果我以为是递归哪里写错了。。然后一个劲儿的查找递归的问题

找到最后还是找不到。。于是使用最著名的debug大法：print

结果发现我循环到第二次输出的数据竟然是出了0号位置设置了其他值以外剩下的7位都一样。。

这下我才想起来很久很久之前好像听过这个问题。。但是一直觉得python是一种特别随意的语言。。所以就没有注意。。

好了回归正题。。

这次特意从网路上找来了一些资料。。总结在这里。。

免得我下次再次遇到这种问题时候又不知道该怎么办hhhhhh

对于元素值没有要求的初始化可以使用如下代码

1
list_result = list(range(x))

这样的输出结果会是

1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

如果初始化成为相同的内容可以使用*来解决，如：

1
2
3
list_result = [0]*10
list_result[0] = 1
list_result

其输出结果为

1
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

或者还可以使用内联的方式

1
2
3
list_result = [-1 for _ in range(10)]
list_result[0] = 1
list_result

输出结果为

1
[1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

对于一个二维数组

可以先用上述方法生成行，再对每一行进行生成，即

1
list_list_result = [[-1 for _ in range(10)] for _ in range(10)]

其输出结果为

1
2
3
4
5
6
7
8
9
10
[[1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]]

当然上面的这些内容也可以使用numpy去解决。。但是我暂时不想写了。。记录到这里就完了

参考链接

【Python递归报错：RuntimeError: maximum recursion depth exceeded in comparison】：https://www.cnblogs.com/zhanxueyou/p/3799410.html

【python初始化list列表（1维、2维）】：https://www.cnblogs.com/zqifa/p/python-list.html