士兵站队问题

第二章：递归与分治策略---士兵站队问题问题描述：•在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一列。问题分析：•士兵有多种移动方式：通过适当的移动顺序和移动路线可以使得同一时刻不会有两名士兵站在同一点•题目要求最佳移动方式（即求移动的最少步数）：转化为求士兵站立的“最终位置”，即如何取“最终位置”使得士兵移动的步数最少（最优）。解题思路：Y轴方向上的考虑：设目标坐标为M，即n个士兵最终需要移动到的Y轴的坐标值为M，n个士兵初始位置的Y轴坐标分别为：Y0，Y1，Y2…Yn-1则最优步数S=|Y0-M|+|Y1-M|+|Y2-M|+…+|Yn-1-M|。从最上和最下的两个士兵开始递推，可得M取中间点的值使得S为最少（最优），即处于中间位置的士兵的Y轴坐标值就是“最终位置”的Y轴坐标。解决办法：对所有的Y轴坐标进行排序（O（nlogn））或者进行线性时间选择（O（n）），然后取“中间”点的Y轴坐标值作为最佳位置M的值，最后通过公式求出Y轴方向上移动的最优步数。解题思路：X轴方向上的考虑首先需要对所有士兵的X轴坐标值进行排序；然后，按从左至右的顺序依次移动到每个士兵所对应的“最终位置”，所移动的步数总和就是X轴方向上需要移动的步数。例，最左的士兵移动到“最终位置”的最左那位，第二个士兵移动到“最终位置”的第二位则总的步数为：士兵1移动步数+士兵2移动步数+……+士兵n移动步数。如何确定X轴方向上的最佳的“最终位置”？n个士兵他们相应的X轴坐标为：X0，X1，X2…Xn-1设“最终位置”的X轴坐标值为：k，k+1，k+2…k+（n-1）则最优步数：S=|X0-k|+|X1-(k+1)|+|X2-(k+2)|+…+|Xn-1-(k+(n-1))|经过变形：S=|X0-k|+|(X1-1)-k|+|(X2-2)-k|+…+|(Xn-1-(n-1))-k|•X轴方向公式的形式与Y轴方向上的考虑一样，同样是n个已知数分别减去一个待定数后取绝对值，然后求和。因此还是采用取中位数的办法求得k值，最后算出最优解。算法实现：1、用快速排序对士兵当前位置的x轴坐标进行排序2、分别找出x轴坐标和y轴坐标的第（n+1）/2小元素，即中位数3、分别算士兵当前位置的x轴和y轴坐标值到各自中位数的绝对差之和，最后把这两个值相加即为所求的最少步数。•#includeiostream•#includemath.h•#includestdlib.h•usingnamespacestd;•voidSwap(int&a,int&b)//交换函数•{•inttemp;//定义一个交换的临时变量•temp=a;•a=b;•b=temp;•}•intpartition(int*a,intlow,inthigh)//确定一个基准元素以对数组元素进行划分•{•intkey=a[low];//key初始化为a的首元素•while(lowhigh)•{•while(lowhigh&&a[high]=key)high--;•a[low]=a[high];•while(lowhigh&&a[low]=key)low++;•a[high]=a[low];•}•a[low]=key;•returnlow;•}•//在a[low:high]中随机选一个元素作为基准，以期划分较对称•intRandomizedPartition(int*a,intlow,inthigh){•inti=rand()%(high-low+1)+low;//rand()函数可以生成一个随机数，•Swap(a[i],a[low]);//将随机挑选的元素与数组首元素交换•returnpartition(a,low,high);}•intRandomizedSelect(int*a,intp,intr,intk)//找数组中a[p:r]的第k小元素{•if(p==r)returna[p];•inti=RandomizedPartition(a,p,r);//将数组a[p:r]划分成两个子数组a[p:i]、a[i+1:r]•intj=i-p+1;//计算子数组a[p:i]中元素个数j•if(j=k)//如果j=k,则第k小元素落在子数组a[p:i]中,否则落在a[i+1:r]中•returnRandomizedSelect(a,p,i,k);•else•returnRandomizedSelect(a,i+1,r,k-j);}•voidRandomizedQsort(int*a,intlow,inthigh)//随机化的快速排序函数：{•intkey;•if(lowhigh){•key=RandomizedPartition(a,low,high);//产生随机的划分基准•RandomizedQsort(a,low,key-1);//对左半段排序•RandomizedQsort(a,key+1,high);//对右半段排序•}}•intmain()•{•intx[10000],y[10000],n,xkey,ykey,x1[10000],sum;•cout请输入士兵数n(1~10000):endl;cinn;•cout请输入这n个士兵的初始位置坐标：endl;•while(1)•{•sum=0;•for(inti=0;in;i++)•cinx[i]y[i];//输入士兵位置的xy坐标分别存入数组x[],y[]中•RandomizedQsort(x,0,n-1);//调用排序函数，对士兵初始位置的x坐标进行排序•for(intj=0;jn;j++)//计算最终位置的x的坐标值•x1[j]=x[j]-j;•ykey=RandomizedSelect(y,0,n-1,(n+1)/2);//y的第(n+1)/2小元素，即中位数•xkey=RandomizedSelect(x1,0,n-1,(n+1)/2);//x的第(n+1)/2小元素，即中位数•for(intk=0;kn;k++)•{•sum+=abs(y[k]-ykey);//要移到最终位置y方向所移动的总步数•sum+=abs(x1[k]-xkey);//要移到最终位置x方向所移动的总步数•}•cout使士兵排成一行需要的最少移动步数：sumendl;•}•return0;•}运行结果：复杂度分析：•时间复杂度跟所选用的排序方法等有关，这里用的是随机选择策略的快速排序算法，虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。复杂度分析：•在选择中位数时算法RandomizedSelect，在最坏情况下，算法RandomizedSelect需要O（n^2）计算时间，平均情况下，由于用到随机快速排序算法中使用了一个随机数产生器rand（），它能随机的产生low和high之间的一个随机整数，即RandomizedPartition产生的划分基准是随机的，在这个条件下，它可以在O（n）平均时间内完成任务。•综上：该算法完成士兵站队问题的时间复杂度为：O(nlogn)+2*O（n）=O(nlogn)