1.问题描述
问题描述
给定n个大小不等的圆 C1,C2,C3,...Cn, 现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排序中找出最小长度的圆排序。`
问题分析------举例
例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这三个圆有两种可能：
显然第二种情况的长度要小于第一种情况下的长度
2. 算法分析
回溯法最重要的就是求出界限函数，按问题性质，画出子集树或者排列树
在圆排列问题中，它的解空间是一棵排列树。设开始时数组a是所给n个圆的半径，则相应排列树由 a[1:n] 的所有排列构成，如下:
使用回溯遍历所有情况，在满足下界情况（即当不满足下界条件时，要剪枝），且遍历到叶子结点时，计算当前情况的圆排列长度，并更新当前最优值。
3.算法模型
数组r[ ] -起始表示是输入的n个圆的半径 ；计算结束后返回的数组a是相应于最优解的圆排列。
数组x[ ] -则记录当前圆排列中各圆的圆心横坐标。
backtrack(t) -回溯算法，t 表示选择第t个圆，当 t=N 时返回找到的最小的圆排列长度。
center(t) -计算圆在当前圆排列中的横坐标
compout() -计算当前圆排列的长度。
变量minlen -记录当前最小圆排列长度。
一一解释三个函数 :
center(t) 函数
--计算第 t 个圆圆心横坐标。由 例1.png易知d[k]^2= sqrt((r[k]+r[k-1])2-(r[k]-r[k-1])2)，推导出d[k] = 2sqrt(r[k] r[k-1]) 从而得x = 2*sqrt(r1*r2)。如图例2.png所示，在计算第三个圆 R[3] 的圆心横坐标时，不能确定是 R[1] 与它相切，还是 R[2] 与它相切，故求解第 t 个圆的圆心坐标的思想是遍历在t之前的所有圆，并计算当每一个圆与 R[t] 相切时的圆心坐标，最大值即为 R[t] 实际的圆心坐标
(伪码)
def center(t):
temp = 0
for i in range(1, t):
xvalue = x[i] + 2.0 * math.sqrt(r[t] * r[i]) #temp暂时存储最大值即第 t 个圆可能圆心坐标
if xvalue > temp:
temp = xvalue
return temp
compute() 函数
--计算当前圆排列长度。用变量lenmin记录当前最小圆排列长度；数组 r[] 存储所有圆的半径。数组 x[] 则记录当前圆排列中各圆的圆心横坐标。用 low 和 high 指针分别指向圆排列的最左端和最右端，如例1.png 所示，bestr[] 数组记录当前排列方式(即排列树的一条路径)。
def compute():
low, high = 0, 0
for i in range(1, N):
if x[i] - r[i] < low:
low = x[i] - r[i]
if x[i] + r[i] > high:
high = x[i] + r[i]
# 更新并记录
if high - low < minlen:
minlen = high - low #用变量lenmin记录当前最小圆排列长度
for i in range(1, N): #bestr[] 数组记录当前排列方式(即排列树的一条路径)
bestr[i] = r[i]
backtrack(t) 函数
--当t=n时，表示n个圆选择完毕，利用compute()函数得到最小圆排列长度，并保存此时的圆序列；
当t<n时，在r[t+1],r[t+2] .. r[n] 中选择第t个圆r[j]，swap r[j],r[t]，则此时的r[0]到r[t]为第t个圆为r[j]的圆排序；
下一步，对其进行是否符合剪枝条件的判断，若符合则舍去，并回溯到上一层，即恢复现场，swap r[j],r[t] ；若不符合，则，计算第t个圆的圆心坐标，递归选择下一个圆。
剪枝条件：r[0]到r[t]的圆心距加r[0],r[t]的半径要小于当前最小值
如排列树.png为例，当在第一棵树在第一层搜索第二层结点时即backtrack(2)时，可选择的点为a2,a3;选择a2为第二层结点时，判断a1a2的圆心距+a1的半径+a2的半径是否小于minlen，若小于则递归选择第三层；若不符合退回第一层，选择a3,以此类推。
def backtrack(t):
if t == N:
compute()
else:
# r[t]-r[N]为未被选择的圆
for j in range(t, N):
# 将第j个圆选入排序中
r[t], r[j] = r[j], r[t]
if center(t) + r[t] + r[1] < minlen:
x[t] = centerx
backtrack(t + 1)
# 恢复现场
r[t], r[j] = r[j], r[t]
4.代码实现
# 回溯法
import math
N = 4
# N = int(input('n='))
minlen = 999
bestr = [0 for i in range(0, N)]
r = [0 for i in range(0, N)]
x = [0 for i in range(0, N)]
r[1], r[2], r[3] =1,1,2
# for i in range(1, N):
# r[i] = int(input('r='))
# 计算当前所选择圆的圆心横坐标
def center(t):
temp = 0
for i in range(1, t):
xvalue = x[i] + 2.0 * math.sqrt(r[t] * r[i])
if xvalue > temp:
temp = xvalue
return temp
# 计算当前圆排列的长度
# 变量lenmin记录当前最小圆排列长度。
# 数组r存储所有圆的半径。数组x则记录当前圆排列中各圆的圆心横坐标
def compute():
global minlen
low, high = 0, 0
for i in range(1, N):
if x[i] - r[i] < low:
low = x[i] - r[i]
if x[i] + r[i] > high:
high = x[i] + r[i]
# 更新并记录
if high - low < minlen:
minlen = high - low
for i in range(1, N):
bestr[i] = r[i]
# 回溯 选择第t个圆
def backtrack(t):
if t == N:
compute()
else:
# r[t]-r[N]为未被选择的圆
for j in range(t, N):
# 将第j个圆选入排序中
r[t], r[j] = r[j], r[t]
centerx = center(t)
# 剪枝-当末端3个半径逐一递增或递减时不可能为最优解，舍去
if centerx + r[t] + r[1] < minlen:
x[t] = centerx
backtrack(t + 1)
# 恢复现场
r[t], r[j] = r[j], r[t]
backtrack(1)
print('最小圆排列长度为 ' + repr(minlen))
print('最优圆排列的顺序对应半径分别为',end=';')
for i in range(1, N):
print(repr(bestr[i]), end=' ')
4.优化与改进
- 例如，像1,2,…,n-1,n和n,n-1, …,2,1这种互为镜像的排列显然具有相同的圆排列长度，通过算法优化，可减少约一半的计算量。
- 如果所给的n个圆中有k个圆有相同的半径，则这k个圆产生的 k! 个完全相同的圆排列也显然相同。
- 剪枝优化：当后三个圆的半径为递增或者递减时，肯定不是最小长度，剪枝。
代码实现
第一部分
# z-奇数为0 偶数为1
z= (N-1)% 2
# 剪掉一半的子树-偶数则搜索2/N个子树，奇数则搜索2/N+1个子树
for i in range(1,int((N-1)/2)+z+1):
x[1]=0
r[1],r[i]=r[i],r[1]
backtrack(2)
第三部分
def backtrack(t):
if t == N:
compute()
else:
# r[t]-r[N]为未被选择的圆
for j in range(t, N):
# 将第j个圆选入排序中
r[t], r[j] = r[j], r[t]
# 剪枝优化
if t>4:
if (r[t]>r[t-1] and r[t-1]>r[t-2] )or(r[t]<r[t-1]and r[t-1]<r[t-2]):
return
if center(t) + r[t] + r[1] < minlen:
x[t] = center(t)
backtrack(t + 1)
# 恢复现场
r[t], r[j] = r[j], r[t]
代码优化部分 待续~
5.时间复杂度和空间复杂度
时间复杂度：由回溯法的排列树可知，搜索子结点的时间复杂度是O(n!)次，即全排列的时间复杂度，而Backtrack()函数每次计算需要O(n)计算时间，从而整个算法的计算时间复杂性为O((n+1)!)。
虽然理论上时间复杂度很大，但实际的消耗实际由于增加了剪枝条件，会比O((n+1)!)小很多。
空间复杂度：由于r[]数组，x[]数组的大小都为n，故空间复杂度为O(n)
