数据基础及结构 5

第10章算法思想经典算法设计思想解析与应用枚举法回溯法分治法动态规划贪心法10.1枚举法（ExhaustiveSearch）基本思想(BasicIdea)按照一定规则对所有可能解进行系统性遍历，并通过验证函数判断哪些解满足条件。核心特点(Features)全面性：保证找到所有解或最优解。简单性：逻辑直观，易于实现。局限性：时间复杂度高，适合小规模问题。使用步骤(Procedure)Step1:确定解空间明确候选解的范围和结构，界定搜索边界。Step2:遍历机制设计高效的方式来依次生成候选解，避免遗漏。Step3:验证函数对每个解进行条件判断，筛选出符合要求的解。10.1枚举法-示例：生成集合的所有子集问题描述给定一个集合，要求生成其所有可能的子集（幂集）。例如，输入[1,2]，输出应包含{},{1},{2},{1,2}。算法思路：递归枚举采用递归方式遍历每个元素。对于每个元素，都有“选”或“不选”两种决策分支。通过回溯法恢复状态，最终生成2^n种子集。C++核心实现代码template<typenameT>voidgenerateSubsets(constvector<T>&arr,intindex,vector<T>&subset,function<void(constvector<T>&)>action){//递归终止条件：处理完所有元素，输出当前子集if(index==arr.size()){action(subset);return;}//情况1：不包含当前元素generateSubsets(arr,index+1,subset,action);

//情况2：包含当前元素subset.push_back(arr[index]);generateSubsets(arr,index+1,subset,action);subset.pop_back();//回溯，恢复状态}10.1枚举法-性能分析与优化性能分析指标时间复杂度O(N×M)N为解空间大小，M为验证单个解的时间。规模增大时计算量呈指数增长。空间复杂度O(1)或O(N)取决于算法是否需要存储中间状态或候选解集。核心特性优点：思路直观，能保证找到全部解或最优解。缺点：效率低下，不适用于大规模问题。关键优化策略剪枝技术(Pruning)在搜索过程中及早排除不可能产生有效解的分支，减少不必要的计算。并行计算(Parallelism)将解空间分配至多线程或分布式系统中并行探索，利用多核资源加速。启发式排序与双向搜索优先考察更具潜在可行性的候选解；或从问题两端同时搜索以降低复杂度。10.2回溯法（Backtracking）基本思想：深度优先+剪枝在深度优先搜索的基础上加入剪枝判断，逐步构造候选解。当发现当前路径不满足约束条件或无法导向目标时，立即撤销最近一次选择并回退到上一步，尝试另一条路径。核心机制：试探—检查—撤销试探：做出一个局部选择，构造部分解。检查：判断当前路径是否满足约束条件。撤销：若不满足则回退（Backtrack），尝试其他选择。核心优势：高效削减搜索空间通过剪枝操作，能够有效避免进入无效的搜索分支，在保证解的正确性的同时，显著降低时间复杂度，提高搜索效率。10.2回溯法-示例：N皇后问题问题描述在N×N的棋盘上放置N个皇后，使得它们互不攻击。即任意两个皇后都不能处于同一行、同一列或同一斜线上。算法思路逐行尝试放置皇后，即时检查冲突。若当前路径不可行（无法放置），立即回退到上一行（回溯），尝试下一个可能的位置。C++核心实现classNQueensSolver{public:vector<vector<string>>solveNQueens(intn){vector<vector<string>>solutions;vector<int>board(n,-1);//每行皇后列位置，-1表示未放置backtrack(0,board,solutions);returnsolutions;}C++核心实现private://递归回溯函数voidbacktrack(introw,vector<int>&board,vector<vector<string>>&solutions){intn=board.size();if(row==n){//所有行放置完成solutions.push_back(formatSolution(board));return;}

//尝试当前行的每一列for(intcol=0;col<n;col++){if(isValid(board,row,col)){//检查冲突board[row]=col;//放置皇后backtrack(row+1,board,solutions);//递归下一行board[row]=-1;//回溯：撤销选择}}}//检查位置(row,col)是否安全boolisValid(constvector<int>&board,introw,intcol){for(inti=0;i<row;i++){//检查同列或对角线冲突（|Δrow|=|Δcol|）if(board[i]==col||abs(board[i]-col)==abs(i-row)){returnfalse;}}returntrue;}

//格式化解为棋盘表示vector<string>formatSolution(constvector<int>&board){vector<string>solution;intn=board.size();for(inti=0;i<n;i++){stringrow(n,'.');//初始化为全'.'row[board[i]]='Q';//皇后位置solution.push_back(row);}returnsolution;}};10.2回溯法-性能分析与应用性能分析与特性时间复杂度：O(b^d)(b为分支因子，d为搜索深度)空间复杂度：O(d)(取决于递归深度)核心优势：通过剪枝有效削减搜索空间，保证结果完整性局限性：问题规模过大时，时间开销依然较高典型应用场景约束满足问题：N皇后问题、数独求解组合问题：子集和、全排列生成路径搜索：迷宫求解、图的遍历决策优化：任务调度、资源分配10.3分治法（DivideandConquer）基本思想(BasicIdea)将大规模问题分解为若干个规模较小、结构相同的独立子问题，分别递归求解，最后合并子问题的解得到原问题的解。1.分解(Divide)将原问题划分为若干个规模较小、相互独立的子问题。2.求解(Conquer)递归求解各个子问题。若子问题足够小（基线条件），则直接求解。3.合并(Combine)将子问题的解合并起来，得到原问题的最终解。有效性条件(ValidityConditions)•问题具有可分解性•子问题具有独立性•子问题解可有效合并10.3分治法-示例：归并排序问题描述给定一个无序数组，通过分治法将其排序为有序数组。核心思路(Divide&Conquer)分解(Divide)：将数组递归二分，直到子数组长度为1。解决(Conquer)：单个元素的数组天然有序。合并(Merge)：逐层将两个有序子数组合并为一个大的有序数组。//复制剩余元素while(i<L.size())arr[k++]=L[i++];while(j<R.size())arr[k++]=R[j++];}template<typenameT>voidMergeSort(vector<T>&arr,intl,intr){if(l<r){intm=l+(r-l)/2;//防止整数溢出MergeSort(arr,l,m);//排序左半部MergeSort(arr,m+1,r);//排序右半部Merge(arr,l,m,r);//合并两部分}}C++ImplementationC++Implementationtemplate<typenameT>voidMerge(vector<T>&arr,intl,intm,intr){//创建左右子数组vector<T>L(arr.begin()+l,arr.begin()+m+1);vector<T>R(arr.begin()+m+1,arr.begin()+r+1);

inti=0,j=0,k=l;//索引：左数组、右数组、原数组

//比较左右数组元素，取较小者放入原数组while(i<L.size()&&j<R.size()){if(L[i]<=R[j])arr[k++]=L[i++];elsearr[k++]=R[j++];}

示例：归并排序10.3分治法-性能分析与应用性能分析核心要点时间复杂度分析通常使用主定理T(n)=aT(n/b)+f(n)刻画。归并排序为O(nlogn)。核心优势通过递归分解将复杂问题简化，显著降低时间复杂度。局限性效率高度依赖于子问题的独立性与合并步骤的可行性。典型应用场景排序算法：归并排序、快速排序查找算法：二分查找（BinarySearch）矩阵运算：Strassen矩阵乘法算法几何问题：最近点对问题求解并行计算：MapReduce分布式计算模型10.4动态规划（DynamicProgramming）基本思想(BasicIdea)将原问题分解为多个相互重叠的子问题，通过记录子问题的解并加以复用，从而避免重复计算，逐步合并子解得到全局最优解。有效性条件(Conditions)最优子结构：问题的最优解可由子问题最优解组合而成。重叠子问题：同一子问题在求解过程中被多次涉及。核心逻辑(CoreLogic)核心在于：记忆化(Memoization)+递推(Recursion)实现步骤(ImplementationSteps)定义状态：用dp[i]或dp[i][j]表示子问题的解。状态转移方程：建立当前状态与更小问题的联系。确定边界条件：处理最小规模的子问题。递推计算：自底向上填充表格或带记忆化递归。10.4动态规划-示例：0/1背包问题问题描述给定物品重量和价值，以及背包容量，选择物品使得总价值最大，且总重量不超过容量。每个物品只能选择一次（0或1）。算法思路(DP)定义dp[i][w]表示前i件物品放入容量为w的背包的最大价值。状态转移：取“放入当前物品”或“不放”中的最大值。C++代码实现intknapsack(intW,constvector<int>&weights,constvector<int>&values){intn=weights.size();//创建DP表(n+1行,W+1列)初始化为0vector<vector<int>>dp(n+1,vector<int>(W+1,0));

//填充DP表for(inti=1;i<=n;i++){for(intw=0;w<=W;w++){if(weights[i-1]<=w){//选择当前物品：当前价值+剩余容量最大价值intinclude=values[i-1]+dp[i-1][w-weights[i-1]];//不选择当前物品：继承前i-1个物品的最大价值intexclude=dp[i-1][w];dp[i][w]=max(include,exclude);}else{//当前物品超重，只能不选dp[i][w]=dp[i-1][w];}}}returndp[n][W];//返回最大价值}10.4动态规划-应用领域序列比对应用于DNA序列比对、最长公共子序列（LCS）等生物信息学场景。路径规划解决最短路径问题，如Floyd-Warshall算法，寻找最优路径。资源分配经典的背包问题、任务调度等，实现有限资源的最优配置。金融计算用于期权定价模型（如Black-Scholes）及风险评估计算。图像处理应用于图像拼接、特征匹配以及计算机视觉中的优化问题。自然语言处理在机器翻译、语音识别等领域中处理序列建模问题。10.5贪心法（GreedyAlgorithm）核心思想与特性基本思想：每一步都选择当前看起来最优的解，期望通过一系列局部最优的选择最终得到全局最优解。与动态规划区别：不做回溯，只在当下做出决策，一旦选择便不再改变。有效性条件与优缺点贪心选择性质：局部最优能够导向全局最优。最优子结构：问题的最优解可以由子问题的最优解构建而成。优点：实现简单，时间效率较高。缺点：并非所有问题都满足贪心性质，可能导致全局解失效。10.5贪心法-示例：活动选择问题问题描述给定一组活动，每个活动都有开始时间和结束时间。要求在不发生时间冲突的前提下，选择数量最多的活动。贪心策略1.按结束时间对活动进行升序排序。2.依次选择结束最早且与上一个选中活动不冲突的活动。C++实现代码structActivity{intstart;intfinish;};voidselectActivities(vector<Activity>&activities){//按结束时间升序排序（贪心选择关键）sort(activities.begin(),activities.end(),[](constActivity&a,constActivity&b){returna.finish<b.finish;});vector<Activity>selected;selected.push_back(activities[0]);//第一个活动必选intlast_finish=activities[0].finish;//记录最后结束时间

//遍历后续活动for(inti=1;i<activities.size();i++){//当前活动开始时间晚于最后结束时间->不冲突if(activities[i].start>=last_finish){selected.push_back(activities[i]);last_finish=activities[i].finish;//更新结束时间