数据结构与算法(九) |
您所在的位置：网站首页 › 数据结构与算法论文引言范文 › 数据结构与算法(九) |
数据结构与算法(九)
|
数据结构与算法(九)-六大常用算法思想
1.贪心算法思想
greedy algorithm，又称贪婪算法。是一种在每一步选择中都采取在当前状态下最好或最优的选择。是对问题产生整体最优解或者是整体最优解的近似解。贪心算法在最优子结构的问题中最尤为效。 1.1 基本思路 建立数学模型来描述问题。把求解的问题分成若干个子问题。对每一子问题求解，得到子问题的局部最优解。把子问题的解局部最优解合成原来解问题的一个解。最优子结构性质: 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 贪心算法的一般流程 Greedy(C){ //C是问题的输入集合即候选集合 S={ }; //初始解集合为空集 while (not solution(S)){ //集合S没有构成问题的一个解 x=select(C); //在候选集合C中做贪心选择 if feasible(S, x) //判断集合S中加入x后的解是否可行 S=S+{x}; C=C-{x}; } return S; } 1.2 实例分析贪心算法不一定是整体的最优解。使用贪心算法是前提是：局本部最优策略能导致产生全局最优解。 1.背包问题
可见这个问题使用贪心算法即可实现。分析得到单价 水果单价（元/kg）苹果1梨3香蕉2菠萝4圣女果1.5肯定是先装单价最多的水果，那么就得到了菠萝20kg,梨30kg，圣女果50kg。 下面来看一个实战题 2.把数组排成最小的数 https://leetcode-cn.com/problems/container-with-most-water/ 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。如数组[3,30,34,5,9]，得到就是"3033459". 分析： 本质上还是一个排序题，假设数组nums的任意两个字符串为x和y，排序规则： 若拼接字符串x + y > y + x，则x 大于 y，使得x在y后；若拼接字符串x + y < y + x，则x 小于 y，使得x在y前；根据以上贪心规则，套用任何排序方法对nums排序即可。 public String minNumber(int[] nums) {//巧妙转化为String[]数组进行操作 String[] str = new String[nums.length]; for (int i = 0; i (x + y).compareTo(y + x));//这里调用内置函数法 自己实现快排实现排序性能更优 StringBuilder res = new StringBuilder(); for(String s:str) res.append(s); return res.toString(); }贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。 2.分治算法思想将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。即原问题的解即子问题的解的合并。快排、归并排序就用到此思想。 2.1 适用情况 该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（递归思想）利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。第三条特征是关键，如果具备第一条和第二条特征，而不具备第三条特征，则考虑用贪心法或动态规划法。 第四条特征涉及到分治法的效率，如果各子问题是不独立，一般用动态规划法较好。 2.2 算法流程分治法在每一层递归上都有三个步骤： 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。思维过程： 一定是先找到最小问题规模时的求解方法；然后考虑随着问题规模增大时的求解方法；找到求解的递归函数式后（各种规模或因子），设计递归程序。 2.3 算法实例详细分析请参看 归并：https://blog.csdn.net/yeahPeng11/article/details/117912723 二分：https://blog.csdn.net/yeahPeng11/article/details/118074093 归并排序 //写代码的时候先写合并操作merge() 再写分解操作 public int[] mergeSort(int[] arr){ if(arr.length if(l >= left.length) newArr[i] = right[r++]; else if(r >= right.length) newArr[i] = left[l++]; else if(left[l] /** * 皇后数组 * 下标对于棋盘行数，值表示列数，即位置为(i,a(i)). */ private int[] queen; /** * 求解n皇后问题 * * @param n */ public List backMethod(int n) { List res = new ArrayList(); //初始化数组 queen = new int[n]; //初始化皇后起点 Arrays.fill(queen, -1); //从第一个皇后开始 int k = 0; while (true) { //第k个皇后要后移一个 queen[k]++;//一开始由-1增加 //判断是否应该回到上一行搜索 if (queen[k] >= n) { //皇后越界,此行没有位置可以放置皇后 if (k > 0) {//把须修改后的数组位置改为-1 queen[k] = -1; k--;//回到没越界处 回溯 continue;//跳出下面判断 } else break; } if (!isMatch(k)) {//不与之前的皇后冲突 k++; if (k >= n) {//越界 //存储答案 res.add(queen); k--;//回到上一个皇后 回溯 } } } return res; } /** * 判断我们第k个皇后是否与之前的皇后冲突 * @param k * @return true表示冲突 */ private boolean isMatch(int k){ for (int i = k-1; i > -1 ; i--) { if(queen[k] == queen [i] || Math.abs(queen[k]-queen[i]) == Math.abs(k-i)) //Math.abs(queen[k]-queen[i]) == Math.abs(k-i) 表示在一条对角线上 return true; } return false; } } 4.动态规划算法思想 4.1 基本思想与策略基本思想与分治法类似，将待求解的问题分解为若干个子问题，按顺序求解子问题，前一子问题的解，为后一子问题的求解提供了实用的信息。有效的解决了重叠子问题的重复计算。 动态规划法与分治法的最大区别是：适合用于动态规划求解的问题，经过分解后得到的子问题往往不是互相独立的，即下一个子问题的解是建立在上一个子问题解的基础之上得到的。 动态规划算法的核心就是记住已经解决过的子问题的解，每次决策依赖于当前状态，又随即引起状态的转移。而记住求解的方式有两种：自顶向下的备忘录法和自底向上。 4.2 适用情况是否能够采用动态规划求解的问题一般具有三个特性： 最优化原理：问的最优解所包括的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理；无后效性：某一阶段的状态是确定的，之后的过程不会影响到曾经的状态，仅仅与当前状态有关；有重叠子问题：子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次用到（该性质可以不满足，但是动态规划的优势就在此）。在Markdown编辑器中设置字体颜色的方法之一：文本 4.3 求解的基本步骤问题是一个多阶段决策问题，一般有初始状态开始，通过对中间阶段决策的选择，达到结束的姿态。形成的一个决策序列：
动态规划算法的设计步骤： 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段，在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的(即不能由阶段1跳到阶段6)，否则无法求解；确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来，并且状态的选择要无后效性；确定决策并写出状态的转移方程：决策和状态转移是密不可分的，状态转移方程：当前状态=上一阶段的状态+决策，可根据两个阶段的状态之间的关系推导出决策方法和状态转移方程（常用）；寻找边界条件：给出的状态方程是一个递推公式，需要递推的终止条件。实际应用中，可以按照以下步骤进行： 分析最优解；递归定义最优解；自底向上或自顶向下的记忆方式（备忘录法）计算出最优值；根据计算优值时得到的信息，构造问题的最优解。 4.4 常见动态规划问题 斐波那契数列写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：（答案需要取模 1e9+7（1000000007）） F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 1.递归解法我直接就是给出递归解法： public int fib1(int n) { //数据合法性检验 if (n //数据不合法 if (n sum = (a+b) % 1000000007; a = b; b = sum; } return a; } 4.测试 public class Main { public static void main(String[] args) { Main m = new Main(); long l1 = System.nanoTime(); System.out.println(m.fib1(50)); long l2 = System.nanoTime(); System.out.println("fib1所花时间:"+(l2-l1)); long l3 = System.nanoTime(); System.out.println(m.fib2(50)); long l4 = System.nanoTime(); System.out.println("fib2所花时间:"+(l4-l3)); long l5 = System.nanoTime(); System.out.println(m.fib3(50)); long l6 = System.nanoTime(); System.out.println("fib3所花时间:"+(l6-l5)); } }输出可见效率提升之大 586268941 fib1所花时间:40009540500 586268941 fib2所花时间:176800 586268941 fib3所花时间:62800 5.枚举算法思想 5.1 枚举算法基本思想与策略在进行归纳时，如果诸葛考察了某类事件的所有可能情况，因而得出一个结论，那么该结论是可靠的，这种归纳方法叫做枚举法。 在使用枚举算法解题的基本思路如下： 确定枚举对象、范围和判定条件；逐一枚举可能的解并验证每个解是否是问题的解。 5.2 枚举算法步骤通常为三步： 确定解题的可能范围，不能遗漏任何一个真正的解，同步避免重复；判定是否为真正解的方法；为例提高解决问题的效率，是可能解的范围降至最小。 5.3 枚举算法实例 百钱买百鸡公鸡每只5元，母鸡每只3元，三只小鸡1元，用100元买100只鸡，问公鸡、母鸡、小鸡各多少只？ 分析：利用枚举法解决该问题，以三种鸡为的个数为枚举对象m,g,x，其中m+g+x=100。且买鸡钱总数5*m+3*g+x/3 = 100作为判断，穷举各种鸡的个数。 public void buyChicken() { for (int g = 0; g //母鸡最多可买33个 int x = 100 - g - m;// 三种鸡的总数是100只 if (((x % 3) == 0) && ((5 * g + 3 * m + x / 3) == 100)) {// 总花费为100元 System.out.println("公鸡为:" + g + ",母鸡为:" + m + ",小鸡为:" + x); } } } } 6.分支限界算法思想 6.1分支界限法的搜索策略在当前节点处，先生成其所有的子节点，然后再从当前节点的子节点中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个节点处，计算一个函数值（限界），并根据函数值，从当前节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。 6.2 选择方法 队列式（FIFO）分支限界法：队列式分支限界法将节点表组织成一个队列，并将队列的先进先出原则选取下一个节点为当前扩展节点；优先队列式分支限界法：优先队列式分支限界法将节点表组织成一个优先队列，并将优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。如果选择这种选择方式，往往将数据排成大顶堆或者小顶堆来实现。对比回溯法： 回溯法是找出解空间中满足约束条件的所有解；分支限界法是找出满足约束条件的一个解，或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解；回溯法是深度优先的搜索算法，分支界限法是广度优先或以最小耗费优先的搜索算法。 6.3 分支界限算法实例其实就是对广度优先算法是应用，这里参看图的广度优先遍历，找到最短路径 找到图begin->target的最短路径。例：下图的0->7最短路径之一：0-1-2-5-7。
详细步骤参看： https://blog.csdn.net/yeahPeng11/article/details/118309593中的图知识点 |
【本文地址】
今日新闻 |
推荐新闻 |