算法笔记回溯法旅行员售货问题和圆排列问题文档格式.docx
- 文档编号:4644313
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:10
- 大小:92.63KB
算法笔记回溯法旅行员售货问题和圆排列问题文档格式.docx
《算法笔记回溯法旅行员售货问题和圆排列问题文档格式.docx》由会员分享,可在线阅读,更多相关《算法笔记回溯法旅行员售货问题和圆排列问题文档格式.docx(10页珍藏版)》请在冰点文库上搜索。
=
4;
//图的顶点数
9.
10.template<
class
Type>
11.class
Traveling
12.{
13.
template<
14.
friend
Type
TSP(Type
**a,
n);
15.
private:
16.
void
Backtrack(int
i);
17.
n,
//
图G的顶点数
18.
*x,
当前解
19.
*bestx;
当前最优解
20.
图G的领接矩阵
21.
cc,
当前费用
22.
bestc;
当前最优值
23.
NoEdge;
无边标记
24.
};
25.
26.template
27.inline
Swap(Type
&
a,
b);
28.
29.template<
30.Type
31.
32.int
main()
33.{
34.
cout<
图的顶点个数
n="
N<
endl;
35.
36.
**a=new
int*[N+1];
37.
for(int
i=0;
i<
=N;
i++)
38.
{
39.
a[i]=new
int[N+1];
40.
}
41.
42.
图的邻接矩阵为:
43.
44.
i=1;
45.
46.
j=1;
j<
j++)
47.
48.
fin>
>
a[i][j];
49.
a[i][j]<
;
50.
51.
52.
53.
最短回路的长为:
TSP(a,N)<
54.
55.
56.
57.
delete
[]a[i];
58.
59.
[]a;
60.
61.
a=0;
62.
return
0;
63.}
64.
65.template<
66.void
Traveling<
:
i)
67.{
68.
if
(i
==
n)
69.
70.
(a[x[n-1]][x[n]]
!
0
a[x[n]][1]
71.
(cc
+
a[x[n-1]][x[n]]
bestc
||
0))
72.
73.
for
(int
j
1;
n;
bestx[j]
x[j];
74.
cc
a[x[n]][1];
75.
76.
77.
else
78.
79.
i;
80.
81.
是否可进入x[j]子树?
82.
(a[x[i-1]][x[j]]
a[x[i-1]][x[i]]
83.
84.
搜索子树
85.
Swap(x[i],
x[j]);
86.
+=
a[x[i-1]][x[i]];
//当前费用累加
87.
Backtrack(i+1);
//排列向右扩展,排列树向下一层扩展
88.
-=
89.
90.
91.
92.
93.}
94.
95.template<
96.Type
97.{
98.
Y;
99.
Y.n=n;
100.
Y.x=new
int[n+1];
101.
Y.bestx=new
102.
103.
=n;
104.
105.
Y.x[i]=i;
106.
107.
108.
Y.a=a;
109.
Y.cc=0;
110.
Y.bestc=0;
111.
112.
Y.NoEdge=0;
113.
Y.Backtrack
(2);
114.
115.
最短回路为:
116.
117.
118.
Y.bestx[i]<
-->
119.
120.
Y.bestx[1]<
121.
122.
[]
Y.x;
123.
Y.x=0;
124.
Y.bestx;
125.
126.
Y.bestx=0;
127.
Y.bestc;
128.}
129.
130.template
131.inline
b)
132.{
133.
temp=a;
134.
a=b;
135.
b=temp;
136.}
算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!
)次,每次更新bestx需计算时间O(n),从而整个算法的计算时间复杂性为O(n!
)。
程序运行结果如图:
2、圆排列问题
给定n个大小不等的圆c1,c2,…,cn,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。
圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。
例如,当n=3,且所给的3个圆的半径分别为1,1,2时,这3个圆的最小长度的圆排列如图所示。
其最小长度为。
圆排列问题的解空间是一棵排列树。
按照回溯法搜索排列树的算法框架,设开始时a=[r1,r2,……rn]是所给的n个元的半径,则相应的排列树由a[1:
解圆排列问题的回溯算法中,CirclePerm(n,a)返回找到的最小的圆排列长度。
初始时,数组a是输入的n个圆的半径,计算结束后返回相应于最优解的圆排列。
center计算圆在当前圆排列中的横坐标,由x^2=sqrt((r1+r2)^2-(r1-r2)^2)推导出x=2*sqrt(r1*r2)。
Compoute计算当前圆排列的长度。
变量min记录当前最小圆排列长度。
数组r表示当前圆排列。
数组x则记录当前圆排列中各圆的圆心横坐标。
在递归算法Backtrack中,当i>
n时,算法搜索至叶节点,得到新的圆排列方案。
此时算法调用Compute计算当前圆排列的长度,适时更新当前最优值。
n时,当前扩展节点位于排列树的i-1层。
此时算法选择下一个要排列的圆,并计算相应的下界函数。
算法具体代码如下:
1.//圆排列问题
cmath>
7.float
CirclePerm(int
n,float
*a);
8.
9.template
10.inline
11.
12.int
13.{
float
*a
new
float[4];
a[1]
1,a[2]
1,a[3]
2;
圆排列中各圆的半径分别为:
a[i]<
最小圆排列长度为:
CirclePerm(3,a)<
25.}
26.
27.class
Circle
28.{
29.
CirclePerm(int,float
*);
30.
Center(int
t);
//计算当前所选择的圆在当前圆排列中圆心的横坐标
32.
Compute();
//计算当前圆排列的长度
33.
min,
//当前最优值
//当前圆排列圆心横坐标
*r;
//当前圆排列
//圆排列中圆的个数
39.};
41.//
计算当前所选择圆的圆心横坐标
42.float
Circle:
t)
43.{
temp=0;
t;
//由x^2
sqrt((r1+r2)^2-(r1-r2)^2)推导而来
valuex=x[j]+2.0*sqrt(r[t]*r[j]);
(valuex>
temp)
temp=valuex;
temp;
55.}
57.//
计算当前圆排列的长度
58.void
Compute(void)
59.{
low=0,high=0;
63.
(x[i]-r[i]<
low)
65.
low=x[i]-r[i];
66.
67.
(x[i]+r[i]>
high)
high=x[i]+r[i];
(high-low<
min)
min=high-low;
77.}
79.void
80.{
(t>
Swap(r[t],
r[j]);
centerx=Center(t);
(centerx+r[t]+r[1]<
min)//下界约束
93.
x[t]=centerx;
Backtrack(t+1);
95.
96.
97.
99.}
101.float
*a)
102.{
X;
X.n
X.r
a;
X.min
100000;
*x
float[n+1];
X.x
x;
X.Backtrack
(1);
[]x;
X.min;
112.}
114.template
115.inline
116.{
120.}
如果不考虑计算当前圆排列中各圆的圆心横坐标和计算当前圆排列长度所需的计算时间按,则Backtrack需要O(n!
)计算时间。
由于算法Backtrack在最坏情况下需要计算O(n!
)次圆排列长度,每次计算需要O(n)计算时间,从而整个算法的计算时间复杂性为O((n+1)!
)
上述算法尚有许多改进的余地。
例如,像1,2,…,n-1,n和n,n-1,…,2,1这种互为镜像的排列具有相同的圆排列长度,只计算一个就够了,可减少约一半的计算量。
另一方面,如果所给的n个圆中有k个圆有相同的半径,则这k个圆产生的k!
个完全相同的圆排列,只计算一个就够了。
程序运行结果为:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 笔记 回溯 旅行 售货 问题 排列
![提示](https://static.bingdoc.com/images/bang_tan.gif)