图论高手请进

来源：百度知道 编辑：UC知道 时间：2024/06/17 23:15:27
怎样求最优旅行商路线（完全图情况下）？有没有算法或相关的软件

你这个问题和最优哈密顿回路问题一样的，属于NPC问题，目前还没有有效算法，不过有 一个近似算法，
步骤如下：
1：有任意选择的节点开始，指出与该点最靠近（即权最小的点），形成有一条边的初始路
2：设x表示最新加到这条路上的节点，从不在路上的所有节点中选一个与x最靠近的节点，并把相应的边加到这条路上，重复此歩，直到所有节点包含在路上
3：将连接起点与最后加入的节点之间的边加入到这条路上，就得到问题的近似解