货郎担问题是一个组合优化问题

货郎担问题是一个组合优化问题具有npc计算复杂性发表论文因此
       任何能使该问题的求解得以简化的方法模拟退火原理
       都将受到高度的评价和关注一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来
       选出最小的路径虽然该方法在理论上是可行的
       但路径的个数与城市的个数成指数增长
       当城市个数较大时
       该方法的求解时间是难以忍受的
       甚至是不可能完成的以每秒1亿次的计算速度来估算
       如果tsp问题包含20个城市时
       求解时间长达350年；如果要处理30个城市
       则求解时间更长达1+10e16年如此长的时间
       在实际中完成是不现实的基于模拟退火算法在处理全局优化、离散变量优化等困难问题中,具有传统优化算法无可比拟的优势尝试用模拟退火算法求解

模拟退火算法原理来源于固体退火：将固体加温至充分高
       再让其徐徐冷却
       固体内部粒子随温升变为无序状
       而徐徐冷却时粒子渐趋有序模拟退火原理
       在每个温度都达到平衡态
       最后在常温时达到基态
       内能减为最小根据metropolis准则
       粒子在温度t时趋于平衡的概率为e-δe/(kt)
       其中e为温度t时的内能
       δe为其改变量
       k为boltzmann常数用固体退火模拟组合优化问题
       将内能e模拟为目标函数值f
       温度t演化成控制参数t
       即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始
       对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代
       并逐步衰减t值
       算法终止时的当前解即为所得近似最优解
       这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程退火过程由冷却进度表(cooling schedule)控制
       包括控制参数的初值t及其衰减因子δt、每个t值时的迭代次数l和停止条件s

1、初始化：初始温度t(充分大)
       初始解状态s(是算法迭代的起点)模拟退火原理
       每个t值的迭代次数l

论文导读:：］货郎担问题
       即是一个组合优化问题具有npc计算复杂性本文分析了模拟退火算法模型
       研究了用模拟退火算法求解tsp算法的可行性
       并给出了用模拟退火算法求解tsp问题的具体实现方法

论文网8200余万篇毕业论文、各种论文格式和论文范文以及9千多种期刊杂志的论文征稿及论文投稿信息
       是论文写作、论文投稿和论文发表的论文参考网站
       也是科研人员论文检测和发表论文的理想平台
       

以上程序在环境下调试完成模拟退火算法一种新的随机搜索方法
       能有效解决组合优化问题
       模拟退火算法具有使用灵活、运行效率高和较少受到初始条件约束等优点

是1,……,n的一个排列
       表明w1城市出发
       依次经过w2, ……, wn城市
       再返回w1城市初始解可选为

5、若δt′<0则接受s′作为新的当前解
       否则以概率exp(-δt′/t)接受s′作为新的当前解.

//如果新路径长于当前路径
       但则仍然替换当前路径

上述变换方法就是将k和m对应的两个城市在路径序列中交换位置,称为2-opt映射

       基于退火遗传算法的网络信息过滤系统研究; 《计算机工程与设计》；2009(2)

       基于模拟退火算法的城市公交线路铺设分析; 《交通科技与经济》；2010(5)

货郎担问题
       即也叫旅行商问题, 是数学领域中著名问题之一其一般提法为：假设有一个旅行商人要拜访n个城市
       他必须选择所要走的路径
       路经的限制是每个城市只能拜访一次
       而且最后要回到原来出发的城市路径的选择目标是要求得的路径路程为所有路径之中的最小值如图1所示
       显然左边的路程要小于右边的路程