写给媳妇儿的算法（二）——2-opt算法解决商旅问题
【引言】一个旅行商，想要从A城市出发，途径BCDEFGH城市，最终返回A城市。每个城市之间的距离可能都是不一样的，那么他该以一个什么样的顺序，每个城市都经过一次的情况下使得他所走的路程最短呢？
商旅问题是一个如果按照正经的方法解决，算法的效率会随着数据的增加爆炸的问题。
算法过程
试想旅行商如果在出发前看一遍所有的路线方案，那么路线方案的数量会随着途径城市的增多而出现爆炸性增长的情况：
路线随着途径城市的增多而增加.png
这种情况下，算法的复杂度会是O(n!), O(n!)是个什么概念呢？：
时间复杂度的图像.png
所以，如果在出发前查看所有的路线方案，如果途径城市很多，会是个非常爆炸的计算数量。
2-opt算法
2-opt算法的核心在于随机选择一个区间段进行优化，这个优化只是对于当前一个状态的优化，并不是对全局的优化。
算法的步骤：
首先确定算法的最大迭代次数MAX，初始化一个计数器N用于记录迭代次数
-
1、随机一条初始化可选择的路线，途径所有城市，比如: A => B => C => D => E => F => G = > H => A， 假设这一条就是最短的路径。
-
2、 随机选择两个不同的途径的城市，反转这两个城市在内的中间的路线，比如随机选择（C、F）
那么此时 老路径 被分割成了三段:
（A => B） =>（ C => D => E => F ）=> （G = > H => A）
翻转后，得到的 新路径 ：
（A => B） =>（ F => E => D => C ）=> （G = > H => A） -
3、如果新路径（A => B => F => E => D => C => G = > H => A）的距离总长 小于 老路径（A => B => C => D => E => F => G = > H => A）距离总长，那么最短的路径变为新路径，计数器N=0；如果新路径距离总长 大于 老路径，那么老路径还是当前的最短路径，计数器N+1。如果 N ≥ MAX ， 算法结束，当前的路径就是最短路径（局部最优的最短路径）。
这个算法得到的路线是局部最优的，也就是它会根据迭代次数的不一样，可能呈现出不一样结果，并不是绝对正确的结果，只是优化后的相对正确。如果要得到绝对正确的结果，就需要把所有的路线都列出来计算所有的距离，这样就会爆炸。
算法实现
运气好的话，就能用这个数据源能跑出来一颗心，送给媳妇儿：
#coding: utf-8
import numpy as np
import matplotlib.pyplot as plt
import numpy.random as random
# 600*600的
cities = np.array([[300,0],
[400, 50],
[450, 100],
[500, 200],
[550, 300],
[600, 400],
[500, 500],
[400, 500],
[300, 400],
[200, 500],
[100, 500],
[0, 400],
[50, 300],
[100, 200],
[150, 100],
[200, 50]])
# 2-opt算法 #
COUNT_MAX = 520
# 因为自己造的输入数据可能是最佳路径，所以先获取一个随机的路线（任选一个可行解）
def get_random_path(best_path):
random.shuffle(best_path)
path = np.append(best_path, best_path[0])
return path
# 计算两个点的距离
def calculate_distance(from_index, to_index):
return np.sqrt(np.sum(np.power(cities[from_index] - cities[to_index], 2)))
# 计算整条路径的距离
def calculate_path_distance(path):
sum = 0.0
for i in range(1, len(path)):
sum += calculate_distance(path[i-1], path[i])
return sum
# 获取随机的起始点还有中间的反转后的路径
def get_reverse_path(path):
start = random.randint(1, len(path) - 1)
while True:
end = random.randint(1, len(path) - 1)
if np.abs(start - end) > 1:
break
if start > end:
path[end: start+1] = path[end: start+1][::-1]
return path
else:
path[start: end+1] = path[start: end+1][::-1]
return path
# 比较两个路径的长短
def compare_paths(path_one, path_two):
return calculate_path_distance(path_one) > calculate_path_distance(path_two)
# 不断优化，得到一个最终的最短的路径
def update_path(path):
count = 0
while count < COUNT_MAX:
reverse_path = get_reverse_path(path.copy())
if compare_paths(path, reverse_path):
count = 0
path = reverse_path
else:
count += 1
return path
def opt_2():
best_path = np.arange(len(cities))
best_path = get_random_path(best_path)
path = update_path(best_path)
show(path)
def show(path):
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
ax.plot(cities[:, 0], cities[:, 1], 'o', color='red')
ax.plot(cities[path, 0], cities[path, 1], color='red')
plt.show()
opt_2()
送给媳妇儿.png
上一篇：写给媳妇儿的算法（一）——二分查找
下一篇：写给媳妇儿的算法（三）——选择排序
