All Tours Algorithm

# -*- coding:utf-8 -*-

import matplotlib.pyplot as plt
import random
import time
import itertools
import urllib
import csv

__author__ = ‘Kalpan‘

"""
　　All Tours Algorithm:生成所有的路径，选择最短的那条
"""
#alltours = itertools.permutations

def alltours_tsp(cities):
    """
    生成所有可能的路线，返回最短路线集
    :param cities:城市的集合
    :return:
    """
    return shortest_tour(alltours(cities))

def shortest_tour(tours):
    """
    选择最短的路线集
    :param tours:路线集
    :return:
    """
    return min(tours, key=tour_length)

def tour_length(tour):
    """
    计算路线tour的长度
    :param tour:
    :return:
    """
    return sum(distance(tour[i], tour[i-1]) for i in range(len(tour)))

# 将city当做点来代替，并以复数的形式表示
Point = complex
City = Point

def X(point):
    """
    点的横坐标
    :param city:
    :return:
    """
    return point.real

def Y(point):
    """
    返回点的纵坐标
    :param point:
    :return:
    """
    return point.imag

def distance(A, B):
    """
    计算A,B两点之间的距离
    :param A:
    :param B:
    :return:
    """
    return abs(A-B)


def cities(n, width=900, height=600, seed=42):
    """
    随机生成城市数据集
    :param num:
    :return:
    """
    random.seed(seed * n) # 故意设置固定的seed，为了确保得到的cities集合是固定的
    return frozenset(City(random.randrange(width), random.randrange(height))
                     for c in range(n))

# 画出路线图
def plot_tour(tour):

    plot_lines(list(tour) + [tour[0]])      # +[tour[0]], 回到最初的起点

def plot_lines(points, style=‘bo-‘):
    """
    画出一系列点的连线
    :param points:
    :param style:
    :return:
    """
    plt.plot(list(map(X, points)), list(map(Y, points))     # 3.0的坑，map()不在直接返回list， 需要list调用
             , style)
    plt.axis(‘scaled‘)
    plt.axis(‘off‘)

def plot_tsp(algorithm, cities):
    """
    选择一种算法，并画出该算法最短路径
    :param algorithm: 
    :param cities:
    :return:
    """
    # 计算算法执行的时间
    t0 = time.clock()
    tour = algorithm(cities)
    t1 = time.clock()
    assert valid_tour(tour, cities)
    plot_tour(tour)
    plt.show()
    print("{} city tour with length {:.1f} in {:.3f} secs for {}"
          .format(len(tour), tour_length(tour), t1-t0, algorithm.__name__))

def valid_tour(tour, cities):
    """
    检查该路径是否为有效路径，
    :param tour:
    :param cities:
    :return:
    """
    return set(tour) == set(cities) and len(tour) == len(cities)        # 经过每个城市，且每个城市只经过一次


"""
    在进行路径选择的过程中， 我们选择的是全排列，相对于{1， 2， 3} 三座城市，就有六种可能
    → [(1，2，3)，(1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
    这里出现了重复，至少在计算最短路径时，(1, 2, 3), (2, 3, 1) 和 (3, 1, 2)所得的结果显然相同，它们按着相同的序列排列
    针对该算法的改进：
    我们只计算以某个城市开始，让其他的城市全排列，确定所得到的序列中没有重复
    改进前，10 city tour with length 2291.8 in 45.799 secs for alltours_tsp
    改进后，10 city tour with length 2291.8 in 5.172 secs for alltours_tsp
"""

def alltours(cities):
    """
    返回一个路径的链表，每一个元素是组城市的排列，而且都以同一个城市开始
    :param cities:
    :return:
    """
    start = first(cities)
    return [[start] + Tour(rest)
            for rest in itertools.permutations(cities - {start})]

def first(collection):
    return next(iter(collection))

Tour = list