智能优化算法解决TSP旅行商问题--小总结

from itertools import combinations,permutations # 导入模块

all_number = list(range(1,11))
all_p = list(permutations(all_number,len(all_number))) # 输出排列

print(len(all_p)) 统计排列数量

# 10个城市的地址数据
cities = [
    (2066,2333),
    (935,1304),
    (1270,200),
    (1389,700),
    (984,2810),
    (2253,478),
    (949,3025),
    (87,2483),
    (3094,1883),
    (2706,3130),
]
'''================找出最小距离的函数======================'''
def find_the_path(point,list):
    path = []
    for i in range(len(list)):
        D = eucliDist(point,list[i])
        path.append(D)
    return path
'''================计算欧式距离==========================='''
def eucliDist(A,B):
    return math.sqrt((A[0] - B[0])**2 + (A[1]-B[1])**2)
'''=================输出路线============================='''
def draw_path(x_path,y_path):
    plo.plot(x_path,y_path,color = 'red') # 这里还需要把点凸显出来就可以了
    plo.xlabel('x')
    plo.ylabel('y')
    plo.title('TSP')
    plo.show() # 实现图片
'''=================找出最短的距离========================'''
frist_i = random.randint(0,199) # 任意取一个点
print(frist_i)
frist_point = cities[frist_i] # 找出这个位置上的坐标值
del cities[frist_i] # 将这个坐标从原来的列表中删除

generation = 0   # 迭代数统计

x_output = [] # 最终输出x的坐标列表，每计算出来一个点的坐标，其对应的x坐标都添加到这个列表中
y_output = [] # 最终输出y的坐标列表，同上
x_output.append(frist_point[0]) # 将出发点的x坐标添加进去
y_output.append(frist_point[1]) # 将出发点的y坐标添加进去

k = len(cities) # 城市的数量
sum_path = 0 # 最终的最短距离之和
'''
贪心算法的核心部分：每一步都是当时的最优解，全局来看可能是局部的最优解。
'''
while(generation < k):
    path = find_the_path(frist_point, cities) # 计算距离初始出发点的所有距离
    best_point_way = min(path) # 从所有的距离中，找出最小距离
    sum_path += best_point_way # 每一次迭代计算中，最小的距离相加
    points = cities[path.index(best_point_way)] # 距离出发点的距离最短的那个点

    x_output.append(points[0]) # 将本次计算出的点坐标添加到最终的路线中
    y_output.append(points[1]) # 同上

    frist_point = points # 将points的值转移到frist_point上，为下一次迭代计算做准备
    del cities[path.index(best_point_way)] # 将这个点从原来的列表中删除，这样cities中的值就会越来越少

    generation += 1 # 最后迭代数增加一次

x_output.append(x_output[0]) # 在循环结束之后，将出发点坐标添加到最后，形成闭环回路
y_output.append(y_output[0]) # 同上
print(x_output)
print(y_output)
frist_point = (x_output[0],y_output[0])

final_path = eucliDist(points,frist_point) # 计算最后一个点到初始出发点的距离
sum_path += final_path # 最后的总距离一定要加上最后这段距离，才能形成闭环
print(sum_path) # 输出最终的，最短距离之和

draw_path(x_output,y_output) # 画出所有的TSP轨迹路线

'''================找出最小距离的函数======================'''
def find_the_path(point,list):
    path = []
    for i in range(len(list)):
        D = eucliDist(point,list[i])
        path.append(D)
    return path
'''================计算欧式距离==========================='''
def eucliDist(A,B):
    return math.sqrt((A[0] -B[0])**2 + (A[1]-B[1])**2)
'''=================输出路线============================='''
def draw_path(x_path,y_path):
    plo.plot(x_path,y_path,color = 'red') # 这里还需要把点凸显出来就可以了
    plo.xlabel('x')
    plo.ylabel('y')
    plo.title('TSP')
    plo.show() # 现实图片
'''=================找出最短的距离========================'''
Optimization_solution = [] # 定义一个优化解的集合
num_cities = len(cities) # 计算城市数据集的大小 ，就是统计城市的数量
for i in range(0,num_cities): # 遍历完从0到n的数
    this_turn = cities # 将列表cities的值全都复制给this_turn，这样后面的操作都不会影响cities
    frist_point = this_turn[i] # 意义：将每一个点都作为初始出发点

    del this_turn[i] # 将这个坐标从原来的列表中删除

    generation = 0   # 迭代数统计

    x_output = [] # 最终输出x的坐标列表，每计算出来一个点的坐标，其对应的x坐标都添加到这个列表中
    y_output = [] # 最终输出y的坐标列表，同上
    x_output.append(frist_point[0]) # 将出发点的x坐标添加进去
    y_output.append(frist_point[1]) # 将出发点的y坐标添加进去

    k = len(this_turn) # 城市的数量
    sum_path = 0 # 最终的最短距离之和
    '''
    贪心算法的核心部分：每一步都是当时的最优解，全局来看可能是局部的最优解。
    '''
    while(generation < k):
        path = find_the_path(frist_point, this_turn) # 计算距离初始出发点的所有距离
        best_point_way = min(path) # 从所有的距离中，找出最小距离
        sum_path += best_point_way # 每一次迭代计算中，最小的距离相加
        points = this_turn[path.index(best_point_way)] # 距离出发点的距离最短的那个点

        x_output.append(points[0]) # 将本次计算出的点坐标添加到最终的路线中
        y_output.append(points[1]) # 同上

        frist_point = points # 将points的值转移到frist_point上，为下一次迭代计算做准备
        del this_turn[path.index(best_point_way)] # 将这个点从原来的列表中删除，这样cities中的值就会越来越少

        generation += 1 # 最后迭代数增加一次

    x_output.append(x_output[0]) # 在循环结束之后，将出发点坐标添加到最后，形成闭环回路
    y_output.append(y_output[0]) # 同上

    frist_point = (x_output[0],y_output[0])  # 把初始出发点找出来

    final_path = eucliDist(points,frist_point) # 计算最后一个点到初始出发点的距离
    sum_path += final_path # 最后的总距离一定要加上最后这段距离，才能形成闭环
    # print(sum_path) # 输出最终的，最短距离之和
    Optimization_solution.append(sum_path)

The_optimal_solution = min(Optimization_solution) # 找出最短距离之和
print(The_optimal_solution) # 输出最短距离