旅行售货员问题问题描述:某售货员要到若干城市去推销商品,一直各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短该问题是一个NP完全问题,有(n-1)!条可选路线最优解(1,3,2,4,1),最优值25问题具体描述:某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用(权)为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。https://wkretype.bdimg.com/retype/zoom/ae9a5b75f46527d3240ce072?pn=1&x=0&y=0&raww=489&rawh=175&o=png_6_0_0_135_635_550_196_892.979_1262.879&type=pic&aimh=171.77914110429447&md5sum=4ced18926fc1df50fb21611e730b7292&sign=9f67dccda7&zoom=&png=0-6122&jpg=0-0算法描述:旅行售货员问题的解空间是一棵排列树x=[123⋯..n]——>相应的排列树由x[1:n]的所有排列构成①在递归算法Backtrack中②当i=n时,当前扩展结点是排列树的叶节点的父结点③此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边⋯⋯⋯算法:templatevoidTraveling::Backtrack(inti){if(i==n){if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]