说明:采用启发式搜索求解TSP问题步骤为:首先利用最小生成树算法构造无向图 G 的TSP问题的最小生成树;然后从最小生成树开始构造闭合回路(N个城市不重复排列序列);最后采用枚举的方法,确定从不同最小生成树开始构造的闭合回路中距离最小的一个 ,即最短城市序列 。
由于闭合回路中每个节点的度都为2 ,因此在构造闭合回路时需要处理最小生成树中度不等于2的节点。处理时,第一步是通过删除边的方法降低最小生成树中度大于2的节点的度 ,保证每个节点的度都不大2。删除边时,首先选择与待处理节点(度大于2的节点)
<abc2779845> 在 上传 | 大小:3072