精华内容
下载资源
问答
  • 基于回溯法的TSP问题解决方案,附有TSP问题相关的c++和matlab解法资料,及工程文件(西电02105143)
  • 标准GA算法,及应用解决TSP问题的C#实现源码 为实际项目专案特别编写的,在BIN目录下CityChromoSome.txt的为测试用例文档
  • 一、TSP问题 1、TSP问题描述 简单来说,就是给定一些点,找出一条通过所有点的回路,使得回路最短 旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之...

    一、TSP问题

    1、TSP问题描述
    简单来说,就是给定一些点,找出一条通过所有点的回路,使得回路最短

    旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

    2、本文使用的TSP例子
    ……为简化问题,直接在x轴上找一百个整数点 ,纵轴为0,横轴为1……100
    显然最短路径是按照123456……100的顺序或者倒序走,再连接首位1和100,总路径为200
    但在实际问题中,点的分布是不十分不规则的,比如中国各省的省会城市,绕着走一圈,是不可能直接就能看出路径最短的走法的。
    ……遍历所有的走法再求出每一条路径长度进行比较是一种易于理解的方法,但所有走法总数目是 城市个数的全排列,如果有N个城市,就有N!种走法。对于中国三十多个省来说,这不是一个很大的数字,可以遍历出,但是如果N很大,比如遍历中国所有乡镇,这是一个天文数字,一般计算机是很难以计算出来的。
    ……于是,为了减少计算代价,就可以利用贪心法、爬山法、模拟退火法来求解,当然求得的解达到全局最优解是很难的,但可以在一定误差范围内得到较优的解,计算代价却小得多。他们都带有一定的随机性,达不到全局最优解的原因是他们陷入局部最优解的凹槽中无法解脱出来。

    二、简单介绍:贪心法、爬山法、模拟退火

    找到全局最优解就是找到全局最小解,全局最小的解肯定是在“凹槽”,一个函数可能有许许多多的“凹槽”,最小解是在找到最深的一个“凹槽”并取到它的底部的值。一般在未知的情况下,因为不知道最深“凹槽”是在哪里,只能随机选择一个点开始进行搜索,这三种方法都是随机选择一个点开始,按照“下山”方向进行搜索和更新
    在这里插入图片描述
    图中画的是一维,实际问题是二维以上的,以二维为例,二维寻找“凹槽”就和实际中下山的过程是一样的了,以下按照“下山”进行算法比喻的解释
    1、贪心算法:
    ……在山坡上某一点时,随机确定一个方向,不管山坡的陡峭程度,如果这个方向是下山的方向,就要往这个方向走一步;如果这个方向是上山,就不走动,再随机确定一个方向。比如,一个人下山时,他身前180度角度内都是下山方向,身后180度角度内都是上山方向,在每一次确定方向时,只要方向是身前的180度之内,就往下走,如果方向是身后的180度之内,就不走。
    ……这种方法取名为贪心法,是因为它只着眼于眼前,目光短浅地对选取到的下山方向很贪心
    在这里插入图片描述

    2、爬山算法
    ……爬山法是贪心算法的一种升级,他每走一步之前,随机确定很多方向,如果是身前180度角度的方向都保留,身后180度的方向都舍弃,再从保留下来的方向中找一个最好的;也就是说,他的每一步不仅是下山的,而且是当前下山最快的方向。爬山法相对于贪心法来说,没有这么贪心于眼前找到的第一个下山方向,而是花一些时间找很多方向,再在这些方向中找一个最优的,然后才往下走一步
    在这里插入图片描述
    3、模拟退火算法
    ……首先,先说明一下,贪心算法和爬山算法都只能找到附近的局部最优解;显然,当它找到第一个山谷时,身前180度和身后180度都是上山的方向了,所以它不在变动。如果刚好,这个山谷是全部山谷中最深的一个,那么恭喜,找到了全部最优解了,当然,这种情况的概率不高,因为实际中的函数里面山谷非常多,随机初始点在最深山谷的附近是不容易的。
    ……模拟退火算法就是为了弥补以上两种方法只能找到局部最优解的缺点而发明的。因为前两种方法,每一步总是向着附近的山谷方向移动的,这就决定它们只能找到附近的山谷;模拟退火方法摒弃了这种“只向某一山谷方向移动的原则”,适当地向上山方向移动,这样它就有机会去见到更多的山谷,而找到更好的一个解。
    ……模拟退火取名如此,是因为它类于比物理学中的晶体熔化和降温。想要获取某种晶体的最佳状态,需要先熔化晶体再进行降温,在降温过程中不是一直保持降温状态,而是适当的给晶体深温。降温就好比下山,升温就好比上山。

    4、路径变更、判断下山方向以及什么时候可以适当上山
    1)路径变更
    ……路径也就是点的排列,装在一个数组中,排列顺序就是路径顺序(注意,最后一个要记得和第一个相连构成回路)。每一个数组排列代表一个路径,每次随机做一个小改动,就是将数组排列中的任意两个点交换位置,位置交换后就得到一个新的数组排列,也就是一个新的路径(当然也有其他路径变更的方法,只要变换数组的排列顺序即可,比如找到任意一个点,这个点前面的和后面的交换一下)
    2)判断是否为下山方向
    ……变更前的路径为path_old,变更后的为path_new,求两次路径的长度len_old和len_new,若det=len_new-len_old,如果det<0,即为下山方向;此时对于贪心算法,会更新path_old为path_new作为下一次搜索起点
    3)模拟退火法的适当上山原则
    ……给定温度T,这个T是为了模拟退火方法额外添加的,与寻找最优值没有直接关系;T会随着时间t不断衰退(有很多种已经给定好的衰退方法),当T小于某个给定的值时,退火完毕。
    ……T每衰退一次,进行一次优化搜索,此时T的作用就是为优化搜索提供一个参数;优化搜索是一个循环过程:

    (1)对T时刻的路径path_old,随机交换数组排列的两个位置得到一个新路径path_new,计算det=path_new-path_old
    给一个概率p定义如下:path_old会有p的概率转变未path_new
    (2)如果det<0,更新path_old为path_new作为下一次搜索起点,即p=1
    (3)如果det>=0,计算p,p和det有关:
    …………………………………p=exp(-det/T)
    (其中(2)(3)称为 Metropolis准则,由退火过程而得,在退火过程det是能量差,在这里是路径长的差)
    在这里插入图片描述

    (4)对于det>0,可以看出,det越小,p越大,path_old转变的几率越大;det越大,p越小,path_old转变几率越小。p的直观意义就是,现在找到一个方向是上山的,要不要往这个方向走,往这个方向走的可能性是p
    (5)计算得到p后,如何发挥p的作用? 再随机产生一个(0-1)的随机数p_test,p_test小于p的几率就是p;所以,当p_test<p时,就将path_old变为path_new,尽管现在是上山方向

    ……在每一个T下,循环次数达到指定次数后跳出循环,最后的path保存下来(作为下一次循环的起点),T根据给定的方式下降成新的T,再进行循环……一直这样反复操作到T小于某个给定的值T_end
    ……如何选定初始T和T_end?可以根据一些启发经验来给定或者自己调比较,一般来说,初始T越高,运行时间越久,得到更优解的机会更高
    在这里插入图片描述

    三、python代码实现

    1、初始路径:
    由于我这里为了好理解,只取了x轴1-100这100个点,其最短路径就是按1到100顺序或者倒序走,再连接100和1,总共200
    假装我们是不知道最优路径的,只能迷茫地随机选择某个路径作为初始路径,我利用random.shuffle()函数随机打乱了1-100的排列,得到如下路径作为初始路径

    # coding:utf-8
    import random
    import numpy as np
    import time
    
    path0= [47,  70,  68,  11,  36,  74,  81,  71,  86,  76,  34,  77,  80,
            85,  19,  49,  84,   2,  98,  20,  67,  13,  58,  33,  99,  44,
            66,  35,  30,   3,  56,  18,   1,  93,   9,  32,  12,  40,  90,
            51,  23, 100,  53,  59,  73,  22,  65,  97,  52,  64,  92,  72,
            17,  14,  31,  69,  50,   4,  78,  89,  57,  55,  45,  82,  10,
            28,  96,  91,  87,  42,   7,  83,  46,  61,   5,  29,  39,  21,
            88,  79,  26,  62,  27,  25,   8,  48,  94,  54,  24,  63,  43,
            75,  41,  15,  16,  95,  38,  60,  37,   6]
    

    2、计算路径长
    两个相邻点的路径长就是前后两个数的差的绝对值,总路径长就是将这些绝对值求和:

    def path_len(path):
        path_dis = 0
        for i in range(len(path) - 1):
            two_dis = abs(path[i + 1] - path[i])  # 两点距离
            path_dis += two_dis
    
        path_dis += abs(path[-1] - path[0]) # 再加上首尾距离
        return path_dis
    

    3、路径变换

    def change_path(path, i, j):
        path_new=[]
        for t in path:
            path_new.append(t)
    
        c = path_new[i]
        path_new[i] = path_new[j]
        path_new[j] = c
        return path_new
    

    4、贪心法选择路径

    def tanxin(path):
        n = len(path)
        get_new_path = path
        old_len = path_len(path)
        count = 0
        while count < n*n:
            i = random.randint(0, n - 1)
            j = random.randint(0, n - 1)
            path_new = change_path(path, i, j)
            count += 1
            if path_len(path_new) < old_len:
                get_new_path = path_new
                break
    
        if get_new_path == path:
            print('没有找到附近更优解,返回原解')
            return path
        else:
            print('找到该path更优附近解,返回更优附近解:',get_new_path)
            return get_new_path
    

    5、爬山法选择路径

    def pashan(path):
        n = len(path)
        get_new_path = path
        old_len = path_len(path)
        count = 0
        while count < n*n:
            i = random.randint(0, n - 1)
            j = random.randint(0, n - 1)
            path_new = change_path(path, i, j)
            count += 1
            if path_len(path_new) < old_len:
                old_len=path_len(path_new)
                get_new_path=path_new
    
        if get_new_path == path:
            print('没有找到附近更优解,返回原解')
            return path
        else:
            print('找到该path更优附近解,返回更优附近解:',get_new_path)
            return get_new_path
    

    6、寻找最优解,当找不到下山方向(路径没有变化时)得到该种方法最优解

    def best_path(path):
        nums=0
        while 1:
            path_better=tanxin(path)   
            #这里是用贪心法,改为pashan(path)则为爬山法
            nums+=1
            print(nums)
            if path_better == path:
                dis=path_len(path_better)
                print('----'*50)
                print( '共迭代',nums,'次,搜索到这种方法的最优解')
                print('最优路径:',path_better)
                print('最优距离:',dis)
                break
            else:
                path=path_better
    
    

    7、模拟退火法(另开一个新程序)

    # coding:utf-8
    import math
    import random
    
    
    # 温度变化函数
    def T_update(t,T0):  # t 为推移时间,即每需要更新一次,t+1,表示冷却一次
        T=T0/math.log(1+t)
        return T
    
    # 计算路径长函数
    def path_len(path):
        path_dis = 0
        for i in range(len(path) - 1):
            two_dis = abs(path[i + 1] - path[i])  # 两点距离
            path_dis += two_dis
    
        path_dis += abs(path[-1] - path[0])
        return path_dis
    
    # 得到新路径函数
    def change_path(path, i, j):
        path_new=[]
        for t in path:
            path_new.append(t)
    
        c = path_new[i]
        path_new[i] = path_new[j]
        path_new[j] = c
        return path_new
    
    # metropolis 准则
    def metropolis(path_old,path_new,T):
        len_new=path_len(path_new)
        len_old=path_len(path_old)
        detE=len_new-len_old
        if detE<=0:
            p=1
        else:
            p=math.pow(math.e,-detE/T)
        return p
    
    # 退火法函数
    def disfire(path,T=20000,T_end=0.0001,iteration=10000):
        # 参数: 初始路径,初始温度,结束温度,每个温度下的迭代次数
        n=len(path)
        t=0
        while T>=T_end:
            t +=1
            count=0  # 计数
            while count < iteration:
                count += 1
                i=random.randint(0,n-1)
                j=random.randint(0,n-1)
                path_new=change_path(path,i,j)
                p=metropolis(path,path_new,T)
                p_random=random.random()
    
                if p_random <= p: # 当 path_new 更优时,p=1 , p_random<=p必成立, 若path_new不优,则以一定概率p变成path_new
                    path=path_new
            print('温度',T,'下的优解:',path)
            T=T_update(t,T)
    
        best=path_len(path)
        print('最优解为:',path)
        print('最优解长度:',best)
    
    
    path0= [47,  70,  68,  11,  36,  74,  81,  71,  86,  76,  34,  77,  80,
            85,  19,  49,  84,   2,  98,  20,  67,  13,  58,  33,  99,  44,
            66,  35,  30,   3,  56,  18,   1,  93,   9,  32,  12,  40,  90,
            51,  23, 100,  53,  59,  73,  22,  65,  97,  52,  64,  92,  72,
            17,  14,  31,  69,  50,   4,  78,  89,  57,  55,  45,  82,  10,
            28,  96,  91,  87,  42,   7,  83,  46,  61,   5,  29,  39,  21,
            88,  79,  26,  62,  27,  25,   8,  48,  94,  54,  24,  63,  43,
            75,  41,  15,  16,  95,  38,  60,  37,   6]
    disfire(path0)
    

    其中 初始温度T和结束温度T_end可以不断调试择优
    温度更新函数选择 经典退火函数
    在这里插入图片描述

    四、分别用这三种方法得出结果,进行比较

    由于这三种方法的路径更新都有随机因素,所以每种方法运行五次得出结果进行观察与比较
    在这里插入图片描述

    由表可见,
    模拟退火法由于有自动跳出局部解的能力,而有更多地机会得到更优解;这种方法得到的优解远小于爬山法和贪心法,并且得到的优解波动并不大,耗时波动也不大
    爬山法是相对比较耗时(依赖于每次搜索的迭代次数,由于我这里设置的比较多,所以爬山法过慢),但是得到的解并不一定优于贪心法,因为它每次都选取下山最快的路径,更容易陷入某些局部解;但它在一定几率上会获得比贪心法好很多的解
    贪心法最易于理解最简单的方法,除了容易陷入局部解,好像没有什么其他缺点(随机效果也会产生一些缺点)

    展开全文
  • 关注公众号 长歌大腿,发送“机器学习”关键字,可获取包含机器学习(包含深度学习),统计概率,优化算法等系列文本与视频经典资料,如《ESL》《PRML》.../上周在无意间跟室友讨论到TSP问题时,我觉得应该把这个...

    此实验的代码的github
    同步至我的阿里云博客(https://yq.aliyun.com/users/1320894660843258)

    #分层规划的旅行商问题解决方案
    /上周在无意间跟室友讨论到TSP问题时,我觉得应该把这个问题整合一下,并给出自己的解决方案,同时代码公布在github,有人做成其他版本的与其他人探讨共同进步。
    无特别说明情况下,聚类指的是kmeans聚类
    /

    ##摘要
    本文采用分层规划的思想,层层聚类,直至最底层单个城市群数量满足一定阈值,然后利用整数规划求最底层城市群的精确解,单层之间的城市群路径规划同样采用整数规划求精确解,这里的城市群路径规划指的是城市群的聚类中心之间的路径规划,最高层为闭合路径的TSP问题,以下单层包括底层都为确定起点终点的不闭合TSP问题,这里的不闭合TSP问题的起点终点贪心的由上一级城市群聚类中心求出的路径来确定哪两个城市群相邻,并由此计算此相邻城市群的最近子城市群对。

    求出近似路径后再进行局部的随机优化。

    /简单的讲,类比在全球寻找一条可以走遍所有城市的最短路,每个城市只能访问一次,我们先找大范围的路径,如亚洲->非洲->欧洲->北美洲->南美洲->大洋洲->亚洲,然后在往下分层,比如非洲,先计算非洲与它的前驱亚洲后继欧洲之间最近的国家对,比如是埃及-伊朗,利比亚-意大利,这样确定了进入非洲的起点埃及,终点利比亚,在非洲国家之间解决走完所有国家且仅访问一次的路径,再针对其中某个国家进行分析,直至到底层的城市为止。最后路径规划出来后再对求出的路径进行局部的优化,特别需要关注的是包含起点终点部分的路径。/

    ##综述
    对于大规模TSP问题,尚没有太好的有效解决方案,现在智能算法如蚁群算法,遗传算法,人工神经网络更为流行与实用。这些在其他文章中可以找到相应的内容。遗传算法(GA)寻解空间好大,我超喜欢GA的。

    ##问题建模

    TSP问题的描述

    给定城市与城市间的连接关系,在有解的前提下,从起点出发,寻找一条路径回到起点,这条路径需要满足经过所有城市,并且每个城市仅能经过一次。

    本文提出的解决方案的建模与数学描述

    1. 首先利用分层规划,层层聚类,直至最底层单个城市群数量满足一定阈值,然后利用整数规划求最底层城市群的精确解。

    2. 最高层为闭合路径的TSP问题,以下单层包括底层都为确定起点终点的不闭合TSP问题,这里的不闭合TSP问题的起点终点贪心的由上一级城市群聚类中心求出的路径来确定哪两个城市群相邻,并由此计算此相邻城市群的最近子城市群对。

    3. 单层之间的城市群路径规划同样采用整数规划求精确解,这里的城市群路径规划指的是城市群的聚类中心之间的路径规划。

    对于Top层如下图所示求闭合路径
    Top示意.png

    对于非top层,实则为确定起点终点的聚类中心之间的路径规划,如下图。
    子城市群示意.png

    子城市顺延示意.png

    对于子层,如果满足子层节点中城市数量不超过一定阈值(整数规划求精确解时间允许的城市数量),则不进行分裂,直接将其进入下一层。
    寻路示意.png

    本文的模型总结与分析

    ##模型算法
    整体结构类似于树的广搜,先处理顶层,再处理后续子层。采取一个队列存储当前层的城市信息。分支定界也让计算复杂度得以控制。

    整数规划求解小规模TSP问题算法

    推荐这篇文章Optimization by Integer Programming

    确定起点终点的不闭合TSP模型解决算法

    这个地方很诡异,建立转化为闭合路径的TSP问题来计算,比如我们可以增加了这样一条规则:

    virtual_node = rand();//设定一个虚拟节点,随机生成坐标
    virtual_node->start_node = 0;//虚拟节点到起始点的距离为0
    virtual_node->end_node = 0;//虚拟节点到终止点的距离为0
    virtual_node->other_nodes = INF;//虚拟节点到除了起点终点的其他节点的距离为很大一个数值
    

    注意,这个是在计算出距离之上直接修改,这个设定在实际上肯定不存在,因为这样会导致起点终点直联的距离不等于由经过虚拟节点的距离,不过这并不影响计算。

    有了这个设定,在这样的一个闭合TSP问题中,肯定会包含一条start_node-virtual_node-end_node的路径,去掉虚拟节点以及其两边,则为确定起点终点的路径,而且因为虚拟节点到起点终点的距离均为0,计算时候也不影响优化结果,解仍然是最优的。

    城市群内部子城市群路径起点终点的确定算法

    因为聚类中心数量并不大,而且可控,直接暴搜走起。

    整体算法流程

    logicImp()
     
        %初始化一些数据
        city;MaxCityNum;...
        
        %分层处理
        while(true)
            %如果全部满足底层条件,退出死循环
            if allCityGroupMinEnough(cityCell,MaxCityNum)
                break;
            end
            
            %否则处理单层问题
            todo
    
            for i=1:cityCellLength
                %子城市群预处理
                todo
    
                %如果子城市群满足不分裂条件,该子城市群出队再入队,跳过当前子城市群
                if cur_city_group_x < MaxCityNum
                    todo
                    continue;
                end
                
                %子城市群边界的处理
                todo
                
                %聚类得到类中心坐标向量与分组
                todo
                
                %得到起始点与终止点
                todo
    
                %如果起点终点一样,即产生冲突,改变一个
                todo
                
                %规划路径,分为顶层与非顶层
                if topFlag == 1
                    circleTspSolver();
                    topFlag = 0;
                else
                    tspSolver();
                end
                
                %检索排序子城市群,分裂的子节点入队。
                todo
                 
            end
            cityCell = cityCellNew;
        end
        
        %处理最底层
        
        for i =1:cityCellLength
            %城市群预处理
             todo
            
            %底层最近邻的起点终点
            todo
    
             %如果起点终点一样,即产生冲突,改变一个
            todo
            
            % 调用整数规划
            tspSolver();
            
            %处理结果
            todo
    
        end
    end
    

    ##实验
    在tsplib数据集上的测试(我们只测试个大规模的),与精确解稳定在10%的损失,不逊于一般论文的方法的测试结果!

    数据集名字1 最优解 本文得到的解 比例
    ja9847 491924 561460 0.8762
    展开全文
  • ** Description:禁忌搜索算法解决TSP问题 5 ** Author: 1702-GCJ 6 ** Version: 1.1 7 ** Date: 2017/10/3 8 ** History: 无 9 ** Modification: IsFindTabu(Queue * Q,const Tabu *item) ...
    本文着重于算法的实现,对于理论部分可自行查看有关资料可以简略参考该博文:http://blog.csdn.net/u013007900/article/details/50379135
    本文代码部分基于C实现,源码如下:
      1 /*****************************************************************************
      2 **    Copyright: NEW NEU laboratory
      3 **    File name: CTSP
      4 **    Description:禁忌搜索算法解决TSP问题
      5 **    Author: 1702-GCJ
      6 **    Version: 1.1  
      7 **    Date: 2017/10/3
      8 **    History: 无 
      9 ** Modification: IsFindTabu(Queue * Q,const Tabu *item) 
     10 *****************************************************************************/
     11 
     12 #include"stdio.h"
     13 #include"stdlib.h"
     14 #include"string.h"
     15 #include "time.h"
     16  
     17 #define CityNum         31       //城市的数量 
     18 #define TabuLength     21     //禁忌表长度(根号下的 种类)
     19 #define Neighbor        400     //邻居个数 
     20 #define MaxNG            400    //迭代次数    
     21 
     22 int currentNG = 0;             //当前迭代次数
     23 int DesireLevel = 0;            //渴望水平 (即最短距离) 
     24 
     25 typedef int ElementType;
     26 ElementType **Distance;        //存储各个城市之间的距离矩阵的指针 数据都是取整的 
     27 
     28 /***************************************************************************************读取数据区******************************************/
     29  
     30 /*************************************************
     31 **Function: MemBlockCity
     32 **Description: 申请存储城市距离空间 
     33 **Calls: 无
     34 **Called By: ReadDataTxt()
     35 **Input: 无
     36 **Output: 无 
     37 **Return: 指向存储城市距离空间的指针 
     38 **Others: 用完需要释放掉相应内存 
     39 *************************************************/
     40 ElementType ** MemBlockCity();
     41 
     42 /*************************************************
     43 **Function: PrintCityDistance
     44 **Description: 显示Distance信息
     45 **Calls: 无
     46 **Called By: main()
     47 **Input: Distance 全局变量的指针  
     48 **Output: 无 
     49 **Return: void 
     50 **Others: 无
     51 *************************************************/
     52 void PrintCityDistance( ElementType **  distance);
     53 
     54 /*************************************************
     55 **Function: ReadDataTxt
     56 **Description: 从txt文档中读取数据
     57 **Calls: MemBlockCity() 
     58 **Called By: main
     59 **Input: 无
     60 **Output: 无 
     61 **Return: void 
     62 **Others: 里面直接用的全局变量 指针Distance 
     63 *************************************************/
     64 void ReadDataTxt();
     65 
     66 /*************************************************
     67 **Function: WriteDataTxt
     68 **Description: 将Distance全局数组数据写到txt文档中去  
     69 **Calls: 无
     70 **Called By: main()
     71 **Input: 无
     72 **Output: 无 
     73 **Return: void 
     74 **Others: 里面用到了宏值CityNum值 
     75 *************************************************/
     76 void WriteDataTxt();
     77 /**********************************************************************************禁忌表操作区*******************************************/
     78 typedef struct _Tabu{
     79     int smallNum;
     80     int bigNum;    //存储数量大的元素 
     81 }Tabu; //禁忌表结构 
     82 
     83 typedef struct _Queue{
     84     Tabu *tabuList;//队列空间指针 
     85     int rear;        //指向尾部 
     86     int front;        //指向队列的头部 
     87     int maxSize;    //记录队列的最大个数 
     88     int count;        //记录资源个数 判断队列空满 
     89     int tabuIndex;    //在禁忌表中找到禁忌元素时 存储该值在禁忌表中的位置 
     90 }Queue;//循环队列的形式 
     91 
     92 /*************************************************
     93 **Function: CreateQueue
     94 **Description: malloc一个禁忌表队列并初始化 
     95 **Calls: 无
     96 **Called By: main()
     97 **Input: tabuLength 禁忌表数据长度 
     98 **Output: 无 
     99 **Return: Queue * 队列变量 
    100 **Others: 里面用到了宏值CityNum值 ,用完需要释放掉相应内存 
    101 *************************************************/
    102 Queue * CreateQueue(int tabuLength);
    103 
    104 /*************************************************
    105 **Function: UpdateTabu
    106 **Description: 更新禁忌表 
    107 **Calls: IsFindTabu() 
    108 **Called By: TSP()
    109 **Input: Q 禁忌表队列 item 加入禁忌表的Tabu结构的变量 
    110 **Output: 无 
    111 **Return: void 
    112 **Others:  
    113 *************************************************/
    114 void UpdateTabu(Queue *Q,Tabu *item);
    115 
    116 /*************************************************
    117 **Function: IsFindTabu
    118 **Description: 禁忌表中是否找到这个元素  
    119 **Calls: 无  
    120 **Called By: UpdateTabu() TSP()
    121 **Input: Q 禁忌表队列 item 判断其是否在禁忌表中的Tabu结构的变量的指针 
    122 **Output: 无 
    123 **Return: 0 没有找到这个元素 1 找到这个元素了 
    124 **Others:  
    125 *************************************************/
    126 static int IsFindTabu(Queue * Q,const Tabu *item);
    127 
    128 /****************************************************************************2Opt邻域+TSp核心算法*********************************************/
    129 //定义解的存储类型 向量形式 
    130 typedef struct _Solve{
    131     ElementType *initSolution;            //初始解 
    132     ElementType *currentSolution;        //当前解 
    133     ElementType * optimalSolution;    //最优解 
    134     ElementType *tempSolution;            //临时解   
    135     ElementType lastdistance;             //上次记录的总距离 
    136     ElementType  initdistance;            //定义初始距离 
    137 }StrSolve;
    138 typedef struct _MotionTable{
    139     Tabu  tabu;                                //存储改变的元素 
    140     ElementType changedistance;        //改变的距离 
    141 }MotionTable;//记录2opt邻域移动信息 
    142 
    143 StrSolve * SolutionSpace ;             //解空间(包含当前解和初始解)指针 
    144 MotionTable *motionTable;                //移动元素信息 (一个表格) 
    145 
    146 /*************************************************
    147 **Function: CreateMotionStruct
    148 **Description: 创建并初始化2-Opt 移动信息表格   
    149 **Calls: 无  
    150 **Called By:  Init2Opt()
    151 **Input: neighbor  邻居数量 
    152 **Output: 无 
    153 **Return: MotionTable *指针变量 
    154 **Others: 不用这块内存的时候要释放掉 ! 
    155 *************************************************/
    156 MotionTable* CreateMotionStruct(int neighbor);
    157 
    158 /*************************************************
    159 **Function: CreateSolutionSpace
    160 **Description: 创建并初始化解空间
    161 **Calls: 无  
    162 **Called By:  Init2Opt()
    163 **Input: cityNum  城市数量 
    164 **Output: 无 
    165 **Return: StrSolve  *指针变量 
    166 **Others: 不用这块内存的时候要逐一释放掉 ! 
    167 *************************************************/
    168 StrSolve *CreateSolutionSpace(int cityNum);
    169 
    170 /*************************************************
    171 **Function: GetInitSolution
    172 **Description: 获得初始解
    173 **Calls: 无  
    174 **Called By:  Init2Opt()
    175 **Input: StrSolve * 指针变量 
    176 **Output: 无 
    177 **Return: StrSolve  *指针变量 
    178 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ! 
    179 *************************************************/ 
    180 void GetInitSolution(StrSolve * strSolve);
    181 
    182 /*************************************************
    183 **Function: Init2Opt
    184 **Description: 初始化TSP需要用的值 
    185 **Calls: CreateMotionStruct()  CreateSolutionSpace()  GetInitSolution()
    186 **Called By:  main
    187 **Input: 无 
    188 **Output: 无 
    189 **Return: void
    190 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ! 不知道为什么只能在Main函数中调用否则 会出现段错误 
    191 *************************************************/ 
    192 void Init2Opt();
    193 
    194 /*************************************************
    195 **Function: FindPosition
    196 **Description: 在数组中找到指定元素值的位置 
    197 **Calls: 
    198 **Called By:  Get2OptChangeDistance()  TSP()
    199 **Input: solution 一维数组指针  tabu  Tabu结构指针 
    200 **Output: 无 
    201 **Return: void
    202 **Others: 这里是从solution[1]开始查找到的! 
    203 *************************************************/ 
    204 static void FindPosition(const ElementType * solution,Tabu *tabu);
    205 
    206 /*************************************************
    207 **Function: FindPosition
    208 **Description: 获得2邻域变化值 
    209 **Calls: FindPosition()
    210 **Called By:  Get2optSolution()
    211 **Input:  tabu  Tabu结构指针  solution 一维数组指针 
    212 **Output: 无 
    213 **Return: ElementType 2邻域城市变化值 
    214 **Others: 返回的值越小越好 ! 
    215 *************************************************/
    216 static ElementType Get2OptChangeDistance(Tabu * tabu,const ElementType * solution);
    217 
    218 /*************************************************
    219 **Function: Get2optSolution
    220 **Description: 得到1个2邻域解 将移动元素,及其导致路径的变化值 存储到移动表中 
    221 **Calls: Get2OptChangeDistance()
    222 **Called By:  TSP()
    223 **Input:  strSolve 解空间指针  motiontable 移动表指针 
    224 **Output: 无 
    225 **Return: void 
    226 **Others: 随机数要注意! 
    227 *************************************************/
    228 void Get2optSolution(const StrSolve * strSolve,MotionTable *motiontable );
    229 
    230 /*************************************************
    231 **Function: Insert_Sort
    232 **Description: 按从小到大排序 插入排序 将制定的类数组变量 的内容进行排序 
    233 **Calls: 无
    234 **Called By:  FindBestMotionValue()
    235 **Input:    motiontable 移动表指针  n为类数组 元素个数 
    236 **Output: 无 
    237 **Return: void 
    238 **Others: 
    239 *************************************************/
    240 void Insert_Sort (MotionTable * motiontable,int n);
    241 
    242 /*************************************************
    243 **Function: FindBestMotionValue
    244 **Description: 找到移动表中最小的值 即为最优值 
    245 **Calls: Insert_Sort()
    246 **Called By:  TSP()
    247 **Input:    motiontable 移动表指针  
    248 **Output: 无 
    249 **Return: MotionTable *型的指针 存储移动表中最好值的表格指针 
    250 **Others: 
    251 *************************************************/
    252 MotionTable * FindBestMotionValue( MotionTable * motiontable);
    253  
    254 /*************************************************
    255 **Function: GetInitLevel
    256 **Description: 获取初始解的渴望水平 
    257 **Calls: 
    258 **Called By:  TSP()
    259 **Input:    distance 存储城市的矩阵指针 initSolution 初始解指针  
    260 **Output: 无 
    261 **Return: 初始解的渴望水平 
    262 **Others: 
    263 *************************************************/
    264 int GetInitLevel( ElementType **distance,ElementType * initSolution);
    265 
    266 /*************************************************
    267 **Function: TSP
    268 **Description: TSP核心算法 
    269 **Calls: GetInitLevel() 
    270 **Called By:  TSP()  Get2optSolution()  FindBestMotionValue()  UpdateTabu()  FindPosition()  memcpy()
    271 **Input:    distance 存储城市的矩阵指针 solutionSpace 解空间指针 motiontable 移动表 desireLevel 渴望水平 queue 禁忌表队列指针  
    272 **Output: 最优解信息 
    273 **Return: void  
    274 **Others: 
    275 *************************************************/
    276 void TSP(  ElementType **distance, StrSolve * solutionSpace ,MotionTable *motiontable,int *desireLevel,Queue *queue);
    277 
    278 /*************************************************
    279 **Function: MemFree
    280 **Description: 释放申请的动态内存 
    281 **Calls: free() 
    282 **Called By:  main()
    283 **Input: distance 存储城市距离的变量指针  queue 禁忌表队列  motiontable 移动表的指针  strSolve  解空间的指针 
    284 **Output: 无 
    285 **Return: void
    286 **Others: 这里也可以一步一步的释放掉 各自的指针 因为就用一个.c所以释放内存的操作都在这里进行 
    287 *************************************************/  
    288 void MemFree(ElementType ** distance,Queue *queue,MotionTable *motiontable,StrSolve *strSolve);
    289 
    290 
    291 /*******************************************************************************MAIN函数*************************************/
    292 int main(int argc,char *argv[])
    293 {
    294 //    Tabu item;
    295     clock_t start, finish;
    296     double  duration;
    297     Queue * queue = CreateQueue(TabuLength); //创建一个禁忌表队列 本身就初始化好了 
    298     Init2Opt();//初始化相关 
    299     // 设置随机数种子 为以后使用rand()做准备 
    300    srand((unsigned int)time(0));
    301     
    302     start = clock();
    303     ReadDataTxt(Distance);//必须放在前面  读取数据后 才能操作 
    304 //    PrintCityDistance(Distance); //显示二维数组的数据 只显示5X5 
    305 // WriteDataTxt(Distance);//将distance 数据写入txt 
    306     TSP( Distance,SolutionSpace ,motionTable,&DesireLevel,queue);    
    307     
    308 ////    //将得到的最优解 从新用TSP算法算 
    309 //    memcpy( SolutionSpace->initSolution,SolutionSpace->optimalSolution,sizeof(ElementType)*CityNum ); //将临时解空间值复制到当前解空间 
    310 //    printf("\n新初始解的渴望水平:%d  \n",GetInitLevel(Distance,SolutionSpace->optimalSolution));
    311 //    TSP( Distance,SolutionSpace ,motionTable,&DesireLevel,queue);
    312 //    
    313     finish = clock();
    314     duration = (double)(finish - start) / CLOCKS_PER_SEC;
    315     printf("\n           TSP算法运行时间:%.4f秒       \n",duration);
    316     MemFree(Distance, queue,motionTable,SolutionSpace);
    317    return 0;  
    318 } 
    319 
    320 
    321 /************************************************************************读取数据区***********************************************/ 
    322 
    323 /*************************************************
    324 **Function: MemBlockCity
    325 **Description: 申请存储城市距离空间 
    326 **Calls: 无
    327 **Called By: ReadDataTxt() 在txt文档中读取数据 
    328 **Input: 无
    329 **Output: 无 
    330 **Return: 指向存储城市距离空间的指针 
    331 **Others: 无
    332 *************************************************/
    333 ElementType ** MemBlockCity()
    334 {
    335     ElementType ** Distance; 
    336     int i=0;
    337     
    338     //动态申请一块内存存储城市之间的数据
    339     Distance = (ElementType **)malloc(sizeof(ElementType *)*CityNum);
    340     for(i = 0;i< CityNum ; i++){
    341         Distance[i] = (ElementType *)malloc(sizeof (ElementType )* CityNum);
    342     }
    343     return Distance;
    344 }
    345 
    346 /*************************************************
    347 **Function: PrintCityDistance
    348 **Description: 显示Distance信息 这里仅仅显示了CityNum-25个元素 因为屏幕显示不开 
    349 **Calls: 无
    350 **Called By: main()
    351 **Input: Distance 全局变量的指针  
    352 **Output: 无 
    353 **Return: void 
    354 **Others: 无
    355 *************************************************/
    356 void PrintCityDistance( ElementType **  distance)
    357 {
    358     int i,j;
    359     for(i = 0; i< CityNum-25;i++){
    360         for(j = 0;j<CityNum-25;j++)
    361             printf("%d ",distance[i][j]);
    362         printf("\n");
    363     }
    364 }
    365 
    366 /*************************************************
    367 **Function: ReadDataTxt
    368 **Description: 从txt文档中读取数据
    369 **Calls: MemBlockCity() 
    370 **Called By: main()
    371 **Input: 无
    372 **Output: 无 
    373 **Return: void 
    374 **Others: 里面直接用的全局变量 指针Distance 
    375 *************************************************/
    376 void ReadDataTxt()
    377 {
    378     //     FILE *fpRead=fopen("F:\\GCJ\\Desktop\\智能优化方法作业\\data.txt","r"); 
    379     FILE *fpRead=fopen("data.txt","r");  //从data.txt中读取数据 
    380     int i,j;
    381     if(fpRead==NULL){  
    382           printf("open file data.txt failed!\n");
    383        exit(1);
    384     }
    385     Distance = MemBlockCity();    //申请一块存储城市数量空间         
    386     for(i=0;i<CityNum;i++){
    387         Distance[i][i] = 0;
    388         for(j=i+1 ;j < CityNum;j++ ){
    389             fscanf(fpRead,"%d",&Distance[i][j]);//自动读取数据 只要自己能够控制好存储位置即可 
    390             Distance[j][i] = Distance[i][j];  
    391         }
    392     } 
    393     fclose(fpRead);
    394 }
    395 
    396 /*************************************************
    397 **Function: WriteDataTxt
    398 **Description: 将Distance全局数组数据写到txt文档中去 
    399 **Calls: 无
    400 **Called By: main()
    401 **Input: 无
    402 **Output: 无 
    403 **Return: void 
    404 **Others: 里面用到了宏值CityNum值 
    405 *************************************************/
    406 void WriteDataTxt(ElementType **distance)
    407 {
    408     FILE *fpWrite;
    409     int i,j;
    410     fpWrite=fopen("F:\\GCJ\\Desktop\\智能优化方法作业\\data.txt","w");  //从data.txt中写数据 
    411     for(i = 0;i< CityNum;i++){
    412         for(j=0;j<CityNum;j++)
    413             fprintf(fpWrite,"%d ",distance[i][j]);//这里%d后面必须要有空格 否则 直接输出连续的数字 
    414             fprintf(fpWrite,"\n");
    415     }
    416     fclose(fpWrite);
    417 }
    418 
    419 /**************************************************************禁忌表操作区*****************************************************/
    420 
    421 /*************************************************
    422 **Function: CreateQueue
    423 **Description: malloc一个禁忌表队列并初始化 
    424 **Calls: 无
    425 **Called By: main()
    426 **Input: tabuLength 禁忌表数据长度 
    427 **Output: 无 
    428 **Return: Queue * 队列变量 
    429 **Others: 里面用到了宏值CityNum值 
    430 *************************************************/
    431 Queue * CreateQueue(int tabuLength)
    432 {
    433     Queue * queue = (Queue *)malloc(sizeof(struct _Queue));//申请一块队列变量
    434     //queue->tabuList =(ElementType *)malloc(sizeof(ElementType)*MaxSize);//申请一块数组空间 
    435     queue->tabuList =(Tabu *)malloc(sizeof(Tabu)*tabuLength);//21的长度 
    436     queue->front = 0;
    437     queue->rear = 0;//头尾 都为0 
    438     queue->maxSize = tabuLength;
    439     queue->count =0;
    440     queue->tabuList[0].smallNum = 0;
    441     queue->tabuList[0].bigNum  = 0;
    442     return queue;
    443 } 
    444 
    445 /*************************************************
    446 **Function: IsFindTabu
    447 **Description: 禁忌表中是否找到这个元素  
    448 **Calls: 无  
    449 **Called By: UpdateTabu() TSP()
    450 **Input: Q 禁忌表队列 item 判断其是否在禁忌表中的Tabu结构的变量的指针 
    451 **Output: 无 
    452 **Return: 0 没有找到这个元素 1 找到这个元素了 
    453 **Others:  
    454 *************************************************/
    455 static int IsFindTabu(Queue * Q,const Tabu *item)
    456 {
    457     Tabu tabu;
    458     int i; 
    459     int IsFindFlag = 0 ; 
    460     
    461     //将要禁忌的值按顺序放在中间变量中 方便加入到禁忌表中 
    462     if( (*item).bigNum >= (*item).smallNum ){
    463         tabu.bigNum = (*item).bigNum;
    464         tabu.smallNum = (*item).smallNum;
    465     }    
    466     else{
    467         tabu.bigNum = (*item).smallNum;
    468         tabu.smallNum = (*item).bigNum;
    469     } 
    470     
    471     //查找禁忌表中是否有这个禁忌元素  没有的话 插入元素在头部 否则把这个元素加上惩罚政策加入到禁忌表的头部 其他依次降序    
    472     for(i = Q->front; (i%TabuLength)!= Q->rear; ){//这个查找函数有问题了 因为循环队列的话 队列慢点话 rear = front  如何解决? 
    473         if( (tabu.smallNum == Q->tabuList[i].smallNum ) && ( tabu.bigNum == Q->tabuList[i].bigNum )  ){ 
    474         //说明在禁忌表中找到这个元素了 那么就惩罚这个 放在最前面 
    475         //把第一个元素放入 这个值 剩下的依次 递减排列 
    476 //            printf("在禁忌表中找到了%d %d\n",tabu.bigNum,tabu.smallNum);
    477 
    478             //新加     记录位置 
    479             Q->tabuIndex = i; 
    480             
    481             IsFindFlag  = 1;
    482             return IsFindFlag ;    //表示不管了 
    483         }    
    484         if(++i >= TabuLength)//仅仅让i 在 0 - Tabulength范围内遍历 
    485             i = 0;
    486     }
    487     if( Q->count >= TabuLength ){//说明禁忌表满 那么rear值就需要访问了  否则不需要访问 
    488         if( i%TabuLength == Q->rear )//因为循环队列寻找的时候 最后一个元素 无法通过for循环遍历到 
    489         if( (tabu.smallNum == Q->tabuList[i].smallNum ) && ( tabu.bigNum == Q->tabuList[i].bigNum )  ){ 
    490 //            printf("找到了最新的了%d %d\n",tabu.smallNum,tabu.bigNum);    
    491             
    492             //新加     记录位置 
    493             Q->tabuIndex = Q->rear; 
    494             
    495             IsFindFlag  = 1;
    496             return IsFindFlag ;    //表示不管了 
    497         }
    498     }
    499     
    500         return IsFindFlag;//之前这里就忘了加了 注意这点    !! 
    501 }
    502 
    503 /*************************************************
    504 **Function: UpdateTabu
    505 **Description: 更新禁忌表 
    506 **Calls: IsFindTabu()  
    507 **Called By: TSP()
    508 **Input: Q 禁忌表队列 item 加入禁忌表的Tabu结构的变量的指针 
    509 **Output: 无 
    510 **Return: void 
    511 **Others:  
    512 *************************************************/
    513 void UpdateTabu(Queue *Q,Tabu *item) 
    514 {
    515     Tabu tabu;
    516     Tabu temptabu;
    517     int i; 
    518 
    519     //将要禁忌的值按顺序放在中间变量中 方便加入到禁忌表中 
    520     if( (*item).bigNum >= (*item).smallNum ){
    521         tabu.bigNum = (*item).bigNum;
    522         tabu.smallNum = (*item).smallNum;
    523     }    
    524     else{
    525         tabu.bigNum = (*item).smallNum;
    526         tabu.smallNum = (*item).bigNum;
    527     }
    528         
    529     if( !IsFindTabu(Q,item) ){
    530         //如果没有找到  那么直接在队列插入这个元素    
    531         if( Q->count < TabuLength ){ //说明队列不满 那就直接插入元素
    532             Q->count++ ;//最后满的时候为21个元素 
    533             Q->tabuList[Q->rear++] = tabu;//在后面插入 然后从前面取出元素 
    534             if( Q->rear >= TabuLength)//到了尾部的话 就直接从前面开始存储  尾部先存储后+1 
    535                 --Q->rear ;//说明禁忌表满了的时候 让rear指向最后一个元素即可 
    536         } 
    537         else{//满了的话 就直接头部删除 尾部加入 //不是真正的删除 仅仅是释放掉这块存储空间 
    538             if( ++Q->front >= TabuLength )
    539                 Q->front  =0;
    540             if( ++Q->rear >= TabuLength)//到了尾部的话 就直接从前面开始存储  尾部先存储后+1 
    541                 Q->rear = 0;
    542             Q->tabuList[Q->rear]  = tabu;
    543         }
    544     }
    545     else{//在禁忌表中找到这个元素的时候 需要进行惩罚 将这个值放在头部,而该值前面的数依次向后排 
    546         int j,k;
    547         j = Q->tabuIndex ;    //禁忌表中找到的该值的索引
    548         k = Q->front;            //禁忌表头部索引
    549         
    550         if( Q->tabuIndex >= Q->front  ){
    551             
    552             //说明禁忌表没有满 或者 禁忌表满了 但是移动仅仅在Q->front  到这个索引即可 
    553             for( --j ;j >= k ; --j){
    554                 Q->tabuList[j+1] = Q->tabuList[j];
    555             }/*for end*/
    556                 
    557         }
    558         else{
    559             //禁忌表满了且 Q->front 值大于 Q->tabuIndex 
    560             for( ;j == Q->front; --j ){
    561                 if( j >= 1)
    562                     Q->tabuList[j] =Q->tabuList[j-1]; 
    563                 else{ //j == 0
    564                      j = TabuLength ;
    565                     Q->tabuList[0] = Q->tabuList[j-1];
    566                 }
    567             }/*for ...end */
    568         }
    569         //惩罚策略 
    570         Q->tabuList[Q->front] = tabu;
    571         
    572     }/*if find .. else ..end*/
    573     
    574 }
    575 
    576 /******************************************************************************************2Opt邻域+TSp核心算法***********************************/
    577 
    578 /*************************************************
    579 **Function: CreateMotionStruct
    580 **Description: 创建并初始化2-Opt 移动信息表格   
    581 **Calls: 无  
    582 **Called By:  Init2Opt()
    583 **Input: neighbor  邻居数量 
    584 **Output: 无 
    585 **Return: MotionTable *指针变量 
    586 **Others: 不用这块内存的时候要释放掉 ! 
    587 *************************************************/
    588 MotionTable* CreateMotionStruct(int neighbor)
    589 {
    590     int i;
    591     MotionTable * motiontable = (MotionTable *)malloc(sizeof(MotionTable)*neighbor );
    592     for(i = 0;i< neighbor;i++){
    593         motiontable->tabu.smallNum  =0;
    594         motiontable->tabu.bigNum = 0;
    595         motiontable->changedistance = 0;
    596     }
    597     return motiontable;
    598 } 
    599 
    600 /*************************************************
    601 **Function: CreateSolutionSpace
    602 **Description: 创建并初始化解空间
    603 **Calls: 无  
    604 **Called By:  Init2Opt()
    605 **Input: cityNum  城市数量 
    606 **Output: 无 
    607 **Return: StrSolve  *指针变量 
    608 **Others: 不用这块内存的时候要逐一释放掉 ! 
    609 *************************************************/
    610 StrSolve *CreateSolutionSpace(int cityNum)
    611 {
    612     int i;
    613     StrSolve *strSolve = (StrSolve *)malloc( sizeof(StrSolve) ) ;
    614     strSolve->initSolution = ( ElementType *)malloc(sizeof(ElementType)*cityNum );
    615     strSolve->currentSolution = ( ElementType *)malloc(sizeof(ElementType)*cityNum );
    616     strSolve->optimalSolution = ( ElementType *)malloc(sizeof(ElementType)*cityNum );
    617     strSolve->tempSolution = ( ElementType *)malloc(sizeof(ElementType)*cityNum );
    618     
    619     //初始化解空间 
    620     for(i = 0;i< cityNum;i++){
    621         strSolve->initSolution[i] = (ElementType)0;
    622         strSolve->currentSolution[i] = (ElementType)0;
    623         strSolve->optimalSolution[i] = (ElementType)0;
    624         strSolve->tempSolution[i] = (ElementType)0;
    625     }
    626     strSolve->lastdistance  = 0;//记录上次迭代获得最好的距离值 
    627     return strSolve;
    628  } 
    629 
    630 /*************************************************
    631 **Function: GetInitSolution
    632 **Description: 获得初始解
    633 **Calls: 无  
    634 **Called By:  Init2Opt()
    635 **Input: StrSolve * 指针变量 
    636 **Output: 无 
    637 **Return: StrSolve  *指针变量 
    638 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ! 
    639 @brief :思路 可以用一个记录初始解的类数组(申请的内存 大小为初始解的元素个数),之后循环 CityNum-1次,不断的产生1-CityNum-1的随机数
    640  没产生一个就记录这个值 之后再次产生与上次不同的随机数 ,依次这样循环即可  不过速度上会很慢 
    641 *************************************************/ 
    642 void GetInitSolution(StrSolve * strSolve)
    643 { 
    644     int i;
    645     
    646     //默认从0号城市顺序开始 这里的0是固定不动的 
    647     for( i = 0;i<CityNum;i++){
    648         strSolve->initSolution[i] = i;
    649         strSolve->currentSolution[i] = i;
    650         strSolve->optimalSolution[i] = i;
    651         strSolve->tempSolution[i] = i;
    652     }
    653         
    654 }
    655 
    656 /*************************************************
    657 **Function: Init2Opt
    658 **Description: 初始化TSP需要用的值 
    659 **Calls: CreateMotionStruct()  CreateSolutionSpace()  GetInitSolution()
    660 **Called By:  main()
    661 **Input: 无 
    662 **Output: 无 
    663 **Return: void
    664 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ! 不知道为什么只能在Main函数中调用否则 会出现段错误 
    665 *************************************************/ 
    666 void Init2Opt()
    667 {
    668     motionTable = CreateMotionStruct(Neighbor);//初始化变化表  记录变化邻居值 
    669     SolutionSpace = CreateSolutionSpace(CityNum);//创建解空间 
    670     GetInitSolution(SolutionSpace);//初始化解 
    671 }
    672 
    673 /*************************************************
    674 **Function: MemFree
    675 **Description: 释放申请的动态内存 
    676 **Calls: 
    677 **Called By:  main()
    678 **Input: distance 存储城市距离的变量指针  queue 禁忌表队列  motiontable 移动表的指针  strSolve  解空间的指针 
    679 **Output: 无 
    680 **Return: void
    681 **Others: 这里也可以一步一步的释放掉 各自的指针 因为就用一个.c所以释放内存的操作都在这里进行 
    682 *************************************************/ 
    683 void MemFree(ElementType ** distance,Queue *queue,MotionTable *motiontable,StrSolve *strSolve)
    684 {
    685     int i=0;
    686     int j = 0;
    687     
    688     //释放矩阵元素存储区 
    689     for(i = 0;i < CityNum; i++){
    690         free( distance[i] );
    691     }
    692     free(distance);
    693     
    694     //释放移动表
    695     free(motiontable); 
    696     
    697     //释放掉队列区 
    698     free(queue->tabuList);
    699     free(queue);
    700     
    701     //释放解空间
    702     free(strSolve->initSolution);
    703     free(strSolve->currentSolution);
    704     free(strSolve->optimalSolution);
    705     free(strSolve->tempSolution);
    706     free(strSolve); 
    707 
    708 }
    709 
    710 /*************************************************
    711 **Function: FindPosition
    712 **Description: 在数组中找到指定元素值的位置 
    713 **Calls: 
    714 **Called By:  Get2OptChangeDistance()  TSP()
    715 **Input: solution 一维数组指针  tabu  Tabu结构指针 
    716 **Output: 无 
    717 **Return: void
    718 **Others: 这里是从solution[1]开始查找到的! 
    719 *************************************************/ 
    720 static void FindPosition(const ElementType * solution,Tabu *tabu)
    721 {
    722     int i;
    723     Tabu tempTabu;
    724     for(i = 1; i< CityNum;i++){
    725         if( solution[i] == tabu->smallNum )
    726             tempTabu.smallNum = i;
    727         if( solution[i] == tabu->bigNum )
    728             tempTabu.bigNum = i;
    729     }
    730     *tabu = tempTabu;//不能直接返回&tempTabu  因为这个是一个局部的变量 会有悬挂指针的后果 
    731 }
    732 
    733 /*************************************************
    734 **Function: FindPosition
    735 **Description: 获得2邻域变化值 
    736 **Calls: FindPosition()
    737 **Called By:  Get2optSolution()
    738 **Input:  tabu  Tabu结构指针  solution 一维数组指针 
    739 **Output: 无 
    740 **Return: ElementType 2邻域城市变化值 
    741 **Others: 返回的值越小越好 ! 
    742 *************************************************/
    743 static ElementType Get2OptChangeDistance(Tabu * tabu,const ElementType * solution)
    744 {
    745     ElementType change1,change2;
    746     Tabu tempTabu1 = *tabu;
    747     Tabu tempTabu;
    748     change1 = change2 = 0;
    749     FindPosition(solution,&tempTabu1); //此时这里的tempTabu1存储的就是指定元素在 解空间中的位置 
    750     tempTabu.bigNum  = ( tempTabu1.bigNum >tempTabu1.smallNum )? tempTabu1.bigNum: tempTabu1.smallNum;
    751     tempTabu.smallNum  = ( tempTabu1.bigNum >tempTabu1.smallNum )? tempTabu1.smallNum: tempTabu1.bigNum;
    752     
    753     if( tempTabu.smallNum == tempTabu.bigNum-1){//两个元素在解空间中的 位置相差1 
    754             if( tempTabu.bigNum == CityNum-1 ){    //最大值位置 在最后一个位置    
    755                 change1  = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.smallNum] ]+\
    756                               Distance[ solution[tempTabu.bigNum] ][ solution[ 0] ];
    757                 change2 =  Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.bigNum] ] +\
    758                               Distance[    solution[tempTabu.smallNum] ][ solution[0] ];
    759                 return (change2 - change1);//这个值越小越好 
    760             }
    761             else{
    762                 change1  = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.smallNum] ] +\
    763                               Distance[ solution[tempTabu.bigNum] ][ solution[ tempTabu.bigNum +1] ];
    764                 change2 =  Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.bigNum] ]   +\
    765                               Distance[    solution[tempTabu.smallNum] ][ solution[tempTabu.bigNum +1] ];
    766                               
    767                 return (change2 - change1);
    768             }
    769     }
    770     else{//两个元素位置 不挨着 
    771         if( tempTabu.bigNum == CityNum-1 ){    //最大值位置 在最后一个位置    
    772                 change1 = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.smallNum] ] +\
    773                              Distance[ solution[tempTabu.smallNum] ][ solution[tempTabu.smallNum +1] ] +\
    774                              Distance[ solution[tempTabu.bigNum-1] ][ solution[ tempTabu.bigNum ] ]    +\
    775                              Distance[ solution[tempTabu.bigNum] ][ solution[ 0] ];
    776                 change2 = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.bigNum] ] +\
    777                              Distance[ solution[tempTabu.bigNum] ][ solution[tempTabu.smallNum+1] ]    +\
    778                              Distance[ solution[tempTabu.bigNum-1] ][ solution[ tempTabu.smallNum ] ]+\
    779                              Distance[ solution[tempTabu.smallNum] ][ solution[0] ];
    780                 return (change2 - change1);//这个值越小越好 
    781             }
    782             else{
    783                 
    784                 change1 = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.smallNum] ] +\
    785                              Distance[ solution[tempTabu.smallNum] ][ solution[tempTabu.smallNum +1] ] +\
    786                              Distance[ solution[tempTabu.bigNum-1] ][ solution[ tempTabu.bigNum ] ]    +\
    787                              Distance[ solution[tempTabu.bigNum] ][ solution[ tempTabu.bigNum +1] ];
    788                 change2 = Distance[ solution[tempTabu.smallNum -1] ][ solution[tempTabu.bigNum] ] +\
    789                              Distance[ solution[tempTabu.bigNum] ][ solution[tempTabu.smallNum+1] ]    +\
    790                              Distance[ solution[tempTabu.bigNum-1] ][ solution[ tempTabu.smallNum ] ]+\
    791                              Distance[ solution[tempTabu.smallNum] ][ solution[tempTabu.bigNum +1] ];
    792                 return (change2 - change1);
    793             }
    794     }
    795 
    796 }
    797 
    798 /*************************************************
    799 **Function: Get2optSolution
    800 **Description: 得到1个2邻域解 将移动元素,及其导致路径的变化值 存储到移动表中 
    801 **Calls: Get2OptChangeDistance()
    802 **Called By:  TSP()
    803 **Input:  strSolve 解空间指针  motiontable 移动表指针 
    804 **Output: 无 
    805 **Return: void 
    806 **Others: 随机数要注意! 
    807 *************************************************/
    808 void Get2optSolution(const StrSolve * strSolve,MotionTable *motiontable )
    809 {
    810     //产生一个1-CityNum-1之间的随机数  因为默认0为初始位置 不能动 
    811     ElementType temp;
    812     ElementType changeDistance;
    813     int rand1,rand2;
    814     
    815 //    rand1 = (CityNum-1) *rand()/(RAND_MAX + 1.0);
    816     rand1 = rand()%(CityNum-1)+1;
    817     rand2 = rand()%(CityNum-1)+1;
    818     while(  rand2 == rand1 )//必须产生两个不同的随机数 切不能为0 
    819         rand2 = rand()%(CityNum-1) +1; 
    820             
    821     //记录交换的两个元素 (不是位置) 
    822     motiontable->tabu.smallNum  = (rand2 >rand1)? rand1:rand2;
    823     motiontable->tabu.bigNum =     (rand2 >rand1)? rand2:rand1;
    824     motiontable->changedistance = Get2OptChangeDistance( &motiontable->tabu ,strSolve->tempSolution ); 
    825          
    826 }
    827 
    828 /*************************************************
    829 **Function: Insert_Sort
    830 **Description: 按从小到大排序 插入排序 将制定的类数组变量 的内容进行排序 
    831 **Calls: 无
    832 **Called By:  FindBestMotionValue()
    833 **Input:    motiontable 移动表指针  n为类数组 元素个数 
    834 **Output: 无 
    835 **Return: void 
    836 **Others: 
    837 *************************************************/
    838 void Insert_Sort (MotionTable * motiontable,int n)
    839 {
    840     //进行N-1轮插入过程
    841     int i,k;
    842     for(i=1; i<n; i++){
    843      //首先找到元素a[i]需要插入的位置
    844      
    845          int j=0;
    846          while( (motiontable[j].changedistance < motiontable[i].changedistance )  && (j <i ) )
    847                  j++;
    848                  
    849          //将元素插入到正确的位置
    850          if(i != j){  //如果i==j,说明a[i]刚好在正确的位置
    851              MotionTable temp = motiontable[i];
    852              for(k = i; k > j; k--){
    853                  motiontable[k] = motiontable[k-1];
    854              }
    855              motiontable[j] = temp;
    856          }
    857     }
    858 }
    859 
    860 /*************************************************
    861 **Function: FindBestMotionValue
    862 **Description: 找到移动表中最小的值 即为最优值 
    863 **Calls: Insert_Sort()
    864 **Called By:  TSP()
    865 **Input:    motiontable 移动表指针  
    866 **Output: 无 
    867 **Return: MotionTable *型的指针 存储移动表中最好值的表格指针 
    868 **Others: 
    869 *************************************************/
    870 MotionTable * FindBestMotionValue( MotionTable * motiontable)
    871 {
    872     //下面是仅仅找到一个最好的值 不管在不在禁忌表中 
    873 //    MotionTable *bestMotion= motiontable;
    874 //    MotionTable *start = motiontable;
    875 //    MotionTable *end     = motiontable + Neighbor-1;
    876 //    while(start++ < end ){
    877 //        if( start->changedistance < bestMotion->changedistance){
    878 //            bestMotion = start;//保存最好的结构 
    879 //        }
    880 //    }
    881 //    if( start->changedistance < bestMotion->changedistance )
    882 //        bestMotion = start; 
    883 //    return bestMotion;//f返回最好结构的指针
    884     Insert_Sort(motiontable,Neighbor);//选择排序算法 从小到大排    
    885      
    886     return motiontable;//返回最好元素的地址 
    887 } 
    888 
    889 /*************************************************
    890 **Function: GetInitLevel
    891 **Description: 获取初始解的渴望水平 
    892 **Calls: 
    893 **Called By:  TSP()
    894 **Input:    distance 存储城市的矩阵指针 initSolution 初始解指针  
    895 **Output: 无 
    896 **Return: 初始解的渴望水平 
    897 **Others: 
    898 *************************************************/
    899 int GetInitLevel( ElementType **distance,ElementType * initSolution)
    900 {
    901     int i;
    902     int SumLevel = 0;
    903     for(i = 0; i < CityNum-2 ; i++){
    904         SumLevel += distance[ initSolution[i] ][ initSolution[i+1] ];
    905     } 
    906     SumLevel+= distance[ initSolution[i] ][0];//最后在加上 最后一个值和初始值的 距离 才是循环的总距离距离 
    907     
    908     return SumLevel; 
    909 }
    910 
    911 /*************************************************
    912 **Function: TSP
    913 **Description: TSP核心算法 
    914 **Calls: GetInitLevel() 
    915 **Called By:  TSP()  Get2optSolution()  FindBestMotionValue()  UpdateTabu()  FindPosition()  memcpy()
    916 **Input:    distance 存储城市的矩阵指针 solutionSpace 解空间指针 motiontable 移动表 desireLevel 渴望水平 queue 禁忌表队列指针  
    917 **Output: 最优解信息 
    918 **Return: void  
    919 **Others: 
    920 *************************************************/
    921 void TSP(  ElementType **distance, StrSolve * solutionSpace ,MotionTable *motiontable,int *desireLevel,Queue *queue)
    922 {
    923     int i;
    924     int temp;
    925     int neighborNum = 0;
    926     MotionTable * BestMotionStruct;
    927     ElementType BestChangeDistance;//最好的改变的值 
    928 //    Init2Opt();//初始化相关 
    929     *desireLevel = GetInitLevel(distance,solutionSpace->initSolution);
    930     solutionSpace->lastdistance = *desireLevel;//初始最优值为上次移动的最好的距离 
    931     solutionSpace->initdistance = solutionSpace->lastdistance;//将初始值给初始距离  之后再判断 减少的距离 
    932     printf("初始距离:%d ",*desireLevel);
    933 //    printf("初始最好的距离是%d,solutionSpace->lastdistance = %d\n",*desireLevel,solutionSpace->lastdistance);
    934     printf("城市数量:%d 迭代次数:%d 邻居个数:%d\n",CityNum,MaxNG,Neighbor);
    935     //迭代 次数作为停止条件 
    936     while( currentNG++ < MaxNG ){
    937         //获得邻居最好解
    938         for( neighborNum = 0; neighborNum < Neighbor; neighborNum++ ){//循环Neighbor那么多次 
    939             Get2optSolution(SolutionSpace,&motionTable[neighborNum] );//将邻域 移动放在移动表中 
    940         } 
    941         
    942         //找到移动表中最小的值 此时解若是 < 渴望水平 则更新最优解 否则找到不在禁忌表中的 最好的解 更新当前解
    943         BestMotionStruct = FindBestMotionValue( motiontable);
    944         BestChangeDistance = BestMotionStruct->changedistance;
    945         
    946          if( solutionSpace->lastdistance + BestChangeDistance < *desireLevel){//当前迭代出的最好的解 小于渴望水平 更新最优解T表当前解 
    947             int temp;
    948             //更新T表
    949             UpdateTabu(queue,&BestMotionStruct->tabu); 
    950             //更新渴望水平
    951             *desireLevel = solutionSpace->lastdistance +BestChangeDistance;
    952             //更新上次迭代的最优值
    953             solutionSpace->lastdistance = *desireLevel;
    954             //更新当前解和最优解 
    955             FindPosition(solutionSpace->tempSolution,&BestMotionStruct->tabu);//找到当前解 对应的解空间的位置  
    956             temp = solutionSpace->tempSolution[ BestMotionStruct->tabu.smallNum ];
    957             solutionSpace->tempSolution[ BestMotionStruct->tabu.smallNum] = solutionSpace->tempSolution[ BestMotionStruct->tabu.bigNum ];
    958             solutionSpace->tempSolution[ BestMotionStruct->tabu.bigNum ] = temp;
    959             memcpy( solutionSpace->currentSolution,solutionSpace->tempSolution,sizeof(ElementType)*CityNum ); //将临时解空间值复制到当前解空间 
    960             memcpy( solutionSpace->optimalSolution,solutionSpace->tempSolution,sizeof(ElementType)*CityNum );
    961     
    962         }
    963         else{//没有小于渴望水平 找到不在禁忌表中最好的移动 
    964             //在移动表中找到不在禁忌表中最好元素 因为拍好序了 所以从表的第二个值开始找即可 
    965             int i;
    966             for(i  = 0;i< Neighbor; i++){
    967                 if( !IsFindTabu(queue,&motiontable[i].tabu) ){
    968                     int temp;
    969                     //不在禁忌表中  则这个值就是目前来说最好的值 
    970                     BestMotionStruct = &motiontable[i];
    971                     //更新T表
    972                     UpdateTabu(queue,&BestMotionStruct->tabu); 
    973                     solutionSpace->lastdistance = solutionSpace->lastdistance + BestMotionStruct->changedistance;
    974                     //更新当前解
    975                     FindPosition(solutionSpace->tempSolution,&BestMotionStruct->tabu);//找到当前解 对应的解空间的位置  
    976                     temp = solutionSpace->tempSolution[ BestMotionStruct->tabu.smallNum ];
    977                     solutionSpace->tempSolution[ BestMotionStruct->tabu.smallNum] = solutionSpace->tempSolution[ BestMotionStruct->tabu.bigNum ];
    978                     solutionSpace->tempSolution[ BestMotionStruct->tabu.bigNum ] = temp;
    979                     memcpy( solutionSpace->currentSolution,solutionSpace->tempSolution,sizeof(ElementType)*CityNum ); //将临时解空间值复制到当前解空间 
    980                     
    981                     break;//跳出循环 
    982                 }        
    983             }
    984         }
    985 
    986     }
    987     currentNG = 0;//将全局迭代次数变量值清零 
    988     printf("\n初始值:%d 最优解值:%d 优化距离:%d\n最优解元素:\n\n",\
    989         solutionSpace->initdistance,\
    990         GetInitLevel(distance,solutionSpace->optimalSolution),solutionSpace->initdistance - *desireLevel); 
    991     for(i = 0 ;i< CityNum;i++){
    992         printf("%d-> ",solutionSpace->optimalSolution[i]);
    993     } 
    994     printf( "%d \n",solutionSpace->optimalSolution[0] );
    995 } 
    View Code

    试验结果如下:

     

    相关资源(源码包以及数据)可在以下网址下载:

    http://download.csdn.net/download/geself/10191257

    运行环境:windows7

    IDE:    DEVC++

     

    转载于:https://www.cnblogs.com/newneul/p/7629828.html

    展开全文
  • 遗传算法解决TSP问题

    2012-05-25 23:56:48
    利用java语言实现遗传算法的TSP问题解决
  • matlab解决TSP问题蚁群算法-蚁群算法解决TSP问题.doc 在求解TSP问题中有比较好的应用,大家可以看一下!!
  • c++解决tsp问题

    2018-01-11 23:01:13
    遗传算法解决tsp问题,C++编写控制台程序,EXE文件查看结果。
  • 一、实验内容:TSP问题二、所用算法的基本思想及复杂度分析:1、蛮力法1)基本思想借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵,任意节点到自身节点的距离为无穷大。在第一行找到最小项a[1][j],从而跳转...

    一、实验内容:

    TSP

    问题

    二、所用算法的基本思想及复杂度分析:

    1

    蛮力法

    1

    )

    基本思想

    借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵,任意节点

    到自身节点的距离为无穷大。在第一行找到最小项

    a[1][j]

    ,从而跳转到

    j

    行,

    再找到最小值

    a[j][k]

    再到第

    k

    行进行查找。

    然后构造各行允

    许数组

    row[n]={1,1

    1}

    ,各列允许数组

    colable[n]={0,1,1

    .1}

    ,其中

    1

    表示允

    许访问,即该节点未被访问;

    0

    表示不允许访问,即该节点已经被访问。

    如果改行或该列不允许访问,跳过该点访问下一节点。程序再发问最后

    一个节点前,所访问的行中至少有

    1

    个允许访问的节点,依次访问这些

    节点找到最小的即可;在访问最后一个节点后,再次访问,会返回

    k=0

    即实现访问源节点,得出一条简单回路。

    2

    )

    复杂度分析

    基本语句是访问下一个行列中最小的点,主要操作是求平方,假设有

    n

    个点,则计算的次数为

    n^2-n

    T(n)=n*(n-1)=O(n^2)

    2

    动态规划法

    1

    )

    基本思想

    展开全文
  • GA算法解决TSP问题

    2020-01-02 16:22:30
    Python语言实现的遗传算法解决TSP问题
  • Hopfield解决TSP问题

    2013-12-05 16:07:23
    MatlAB程序,Hopfield神经网络解决TSP问题
  • MPI并行解决TSP问题

    2018-04-28 11:36:42
    TSP的并行解决,关于虚拟机ubuntu MPI程序代码。TSP的并行解决,关于虚拟机ubuntu MPI程序代码。TSP的并行解决,关于虚拟机ubuntu MPI程序代码。TSP的并行解决,关于虚拟机ubuntu MPI程序代码。
  • 用pso解决tsp问题

    2016-11-14 21:21:15
    用pso解决tsp问题的一篇论文
  • Matlab解决TSP问题

    2010-06-08 20:49:36
    使用Matlab遗传算法思想解决TSP问题
  • 遗传算法解决tsp问题
  • 遗传算法解决TSP问题

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,856
精华内容 742
关键字:

tsp问题解决