递归与分治

<h2><a id="1__0"></a>1 递归与分治</h2> <h3><a id="11__1"></a>1.1 递归</h3> <p><strong>递归算法</strong>：直接或间接地调用自身的算法。<br /> <strong>递归函数</strong>：用函数自身给出定义的函数。</p> <h3><a id="12__5"></a>1.2 分治法</h3> <p><strong>思想</strong>：一个规模为 n 的问题，分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题相同。</p> <p><strong><mark>二分搜索</mark></strong></p> <p><strong>基本思想</strong>：</p> <ul> <li>a[0] … a[n-1]</li> </ul> <p><img src="https://static.couragesteak.com/article/5f5a433fb7708f81876192f2f22048ae.png" alt="image.png" /></p> <p><strong>复杂度顺序搜索比较</strong>：</p> <p><img src="https://static.couragesteak.com/article/057f86cc02a4d08e4a8c17bfd49ec436.png" alt="image.png" /></p> <p><strong>代码实现</strong>：</p> <pre><div class="hljs"><code class="lang-java"> </code></div></pre> <h2><a id="2__28"></a>2 动态规划</h2> <p><strong>思想</strong>：将一个规模为 n 问题分解为 k 个规模较小的子问题，但是这些子问题不独立，保存已解决的子问题的答案，而在需要时在找到求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。</p> <p><strong>基本步骤</strong> ：<br /> （1）找出最优解的性质，并刻画其结构特征。<br /> （2）递归地定义最优值<br /> （3）以自底向上的方式计算最优值<br /> （4）根据计算最优值时得到的信息，构造最优解。</p> <p>最少数乘次数：最优值<br /> 最优计算次序：最优解<br /> 最优子结构性质：一定最优</p> <h2><a id="3__41"></a>3 贪心算法</h2> <ol> <li>局部最优选择</li> <li>贪心算法<br /> （1）贪心选择性质<br /> （2）最优子结构性质：原问题最优解包含子问题最优解。</li> </ol> <ul> <li>最优装载</li> <li>活动安排问题</li> </ul> <h2><a id="4__50"></a>4 回溯法</h2> <p><strong>基本步骤</strong>：</p> <p>（1）定义解空间<br /> （2）构造解空间<br /> （3）构造解空间树<br /> （4）搜索（深度有限）</p> <p><strong>名词解释</strong>：<br /> （1）解空间：所有解的集合<br /> （2）解空间树：子集树，所有接构造为一棵树<br /> （3）死节点：2个节点都遍历了<br /> （4）活结点：还有没有遍历的</p> <ul> <li>批处理作业调度</li> <li>n后问题</li> </ul> <h2><a id="5__67"></a>5 分支限界法</h2> <p><strong>1. 分支限界法与回溯法的不同：</strong><br /> （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而 分支限界法的求解目标是找出满足约束条件的一个解，或是满足约束条件的解中找出某种意义下的最优解。<br /> （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度有限或以最小耗费优先的方式搜索解空间树。</p> <p><strong>思想</strong>：<br /> 常以广度优先或以最小耗度（最大收益）的方式搜索问题的解空间树。</p>