【引言】一個(gè)旅行商，想要從A城市出發(fā)隙疚，途徑BCDEFGH城市，最終返回A城市磕道。每個(gè)城市之間的距離可能都是不一樣的供屉，那么他該以一個(gè)什么樣的順序，每個(gè)城市都經(jīng)過一次的情況下使得他所走的路程最短呢溺蕉？

商旅問題是一個(gè)如果按照正經(jīng)的方法解決伶丐，算法的效率會(huì)隨著數(shù)據(jù)的增加爆炸的問題。

算法過程

試想旅行商如果在出發(fā)前看一遍所有的路線方案疯特，那么路線方案的數(shù)量會(huì)隨著途徑城市的增多而出現(xiàn)爆炸性增長(zhǎng)的情況：

路線隨著途徑城市的增多而增加.png

時(shí)間復(fù)雜度的圖像.png

2-opt算法

2-opt算法的核心在于隨機(jī)選擇一個(gè)區(qū)間段進(jìn)行優(yōu)化组题，這個(gè)優(yōu)化只是對(duì)于當(dāng)前一個(gè)狀態(tài)的優(yōu)化，并不是對(duì)全局的優(yōu)化吃衅。
算法的步驟：
首先確定算法的最大迭代次數(shù)MAX往踢，初始化一個(gè)計(jì)數(shù)器N用于記錄迭代次數(shù)

• 1、隨機(jī)一條初始化可選擇的路線徘层，途徑所有城市峻呕，比如: A => B => C => D => E => F => G = > H => A利职， 假設(shè)這一條就是最短的路徑。

• 2瘦癌、 隨機(jī)選擇兩個(gè)不同的途徑的城市猪贪，反轉(zhuǎn)這兩個(gè)城市在內(nèi)的中間的路線，比如隨機(jī)選擇（C讯私、F）
  那么此時(shí) 老路徑 被分割成了三段:
  （A => B） =>（ C => D => E => F ）=> （G = > H => A）
  翻轉(zhuǎn)后热押，得到的 新路徑 ：
  （A => B） =>（ F => E => D => C ）=> （G = > H => A）

• 3、如果新路徑（A => B => F => E => D => C => G = > H => A）的距離總長(zhǎng) 小于 老路徑（A => B => C => D => E => F => G = > H => A）距離總長(zhǎng)斤寇，那么最短的路徑變?yōu)樾侣窂酵把ⅲ?jì)數(shù)器N=0；如果新路徑距離總長(zhǎng) 大于 老路徑娘锁，那么老路徑還是當(dāng)前的最短路徑牙寞，計(jì)數(shù)器N+1。如果 N ≥ MAX 莫秆， 算法結(jié)束间雀，當(dāng)前的路徑就是最短路徑（局部最優(yōu)的最短路徑）。
  這個(gè)算法得到的路線是局部最優(yōu)的镊屎，也就是它會(huì)根據(jù)迭代次數(shù)的不一樣惹挟，可能呈現(xiàn)出不一樣結(jié)果，并不是絕對(duì)正確的結(jié)果缝驳，只是優(yōu)化后的相對(duì)正確连锯。如果要得到絕對(duì)正確的結(jié)果，就需要把所有的路線都列出來計(jì)算所有的距離党巾，這樣就會(huì)爆炸萎庭。

算法實(shí)現(xiàn)

運(yùn)氣好的話，就能用這個(gè)數(shù)據(jù)源能跑出來一顆心齿拂，送給媳婦兒：

#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

# 因?yàn)樽约涸斓妮斎霐?shù)據(jù)可能是最佳路徑驳规，所以先獲取一個(gè)隨機(jī)的路線（任選一個(gè)可行解）
def get_random_path(best_path):
    random.shuffle(best_path)
    path = np.append(best_path, best_path[0])
    return path

# 計(jì)算兩個(gè)點(diǎn)的距離
def calculate_distance(from_index, to_index):
    return np.sqrt(np.sum(np.power(cities[from_index] - cities[to_index], 2)))

# 計(jì)算整條路徑的距離
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

# 獲取隨機(jī)的起始點(diǎn)還有中間的反轉(zhuǎn)后的路徑
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

# 比較兩個(gè)路徑的長(zhǎng)短
def compare_paths(path_one, path_two):
    return calculate_path_distance(path_one) > calculate_path_distance(path_two)

# 不斷優(yōu)化，得到一個(gè)最終的最短的路徑
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