您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

什么是分治算法?

时间:2019-04-28 09:47:26  来源:  作者:
分治算法,了解一下?

 

1 概念

分治算法,根据字面意思解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

2 算法策略

分治策略:对于一个规模为 n 的问题,若该问题可以容易地解决(比如说规模 n 较小)则直接解决,否则将其分解为 k 个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。

在平时日常生活中,分治思想也是随处可见的。例如:当我们打牌时,在进行洗牌时,若牌的数目较多,一个人洗不过来,则会将牌进行分堆,单独洗一小堆牌是相对容易的,每一堆牌都洗完之后再放到一起,则完成洗牌过程。

3 使用场景

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

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

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

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

4 基本步骤

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

(1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题。

(2)求解:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题。

(3)合并:将各个子问题的解合并为原问题的解。

分治算法,了解一下?

 

分治思想

5 伪代码

 Divide-and-Conquer(P)
 if |P| ≤ n0
 then return(ADHOC(P))
 将P分解为较小的子问题 P1 ,P2 ,...,Pk
 for i←1 to k
 do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
 T ← MERGE(y1,y2,...,yk) △ 合并子问题
 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 的解。

6 典型案例

6.1 二分查找

二分查找是典型的分治算法的应用。需要注意的是,二分查找的前提是查找的数列是有序的。

算法流程:

(1)选择一个标志 i 将集合分为二个子集合。

(2)判断标志 L(i) 是否能与要查找的值 des 相等,相等则直接返回。

(3)否则判断 L(i) 与 des 的大小。

(4)基于判断的结果决定下步是向左查找还是向右查找。

(5)递归继续上面的步骤。

通过二分查找的流程可以看出,二分查找是将原有序数列划分为左右两个子序列,然后在对两个子序列中的其中一个在进行划分,直至查找成功。

代码实现:

#include<string.h>
#include<stdio.h>
int k;
int binarysearch(int a[],int x,int low,int high)//a表示需要二分的有序数组(升序),x表示需要查找的数字,low,high表示高低位
{
 if(low>high)
 {
 return -1;//没有找到
 }
 int mid=(low+high)/2;
 if(x==a[mid])//找到x
 {
 k=mid;
 return x;
 }
 else if(x>a[mid]) //x在后半部分
 {
 binarysearch(a,x,mid+1,high);//在后半部分继续二分查找
 }
 else//x在前半部分
 {
 binarysearch(a,x,low,mid-1);
 }
}
int mAIn()
{
 int a[10]={1,2,3,4,5,6,7,8,9,10};
 printf("请输入需要查找的正数字:
");
 int x;
 scanf("%d",&x);
 int r=binarysearch(a,x,0,9);
 if(r==-1)
 {
 printf("没有查到
");
 }
 else
 {
 printf("查到了,在数列的第%d个位置上
",k+1);
 }
 return 0;
}

6.2 全排列问题

问题描述:

有1,2,3,4个数,问你有多少种排列方法,并输出排列。

问题分析:

若采用分治思想进行求解,首先需要把大问题分解成很多的子问题,大问题是所有的排列方法。那么我们分解得到的小问题就是以 1 开头的排列,以 2 开头的排列,以 3 开头的排列,以 4 开头的排列。现在这些问题有能继续分解,比如以 1 开头的排列中,只确定了 1 的位置,没有确定 2 ,3 ,4 的位置,把 2,3,4 三个又看成大问题继续分解,2 做第二个,3 做第二个,或者 4 做第二个。一直分解下去,直到分解成的子问题只有一个数字的时候,不能再分解。只有一个数的序列只有一种排列方式,则子问题求解容易的多。

代码实现:

public class Test {
 public static void main(String[] args) {
 int[] arr = { 1, 2, 3, 4 };
 fullSort(arr, 0, arr.length - 1);
 }
 public static void fullSort(int[] arr, int start, int end) {
 // 递归终止条件
 if (start == end) {
 for (int i : arr) {
 System.out.print(i);
 }
 System.out.println();
 return;
 }
 for (int i = start; i <= end; i++) {
 swap(arr, i, start);
 fullSort(arr, start + 1, end);
 swap(arr, i, start);
 }
 }
 private static void swap(int[] arr, int i, int j) {
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
 }
}

6.3 归并排序

归并排序:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。即先划分为两个部分,最后进行合并。

分治算法,了解一下?

 

归并排序

伪代码:

算法 MergeSort(A, p, r)
输入:数组A[p...r]
输出:有序数组A
if(p < r)
 then q <- (p+r)/2//折半划分
 MergeSort(A, p ,q)//子问题1
 MergeSort(A, p ,q)//子问题2
 Merge(A, p ,q, r)//合并求解

代码实现:

public class MergeSort {
 //两路归并算法,两个排好序的子序列合并为一个子序列
 public void merge(int []a,int left,int mid,int right){
 int []tmp=new int[a.length];//辅助数组
 int p1=left,p2=mid+1,k=left;//p1、p2是检测指针,k是存放指针
 while(p1<=mid && p2<=right){
 if(a[p1]<=a[p2])
 tmp[k++]=a[p1++];
 else
 tmp[k++]=a[p2++];
 }
 while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
 while(p2<=right) tmp[k++]=a[p2++];//同上
 //复制回原素组
 for (int i = left; i <=right; i++) 
 a[i]=tmp[i];
 }
 public void mergeSort(int [] a,int start,int end){
 if(start<end){//当子序列中只有一个元素时结束递归
 int mid=(start+end)/2;//划分子序列
 mergeSort(a, start, mid);//对左侧子序列进行递归排序
 mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
 merge(a, start, mid, end);//合并
 }
 }
}

6.4 快速排序

快速排序的基本思想:当前待排序的无序区为 A[low..high] ,利用分治法可将快速排序的基本思想描述为:

(1)分解:

在A[low..high]中任选一个记录作为基准(pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1) 和 R[pivotpos+1..high] ,并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字 pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置( pivotpos )上,它无须参加后续的排序。

(2)求解:

通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

(3)合并:

因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步骤无须做什么,可看作是空操作。

分治算法,了解一下?

 

快速排序

代码实现:

#include <IOStream>
using namespace std;
void QuickSort(int arr[], int low, int high){
 if (high <= low) return;
 int i = low;
 int j = high + 1;
 int key = arr[low];
 while (true)
 {
 /*从左向右找比key大的值*/
 while (arr[++i] < key)
 {
 if (i == high){
 break;
 }
 }
 /*从右向左找比key小的值*/
 while (arr[--j] > key)
 {
 if (j == low){
 break;
 }
 }
 if (i >= j) break;
 /*交换i,j对应的值*/
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 /*中枢值与j对应值交换*/
 int temp = arr[low];
 arr[low] = arr[j];
 arr[j] = temp;
 QuickSort(arr, low, j - 1);
 QuickSort(arr, j + 1, high);
}

6.5 汉诺塔

汉诺塔(Hanoi Tower)问题也是一个经典的递归问题,该问题描述如下:

汉诺塔问题:古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这个盘子从A座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。

分治算法,了解一下?

 

两个盘子

分治算法,了解一下?

 

三个盘子

  • ① 如果只有 1 个盘子,则不需要利用 B 塔,直接将盘子从 A 移动到 C 。
  • ② 如果有 2 个盘子,可以先将盘子 2 上的盘子 1 移动到 B ;将盘子 2 移动到 C ;将盘子 1 移动到 C 。这说明了:可以借助 B 将 2 个盘子从 A 移动到 C ,当然,也可以借助 C 将 2 个盘子从 A 移动到 B 。
  • ③ 如果有 3 个盘子,那么根据 2 个盘子的结论,可以借助 C 将盘子 3 上的两个盘子从 A 移动到 B ;将盘子 3 从 A 移动到 C ,A 变成空座;借助 A 座,将 B 上的两个盘子移动到 C 。
  • ④ 以此类推,上述的思路可以一直扩展到 n 个盘子的情况,将将较小的 n-1个盘子看做一个整体,也就是我们要求的子问题,以借助 B 塔为例,可以借助空塔 B 将盘子A上面的 n-1 个盘子从 A 移动到 B ;将A 最大的盘子移动到 C , A 变成空塔;借助空塔 A ,将 B 塔上的 n-2 个盘子移动到 A,将 C 最大的盘子移动到 C, B 变成空塔。。。

代码实现:

 public static void hanoi(int n, String sourceTower, String tempTower, String targetTower) {
 if (n == 1) {
 //如果只有一个盘子1,那么直接将其从sourceTower移动到targetTower
 move(n, sourceTower, targetTower);
 } else {
 //将(盘子n-1~盘子1)由sourceTower经过targetTower移动到tempTower
 hanoi(n - 1, sourceTower, targetTower, tempTower);
 //移动盘子n由sourceTower移动到targetTower
 move(n, sourceTower, targetTower);
 //把之前移动到tempTower的(盘子n-1~盘子1),由tempTower经过sourceTower移动到targetTower
 hanoi(n - 1, tempTower, sourceTower, targetTower);
 }
 }
 //盘子n的从sourceTower->targetTower的移动
 private static void move(int n, String sourceTower, String targetTower) {
 System.out.println("第" + n + "号盘子 move:" + sourceTower + "--->" + targetTower);
 }

7 总结分析

分治法将规模为 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)



Tags:分治算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
当prompt策略遇上分治算法,南加大、微软让大模型炼成「火眼金睛」
近年来,大语言模型(LLMs)由于其通用的问题处理能力而引起了大量的关注。现有研究表明,适当的提示设计(prompt enginerring),例如思维链(Chain-of-Thoughts),可以解锁 LLM 在不同领域的...【详细内容】
2024-03-12  Search: 分治算法  点击:(20)  评论:(0)  加入收藏
Java基于分治算法实现的棋盘覆盖问题示例
本文主要介绍了ava基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了java基于分治算法实现棋盘覆盖问题的相关操作技巧,需要的朋友可以参考...【详细内容】
2022-07-30  Search: 分治算法  点击:(260)  评论:(0)  加入收藏
一文搞懂分治算法
前言分治算法(divide and conquer)是五大常用算法(分治算法、动态规划算法、贪心算法、回溯法、分治界限法)之一,很多人在平时学习中可能只是知道分治算法,但是可能并没有系统的...【详细内容】
2020-12-04  Search: 分治算法  点击:(240)  评论:(0)  加入收藏
什么是分治算法?
1 概念分治算法,根据字面意思解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题&hellip;&hellip;直到最后子问题可以...【详细内容】
2019-04-28  Search: 分治算法  点击:(2254)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(17)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(54)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(46)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(80)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(91)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(104)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(73)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(113)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(79)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(169)  评论:(0)  加入收藏
相关文章
    无相关信息
站内最新
站内热门
站内头条