分治算法

转自：http://blog.csdn.net/com_stu_zhang/article/details/7233761

一、基本概念

   在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

    任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

---

二、基本思想及策略

   分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

   分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

   如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

---

三、分治法适用的情况

    分治法所能解决的问题一般具有以下几个特征：

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

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

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

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

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

---

四、分治法的基本步骤

分治法在每一层递归上都有三个步骤：

    step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

    step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

    step3 合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下：

    Divide-and-Conquer(P)

    1. if |P|≤n0

    2. then return(ADHOC(P))

    3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk

    4. for i←1 to k

    5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi

    6. T ← MERGE(y1,y2,...,yk) △ 合并子问题

    7. return(T)

    其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。

---

五、分治法的复杂性分析

    一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：

 T（n）= k T(n/m)+f(n)

    通过迭代法求得方程的解：

    递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当                  mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。 

---

六、可使用分治法求解的一些经典问题

 

 （1）二分搜索

（2）大整数乘法

 （3）Strassen矩阵乘法

（4）棋盘覆盖

（5）合并排序

（6）快速排序

（7）线性时间选择

（8）最接近点对问题

（9）循环赛日程表

（10）汉诺塔

---

七、依据分治法设计程序时的思维过程

 

    实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。

1、一定是先找到最小问题规模时的求解方法

2、然后考虑随着问题规模增大时的求解方法

3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。

 

 

转自：http://www.cnblogs.com/huangxincheng/archive/2012/02/07/2340797.html

一： 思想

     有时候我们处理一个复杂的问题，可能此问题求解步骤非常杂，也可能是数据非常多，导致我们当时很难求出或者无法求出，古语有云：

步步为营，各个击破，这个思想在算法中称为分治思想，就是我们可以将该问题分解成若干个子问题，然后我们逐一解决子问题，最后将子问题

的答案组合成整个问题的答案。

二: 条件

     当然各个思想都有它的使用领域，所以玩这场分治游戏就要遵守它的游戏规则。

       ①   求解问题确实能够分解成若干个规模较小的子问题，并且这些子问题最后能够实现接近或者是O（1）时间求解。

       ②   各个子问题之间不能有依赖关系，并且这些子问题确实能够通过组合得到整个问题的解。

三：步骤

     通过上面对分治的说明，可以看到分治分三步走：

       ①  分解： 将问题分解成若干了小问题。

       ②  求解： O(1)的时间解决该子问题。

       ③  合并： 子问题逐一合并构成整个问题的解。

四：举例

      有n位选手参加羽毛球赛，比赛要进行n-1天，每位选手都要与其他每一个选手比赛一场并且每位选手每天都要比赛一场，请根据比赛要求

   排出选手的比赛日程表。

   思路：首先我们拿到问题要给自己打气，哈哈，因为日常的基本问题都跑不出我们所知道算法思想的范畴，此问题也包括在内。

           当n是8，16，32时，面对这么一个庞大的问题我们可能就崩溃了，因为我们实在无法求出来，此时我们就要想想是否可以分治一下。

           ①  就拿16个选手的比赛安排来说，需要比赛15天。

           ②  分成2个8位选手7天的比赛安排。

           ③  分为4个4位选手3天的比赛安排。

           ④  分为8个2位选手1天的比赛安排。

         相信2位选手1天的比赛安排大家都会吧，如图:

        然后退化到第三步即4位选手3天的比赛安排，如图：

        在图中可以看出:

          第一天：将1，2位和3，4位选手的日程合并。

          第二天，第三天：这两天的比赛安排其实可以发现规律的，整个表格可以划分四格，对角赋值。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Fenzhi
{
    public class Program
    {
        //这里
        static int[,] GameList = new int[8, 8];

        static void Main(string[] args)
        {
            Console.Write("请输入参赛选手的人数：	");

            int person = Convert.ToInt32(Console.ReadLine());

            //参数检查合法性
            if (person % 2 != 0)
            {
                Console.WriteLine("输入的人数必须是2的倍数！");
                return;
            }

            //因为我定了只能容纳8位选手的日程的比赛安排，多的话就会爆掉
            if (person > 8)
            {
                Console.WriteLine("对不起，最多8位选手");
                return;
            }

            //调用分值计算函数
            GameCal(1, person);

            Console.Write("
编号	");

            //最后就是将数组表头
            for (int i = 1; i < person; i++)
            {
                Console.Write("第{0}天	", i);
            }

            //换行
            Console.WriteLine();

            //输出数组内容
            for (int i = 0; i < person; i++)
            {
                for (int j = 0; j < person; j++)
                {
                    Console.Write("{0}	", GameList[i, j]);
                }
                Console.WriteLine();
            }

            Console.ReadLine();
        }

        /// <summary>
/// 分治计算
/// </summary>
/// <param name="index">起始选手编号</param>
/// <param name="num">选手的人数(因为是分治，所以每次砍半)</param>
        static void GameCal(int index, int num)
        {
            //如果人数为2，则说明已经分治到了最简问题
            if (num == 2)
            {
                //参赛选手编号
                GameList[index - 1, 0] = index;

                //对阵选手编号
                GameList[index - 1, 1] = index + 1;

                //参赛选手编号
                GameList[index, 0] = index + 1;

                //对阵选手编号
                GameList[index, 1] = index;
            }
            else
            {
                //折半递归
                GameCal(index, num / 2);

                //折半递归
                GameCal(index + num / 2, num / 2);

                /* 子问题都结束后就要想办法合并，根据发现的规律进行合并 */

                //用于将“左下角”填充到“右上角”
//控制横坐标
                for (int i = index; i < index + num / 2; i++)
                {
                    //控制“纵坐标”
                    for (int j = num / 2; j < num; j++)
                    {
                        //对角赋值
                        GameList[i - 1, j] = GameList[(i - 1) + num / 2, j - num / 2];
                    }
                }

                //用于将“左上角”填充到“右下角”
//控制横坐标
                for (int i = index + num / 2; i < index + num; i++)
                {
                    //控制纵坐标
                    for (int j = num / 2; j < num; j++)
                    {
                        //对角赋值
                        GameList[i - 1, j] = GameList[(i - 1) - num / 2, j - num / 2];
                    }
                }
            }
        }
    }
}