游戏中的算法

分治算法

 

1、分治算法的定义

    分治算法是游戏中比较常用的一种算法，“分治”二字顾名思义，就是“分而治之”的意思，说的通俗一点就是步步为营，各个击破，再来解释分而治之的意思，其实也就是把一个问题（一般来说这个问题都是比较复杂的）分成两个相同或者相似的子问题，再把子问题分成更小的问题，一直这样下去.......直到最后，子问题可以简单地求解，还有一点就是把所有求得的子问题合并就是原问题的解。其实在很多场合下都会使用到分治算法，比如说我们常用的归并排序、快速排序都是很常见的分治思想的体现。

 

2、分治法的解题步骤一般可以分为三步：

1、分解问题：将要解决的问题分开成若干个规模较小且又容易解决的与原问题同类的相互独立子问题。

2、解决问题：将子问题求解。

3、合并：按照原问题的要求，将解决了的子问题合并构成原问题的解。

例如：

最值得求取：

在n个元素中找出最大元素和最小元素。我们可以把这n个元素放在一个数组中，用直接比较法求出。算法如下:

void maxmin1(int A[],int n,int *max,int *min)

{

int i;

*min=*max=A[0];

for(i=0;i <= n;i++)

{

if(A[i]> *max) *max= A[i];

if(A[i] < *min) *min= A[i];

}

}

上面这个算法需比较2(n-1)次。能否找到更好的算法呢?我们用分治策略来讨论。

把n个元素分成两组:

A1={A[1],...,A[int(n/2)]}和A2={A[INT(N/2)+1],...,A[N]}

分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。

例如有下面一组元素:-13，13，9，-5，7，23，0，15。用分治策略比较的算法如下:

void maxmin2(int A[],int i,int j,int *max,int *min)

/*A存放输入的数据，i，j存放数据的范围，初值为0，n-1，*max,*min 存放最大和最小值*/

{

int mid,max1,max2,min1,min2;

if (j==i)

{

最大和最小值为同一个数;

return;

}

if (j-1==i)

{

将两个数直接比较，求得最大和最小值;

return;

}

mid=(i+j)/2;

求i~mid之间的最大最小值分别为max1，min1;

求mid+1~j之间的最大最小值分别为max2，min2;

比较max1和max2，大的就是最大值;

比较min1和min2，小的就是最小值;

}

还有查找为币也可以用分治算法

硬币假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。

 

3、总结分治算法的适用场景 

     1) 该问题的规模缩小到一定的程度就可以容易地解决

      2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

      3) 利用该问题分解出的子问题的解可以合并为该问题的解；

      4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

      

4、分治算法的应用

　　（1）二分搜索

　　（2）大整数乘法

　　（3）Strassen矩阵乘法

　　（4）棋盘覆盖

　　（5）合并排序

　　（6）快速排序

　   （7）循环赛日程表

　　（8）汉诺塔