文件名称：采用启发式搜索求解TSP问题（C语言）
文件大小：3KB
文件格式：TXT
更新时间：2023-07-21 07:00:21
人工智能 C语言 启发式搜索 TSP
采用启发式搜索求解TSP问题步骤为：首先利用最小生成树算法构造无向图 G 的TSP问题的最小生成树；然后从最小生成树开始构造闭合回路(N个城市不重复排列序列)；最后采用枚举的方法,确定从不同最小生成树开始构造的闭合回路中距离最小的一个 ,即最短城市序列 。 由于闭合回路中每个节点的度都为2 ,因此在构造闭合回路时需要处理最小生成树中度不等于2的节点。处理时,第一步是通过删除边的方法降低最小生成树中度大于2的节点的度 ,保证每个节点的度都不大2。删除边时,首先选择与待处理节点(度大于2的节点)相连接的节点中度最大的节点,如果被选择节点的度大于2 ,则删除这两节点之间的边,降低这两节点的度。否则,选择与待处理节点相连接的节点中权值大的节点,删除这两节点之间的边 ,降低这两节点的度 。第二步是通过连接的方法 , 连接最小生成树中度小于2 的节点 , 路 。连接时为了保证所有节点在同一个连通分量中 ,首先标记各连通分量 ,然后选择不同连通分量中度小于 2 的节点并且两点之间权值小的点进行连接 ,从而构成一个大的连通分量 ,最后连接同一个连通分量中仅有的两个度为 1 的节点 , 从而构成一个闭合回路 。