()的解空间是一个排列树。这样的树可用函数Perm(见程序1-10)搜索,并可生成元素表的所有排列。如果以x=[1,2,.,n]开始,那么通过产生从x2到xn的所有排列,可生成n顶点旅行商问题的解空间。由于Perm产生具有相同前缀的所有排列,因此可以容易地改造Perm,使其不能产生具有不可行前缀(即该前缀没有定义路径)或不可能比当前最优旅行还优的前缀的排列。注意在一个排列空间树中,由任意子树中的叶节点定义的排列有相同的前缀(如图16-5所示)。因此,考察时删除特定的前缀等价于搜索期间不进入相应的子树。旅行商问题的回溯算法可作为类AdjacencyWDigraph(见程序12-1)的一个成员。在其他例子中,有两个成员函数:tSP和TSP。前者是一个保护或私有成员,后者是一个共享成员。(v)返回最少耗费旅行的花费,旅行自身由整型数组v返回。若网络中无旅行,则返回NoEdge。tSP在排列空间树中进行递归回溯搜索,TSP是其一个必要的预处理过程。TSP假定x(用来保存到当前节点的路径的整型数组),bestx(保存目前发现的最优旅行的整型数组),cc(类型为T的变量,保存当前节点的局部旅行的耗费),bestc(类型为T的变量,保存目前最优解的耗费)已被定义为AdjacencyWDigraph中的静态数据成员。TSP见程序16-11。tSP(2)搜索一棵包含x[2:n]的所有排列的树。程序16-11旅行商回溯算法的预处理程序template<classT>TAdjacencyWDigraph<T>::TSP(intv[]){//用回溯算法解决旅行商问题//返回最优旅游路径的耗费,最优路径存入v[1:n]//初始化x=newint[n+1];//x是排列for(inti=1;i<=n;i++)x[i]=i;bestc=NoEdge;bestx=v;//=0;//搜索x[2:n]的各种排列tSP(2);delete[]x;returnbestc;}函数tSP见程序16-12。它的结构与函数Perm相同。当i=n时,处在排列树的叶节点的父节点上,并且需要验证从x[n-1]到x[n]有一条边,从x[n]到起点x[1]也有一条边。若两条边都存在,则发现了一个新旅行。在本例中,需要验证是否该旅行是目前发现的最优旅行。若是,则将旅行和它的耗费分别存入bestx与bestc中。当i<n时,检查当前i-1层节点的孩子节点,并且仅当以下情况出现时,移动到孩子节点之一:1)有从x[i-1]到x[i]的一条边(如果是这样的话,x[1:i]定义了网络中的一条路径);2)路径x[1:i]的耗费小于当前最优解的耗费。保存目前所构造的路径的耗费。每次找到一个更好的旅行时,除了更新bestx的耗费外,tSP需耗时O((n-1)!)。因为需发生O((n-1)!)次更新且每一次更新的耗费为(n)时间,因此更新所需时间为O(n*
旅行商问题c语言 来自淘豆网m.daumloan.com转载请标明出处.
