算法设计与分析 课件 7.7-回溯法 - 典型应用 - 排列树实现 - 旅行售货员问题.pptx

算法设计与分析

回溯法—旅行售货员问题

国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使得总的路程（或总旅费）最小。

排列树算法框架

voidBackTrack(intt)

{

if(tn)

Output(x);

else

for(inti=t;i=n;i++)

{

swap(x[t],x[i]);

if(Constraint(t)Bound(t))

BackTrack(t+1);

swap(x[t],x[i]);

}

}

在调用BackTrack(1)进行回溯有哪些信誉好的足球投注网站前，先将变量数组x初始化为单位排列(1,2,…,n)。

TSP问题

解空间树：排列树

1defBacktrack(i):

2globalbestc,cc

3ifi==n-1:#递归出口

4ifa[x[i-1]][x[i]]!=NO_EDGEanda[x[i]][x[0]]!=NO_EDGE\

5and(cc+a[x[i-1]][x[i]]+a[x[i]][x[0]]bestcorbestc==0):#约束条件

6bestc=cc+a[x[i-1]][x[i]]+a[x[i]][x[0]]#更新最小花费

7forjinrange(n):

8bestx[j]=x[j]

9else:

10forjinrange(i,n):

11#剪枝函数，判断是否存在通路，且增加新路费后总花费是否低于当前已获得的最小花费

12ifa[x[i-1]][x[j]]!=NO_EDGEand(cc+a[x[i-1]][x[j]]bestcorbestc==0):

13x[i],x[j]=x[j],x[i]

14cc+=a[x[i-1]][x[i]]

15Backtrack(i+1)

16cc-=a[x[i-1]][x[i]]

17x[i],x[j]=x[j],x[i]

剪枝函数？

达到叶子结点的处理？

TSP问题

（1）

（2）

（3）

（4）

（5）

（6）

思政：生活和科技背后的算法

送外卖

基因变异时序

太空行星观测

电路板钻孔

学以致用，创造属于自己的价值

测试

选择题：

旅行售货员问题的解空间树的形式是（）

A：子集树

B：排列树