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

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

旅行商问题求解模型和方法具有广泛的理论和应用价值,如何简化问题是提高问题求解效率的有效手段之一.通过对问题优化解集及优化解之间关系和性质分析,建立了高概率确定问题全局最优解中部分边的蒙特卡罗模型.利用该模型建立的算法可减少问题求解需进一步确定的边数量,也可用于对问题初始边集进行裁减,从而降低了问题的求解难度,提高各类基于边求解算法的计算效率,具有广泛的普适性.本文提出的模型可泛用于各种规模旅行商问题的求解中.

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.