0

我将创建几个算法来解决旅行商问题，但首先我要创建一个包含 n 个节点的图形/地图，每个节点都有一个边框。（如果 n=100 那么它是 99 个边界）。每个节点之间的距离应该是从 1 到 5 的随机数。

（我在python中这样做）我的第一个想法是每个节点都有一个列表（最终地图将是列表中的列表）与其他节点的距离。如果有 10 个节点，那么每个列表中将有 9 个整数。

生成第一个列表后，其他列表将继承相应的距离。前任。 

A: [5, 5, 3]
B: [5]
C: [5]
D: [3]

下一步是生成一个少一个元素的新列表，将其放在已经存在的值后面并执行与上面相同的操作（其余节点将继承相应的距离）。这将递归完成，直到所有列表都已满。

最终列表看起来像这样： 

[[5, 5, 3],
 [5, 2, 1],
 [5, 2, 4],
 [3, 1, 4]

有人可以给我一个提示，我应该如何实施这个？或者，如果有更简单的方法。谢谢！

随机导入

def main():
    graph_map = []
    max_nodes = 10
    i = 0
    generate_map(graph_map, max_nodes, i)
    print graph_map

def generate_map(graph_map, max, i):
    temp_list = []
    for j in range(max-1):
        temp_list.append(random.randint(1, 5))
    if i > 0:
        graph_map[i].append(temp_list)
    else:
        graph_map.append(temp_list)

    for j in range(1, max):
        graph_map.append([temp_list[j-1]])





if __name__ == '__main__':
    main()

这段代码将为我提供我想要的示例输出开始：

[[4, 5, 5, 2, 1, 3, 3, 3, 2], [4], [5], [5], [2], [1], [3], [3], [3], [2]]
4

1 回答 1

2

我觉得你想多了。简单地做两个循环，首先填充与当前节点的距离，内部循环将它们复制到目标节点

import random

def main():
    graph_map = []
    max_nodes = 5
    for i in range(max_nodes):
        graph_map.append([])
    for i in range(max_nodes):
        for j in range(max_nodes-1-i):
            d = random.randint(1,5)
            graph_map[i].append(d) 
            graph_map[i+j+1].append(d)    

    print graph_map

if __name__ == '__main__':
    main()

印刷

[[5, 2, 1, 5], 
 [5, 1, 2, 3], 
 [2, 1, 4, 5], 
 [1, 2, 4, 5], 
 [5, 3, 5, 5]]

这种方法至少有几个问题：

  1. n x n您的数据表示很奇怪，以后的算法实现实际存储距离矩阵会容易得多，其中D[i,j]的意思是“从第 i 个城市到第 j 个城市的距离”，它只是D[i,i]=0. 您的表示方式类似于“从第 i 个城市到第 j 个城市的距离，如果j<i和第j-1'th 否则
  2. 这（在大多数情况下）不会生成平面图，这意味着您不能将n点放置在平面上，它们之间的距离如此之大。所以数据是相当“不切实际的”，许多启发式 TSP 解决方案都假设平面数据（或三角不等式）。更好的方法是n在平面上生成随机点，然后计算它们的距离。

[0,m]^2 上的平面生成器示例：

import math
import random 
n=5
m=100
def dist(a,b):
    return math.sqrt( (a[0]-b[0])**2 + (a[1]-b[1])**2 )
points = [ [random.randint(0,m), random.randint(0,m) ] for i in range(n) ]
D = [ [ dist( points[i], points[j] ) for i in range(n) ] for j in range(n) ]
print points
print D
于 2013-09-06T07:33:13.963 回答