士兵站队问题ppt课件

第二章：递归与分治策略第二章：递归与分治策略第二章：递归与分治策略第二章：递归与分治策略 -士兵站队问题士兵站队问题士兵站队问题士兵站队问题第二章：递归与分治策略 -1问题描述：问题描述：问题描述：问题描述：在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一列。问题描述：在一个划分成网格的操场上，n个士兵散乱地2问题分析：问题分析：问题分析：问题分析：士兵有多种移动方式：通过适当的移动顺序和移动路线可以使得同一时刻不会有两名士兵站在同一点题目要求最佳移动方式（即求移动的最少步数）：转化为求士兵站立的“最终位置”，即如何取“最终位置”使得士兵移动的步数最少（最优）。问题分析：士兵有多种移动方式：通过适当的移动顺序和移动路线可3解题思路：解题思路：解题思路：解题思路：Y Y轴方向上的考虑：轴方向上的考虑：l设目标坐标为M，即n个士兵最终需要移动到的Y轴的坐标值为M，n个士兵初始位置的Y轴坐标分别为：Y0，Y1，Y2Yn-1 则最优步数S=|Y0-M|+|Y1-M|+|Y2-M|+|Yn-1-M|。l从最上和最下的两个士兵开始递推，可得M取中间点的值使得S为最少（最优），即处于中间位置的士兵的Y轴坐标值就是“最终位置”的Y轴坐标。l解决办法解决办法：对所有的Y轴坐标进行排序（O（nlogn）或者进行线性时间选择（O（n），然后取“中间”点的Y轴坐标值作为最佳位置M的值，最后通过公式求出Y轴方向上移动的最优步数。解题思路：Y轴方向上的考虑：4解题思路：解题思路：解题思路：解题思路：X X轴方向上的考虑轴方向上的考虑l首先需要对所有士兵的X轴坐标值进行排序；然后，按从左至右的顺序依次移动到每个士兵所对应的“最终位置”，所移动的步数总和就是X轴方向上需要移动的步数。例，最左的士兵移动到“最终位置”的最左那位，第二个士兵移动到“最终位置”的第二位则总的步数为：士兵1移动步数+士兵2移动步数+士兵n移动步数。如何确定如何确定X X轴方向上的最佳的轴方向上的最佳的“最终位置最终位置”？ln个士兵他们相应的X轴坐标为：X0，X1，X2Xn-1 设“最终位置”的X轴坐标值为：k，k+1，k+2k+（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轴方向上的考虑5 X轴方向公式的形式与Y轴方向上的考虑一样，同样是n个已知数分别减去一个待定数后取绝对值，然后求和。因此还是采用取中位数的办法求得k值，最后算出最优解。士兵站队问题ppt课件6士兵站队问题ppt课件7算法实现：算法实现：算法实现：算法实现：1、用快速排序对士兵当前位置的x轴坐标进行排序2、分别找出x轴坐标和y轴坐标的第（n+1）/2小元素，即中位数3、分别算士兵当前位置的x轴和y轴坐标值到各自中位数的绝对差之和，最后把这两个值相加即为所求的最少步数。算法实现：1、用快速排序对士兵当前位置的x轴坐标进行排序8#include#include#include using namespace std;void Swap(int&a,int&b)/交换函数交换函数int temp;/定义一个交换的临时变量定义一个交换的临时变量temp=a;a=b;b=temp;int partition(int*a,int low,int high)/确定一个基准元素以对数组元素进行划分确定一个基准元素以对数组元素进行划分 int key=alow;/key初始化为初始化为a的首元素的首元素 while(lowhigh)while(low=key)high-;alow=ahigh;while(lowhigh&alow=key)low+;ahigh=alow;alow=key;return low;#include 9/在在alow:high中随机选一个元素作为基准，以期划分较对称中随机选一个元素作为基准，以期划分较对称int RandomizedPartition(int*a,int low,int high)int i=rand()%(high-low+1)+low;/rand()函数可以生成一个随机数，函数可以生成一个随机数，Swap(ai,alow);/将随机挑选的元素与数组首元素交换将随机挑选的元素与数组首元素交换 return partition(a,low,high);int RandomizedSelect(int*a,int p,int r,int k)/找数组中找数组中ap:r的第的第k小元素小元素 if(p=r)return ap;int i=RandomizedPartition(a,p,r);/将数组将数组ap:r划分成两个子数组划分成两个子数组ap:i、ai+1:r int j=i-p+1;/计算子数组计算子数组ap:i中元素个数中元素个数j if(j=k)/如果如果j=k,则第则第k小元素落在子数组小元素落在子数组ap:i中中,否则落在否则落在ai+1:r中中return RandomizedSelect(a,p,i,k);elsereturn RandomizedSelect(a,i+1,r,k-j);void RandomizedQsort(int*a,int low,int high)/随机化的快速排序函数随机化的快速排序函数：int key;if(lowhigh)key=RandomizedPartition(a,low,high);/产生随机的划分基准产生随机的划分基准RandomizedQsort(a,low,key-1);/对左半段排序对左半段排序RandomizedQsort(a,key+1,high);/对右半段排序对右半段排序 /在alow:high中随机选一个元素作为基准，以期划10int main()int x10000,y10000,n,xkey,ykey,x110000,sum;cout请输入士兵数n(110000):n;cout请输入这n个士兵的初始位置坐标：endl;while(1)sum=0;for(int i=0;i xiyi;/输入士兵位置的输入士兵位置的xy坐标分别存入数组坐标分别存入数组x,y中中 RandomizedQsort(x,0,n-1);/调用排序函数，对士兵初始位置的调用排序函数，对士兵初始位置的x坐标进行排序坐标进行排序 for(int j=0;j n;j+)/计算最终位置的计算最终位置的x的坐标值的坐标值 x1j=xj-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(int k=0;k n;k+)sum+=abs(yk-ykey);/要移到最终位置要移到最终位置y方向所移动的总步数方向所移动的总步数 sum+=abs(x1k-xkey);/要移到最终位置要移到最终位置x方向所移动的总步数方向所移动的总步数 cout使士兵排成一行需要的最少移动步数：sumendl;return 0;int main()11运行结果：运行结果：运行结果：运行结果：运行结果：12复杂度分析：复杂度分析：复杂度分析：复杂度分析：时间复杂度跟所选用的排序方法等有关，这里用的是随机选择策略的快速排序算法，虽然最坏情况仍然是O(n2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。复杂度分析：13复杂度分析：复杂度分析：复杂度分析：复杂度分析：在选择中位数时算法RandomizedSelect，在最坏情况下，算法RandomizedSelect 需要O（n2）计算时间，平均情况下，由于用到随机快速排序算法中使用了一个随机数产生器rand（），它能随机的产生low和high之间的一个随机整数，即RandomizedPartition产生的划分基准是随机的，在这个条件下，它可以在O（n）平均时间内完成任务。综上：该算法完成士兵站队问题的时间复杂度为：O(nlogn)+2*O（n）=O(nlogn)复杂度分析：在选择中位数时算法RandomizedSelec14谢谢！15