0031算法笔记——【回溯法】旅行员售货问题和圆排列问题概论.docx

?1、旅行员售货问题 ? ??问题描述 ? ???某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。 ? ??问题分析 ? ? ?旅行售货员问题的解空间是一棵排列树。对于排列树的回溯法与生成1,2,……n的所有排列的递归算法Perm类似。开始时x=[1,2,……n],则相应的排列树有x[1:n]的所有排列构成。 ? ? ?在递归算法Backtrack中，当i=n时，当前扩展节点是排列树的叶节点的父节点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在，则找到一条旅行员售货回路。此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回流的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解bestx。 ? ? ?当in时，当前扩展节点位于排列树的第i-1层。图G中存在从顶点x[i-1]到顶点x[i]的边时，x[1:i]构成图G的一条路径，且当x[1:i]的费用小于当前最优值时算法进入树的第i层，否则将剪去相应的子树。 ? ? ?算法具体代码如下： [cpp]?view plain?copy 1. //5d9?旅行员售货问题?回溯法求解?? 2. #include?stdafx.h?? 3. #include?iostream?? 4. #include?fstream??? 5. using?namespace?std;?? 6. ?? 7. ifstream?fin(5d9.txt);??? 8. const?int?N?=?4;//图的顶点数???? 9. ?? 10. templateclass?Type?? 11. class?Traveling?? 12. {?? 13. ????templateclass?Type?? 14. ????friend?Type?TSP(Type?**a,?int?n);?? 15. ????private:?? 16. ????????void?Backtrack(int?i);?? 17. ????????int?n,???????????//?图G的顶点数?? 18. ????????????*x,??????????//?当前解?? 19. ????????????*bestx;??????//?当前最优解?? 20. ????????????Type?**a,????//?图G的领接矩阵?? 21. ????????????cc,??????????//?当前费用?? 22. ????????????bestc;???????//?当前最优值?? 23. ????????????int?NoEdge;??//?无边标记?? 24. ?};??? 25. ?? 26. template?class?Type?? 27. inline?void?Swap(Type?a,?Type?b);?? 28. ?? 29. templateclass?Type?? 30. Type?TSP(Type?**a,?int?n);?? 31. ?? 32. int?main()?? 33. {?? 34. ????cout图的顶点个数?n=Nendl;?? 35. ?? 36. ????int?**a=new?int*[N+1];?? 37. ????for(int?i=0;i=N;i++)?? 38. ????{?? 39. ????????a[i]=new?int[N+1];?? 40. ????}?? 41. ?? 42. ????cout图的邻接矩阵为:endl;?? 43. ?? 44. ????for(int?i=1;i=N;i++)?? 45. ????{?? 46. ????????for(int?j=1;j=N;j++)?? 47. ????????{?? 48. ????????????fina[i][j];?? 49. ????????????couta[i][j]?;?? 50. ????????}?? 51. ????????coutendl;?? 52. ????}?? 53. ????cout最短回路的长为：TSP(a,N)endl;?? 54. ?? 55. ????for(int?i=0;i=N;i++)?? 56. ????{?? 57. ????????delete?[]a[i];?? 58. ????}?? 59. ????delete?[]a;?? 60. ?? 61. ????a=0;?? 62. ????return?0;?? 63. }?? 64. ?? 65. te