确定TSP全局最优解部分边的蒙特卡罗模型  

Monte Carlo Algorithm for Fixing Partial Edges Belonging to TSP Global Optimal Solution

作　　者：林冬梅[1] 王东[2] 钟勇[1] 

机构地区：[1]佛山科学技术学院信息与教育技术中心,广东佛山528000 [2]佛山科学技术学院计算机科学与技术系,广东佛山528000

出　　处：《小型微型计算机系统》2010年第4期747-751,共5页Journal of Chinese Computer Systems

基　　金：广东省自然科学基金项目(8452800001000086)资助;中国博士后科学基金项目(20070421015)资助

摘　　要：旅行商问题求解模型和方法具有广泛的理论和应用价值,如何简化问题是提高问题求解效率的有效手段之一.通过对问题优化解集及优化解之间关系和性质分析,建立了高概率确定问题全局最优解中部分边的蒙特卡罗模型.利用该模型建立的算法可减少问题求解需进一步确定的边数量,也可用于对问题初始边集进行裁减,从而降低了问题的求解难度,提高各类基于边求解算法的计算效率,具有广泛的普适性.本文提出的模型可泛用于各种规模旅行商问题的求解中.The model and method of solving traveling salesman problem is of abroad value of theory and application.It is one of efficacious means to improve problem solving efficiency,how to simplify the process of problem solving.By analyzing relationship and character among problem optimal solution sets and among optimal solutions,the Monte Carlo model ascertaining partial edges belonging to problem＇s global optimal solution with high probability is established.The edge number which need be fixed more is cut down utilizing the model,and the initial edge set of problem can be reducing.Consequently,the difficulty solving problem is depressed,and the efficiency is improved.The model is with universal adaptation character.Statistic experimental result has validated correctness of the model.

关 键 词：旅行商问题 全局最优解 蒙特卡罗算法 固定边 缩减规模 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]