采用启发式搜索求解TSP问题步骤为：首先利用最小生成树算法构造无向图 G 的TSP问题的最小生成树；然后从最小生成树开始构造闭合回路(N个城市不重复排列序列)；最后采用枚举的方法,确定从不同最小生成树开始构造的闭合回路中距离最小的一个 ,即最短城市序列 。
由于闭合回路中每个节点的度都为2 ,因此在构造闭合回路时需要处理最小生成树中度不等于2的节点。处理时,第一步是通过删除边的方法降低最小生成树中度大于2的节点的度 ,保证每个节点的度都不大2。删除边时,首先选择与待处理节点(度大于2的节点)相连接的节点中度最大的节点,如果被选择节点的度大于2 ,则删除这两节点之间的边,降低这两节点的度。否则,选择与待处理节点相连接的节点中权值大的节点,删除这两节点之间的边 ,降低这两节点的度 。第二步是通过连接的方法 , 连接最小生成树中度小于2 的节点 , 路 。连接时为了保证所有节点在同一个连通分量中 ,首先标记各连通分量 ,然后选择不同连通分量中度小于 2 的节点并且两点之间权值小的点进行连接 ,从而构成一个大的连通分量 ,最后连接同一个连通分量中仅有的两个度为 1 的节点 , 从而构成一个闭合回路 。
2021-03-20 12:49:09
3KB
1
a*启发式搜索算法的matlab仿真程序 a*启发式搜索算法的matlab仿真程序 a*启发式搜索算法的matlab仿真程序 a*启发式搜索算法的matlab仿真程序
2021-03-20 11:07:33
21KB
1
覆盖路径规划是割草机的重要问题之一，这给我们的生活带来了极大的便利。 本文采用分层划分策略来完成机器人的环境建模，并采用双重启发式优化算法来规划最优覆盖路径。 蚁群优化（ACO）用于上层的全局路径规划，禁忌搜索（TS）用于下层的局部覆盖范围规划。 最后进行了仿真实验，结果表明该方法获得了满意的覆盖路径规划。
2021-02-26 16:07:04
187KB
1