精华内容
下载资源
问答
  • 用Python解决TSP问题(1)——贪心算法

    万次阅读 多人点赞 2018-06-25 20:27:28
    关于TSP问题网上有很多介绍,这里再简单描述一下。旅行商问题(TravelingSalesmanProblem,TSP)一个商品推销员要去若干个城市推销商品,该推销员从一...也有智能算法,比如:蚁群算法、遗传算法、A*等。由于网上使用...

    文章源码在Github:https://github.com/jinchenghao/TSP

    关于TSP问题网上有很多介绍,这里再简单描述一下。旅行商问题(TravelingSalesmanProblem,TSP)一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要遍历所有城市一次且只能一次,回到出发地。应如何选择行进路线,以使总的行程最短。目前解决TSP问题的方法有许多种,比如:贪心算法、动态规划算法、分支限界法;也有智能算法,比如:蚁群算法、遗传算法、A*等。由于网上使用python解决这类问题的比较少,所以我会用python实现这些算法。本文先介绍贪心算法:

    数据格式

    数据格式如下:

    城市XY
    City1100200
    City2150200
    City3345313
    ...  

    即输入的数据有3列,第一列是城市编号,第二列和第三列是城市坐标(x,y)。

    算法简介

    贪心算法非常容易理解,是一种解决实际问题中的常用方法,经常用来和其他算法进行比较。所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

    在TSP问题上,假设城市集合为B,我们每次只选择距离当前城市最近的城市移动。同时集合s记录已经遍历过得城市,下次从集合(B-s)中选择。

    程序

    输入:

    1 2066 2333
    2 935 1304
    3 1270 200
    4 1389 700
    5 984 2810
    6 2253 478
    7 949 3025
    8 87 2483
    9 3094 1883
    10 2706 3130
    

    代码如下:

    #贪心法
    import pandas as pd
    import numpy as np
    import math
    import time
    
    dataframe = pd.read_csv("./data/TSP100cities.tsp",sep=" ",header=None)
    v = dataframe.iloc[:,1:3]
    
    train_v= np.array(v)
    train_d=train_v
    dist = np.zeros((train_v.shape[0],train_d.shape[0]))
    
    #计算距离矩阵
    for i in range(train_v.shape[0]):
        for j in range(train_d.shape[0]):
            dist[i,j] = math.sqrt(np.sum((train_v[i,:]-train_d[j,:])**2))
    """
    s:已经遍历过的城市
    dist:城市间距离矩阵
    sumpath:目前的最小路径总长度
    Dtemp:当前最小距离
    flag:访问标记
    """
    i=1
    n=train_v.shape[0]
    j=0
    sumpath=0
    s=[]
    s.append(0)
    start = time.clock()
    while True:
        k=1
        Detemp=10000000
        while True:
            l=0
            flag=0
            if k in s:
                flag = 1
            if (flag==0) and (dist[k][s[i-1]] < Detemp):
                j = k;
                Detemp=dist[k][s[i - 1]];
            k+=1
            if k>=n:
                break;
        s.append(j)
        i+=1;
        sumpath+=Detemp
        if i>=n:
            break;
    sumpath+=dist[0][j]
    end = time.clock()
    print("结果:")
    print(sumpath)
    for m in range(n):
        print("%s-> "%(s[m]),end='')
    print()
    print("程序的运行时间是:%s"%(end-start))
    

    结果:


    展开全文

空空如也

空空如也

1
收藏数 1
精华内容 0
关键字:

基于贪心算法的蚁群算法求tsppython

python 订阅