Estom的博客

贪心算法概述思想 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。 特点 贪心算法不能对所有问题都得到整体最优解。但对许多问题他能产生整体最优解，或者最优解的近似。 贪心算法中较大子问题的解敲好包含了较小子问题的解作为子集。与动态规划算法中的优化原则本质上一致。 动态规划算法在某一步决定优化函数的最大或最小值时，需要考虑他的所有子问题的优化函数的值。然后从中选出最有的结果。贪心算法的每步判断时，不考虑子问题的计算结果，而是根据当前的情况采取“只顾眼前”的贪心策略决定取舍。 贪心算法的适用条件 最优子结构性质 一个问题的最优解包含其子问题的最优解。问题具有最优子结构性质时，可以用动态规划算法或者贪心算法求解。 贪心选择性质 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 动态规划算法通常是自底向上的方式来求解各个子问题。贪心算法同行一自顶向下的方式，一迭代的方式作出相机的谈心选择。每左慈谈心选择就将所求问题简...

Huffman算法Huffman算法问题描述 一个字符串文件，我们希望尽可能多地压缩文件，但源文件能够很容易地被重建。 用特定的比特串表示每个字符，称为字符的编码，文件的大小取决于文件中的字符数n。我们可以使用一种定长编码，对每个字符赋予一个长度同为m (m≥log2n)的比特串。 设文件中的字符集是C={c1,c2,…, cn}, 又设f(ci), 1≤i≤n,是文件中字符ci的频度，即文件中ci出现的次数。 由于有些字符的频度可能远大于另外一些字符的频度，所以用变长的编码。 去除编码的二义性： 当编码在长度上变化时，我们规定一个字符的编码不能是另一个字符编码的前缀（即词头），这种码称为前缀码。 例如，如果我们把编码10和101赋予字符“a” 和“b”就会存在二义性，不清楚10究竟是“a” 的编码还是字符“b”的编码的前缀。 一旦满足前缀约束，编码即不具备二义性，可以扫描比特序列直到找到某个字符的编码。 算法原理 由Huffman算法构造的编码满足前缀约束，并且最小化压缩文件的大小。算法重复下面的过程直到C仅由一个字符组成： 设ci和cj是两个有最小...

回溯法0 概述基本思想 回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法的基本思想：该方法系统地搜索一个问题的所有的解或任一解。 与剪枝相结合，也称为回溯-剪枝法。 深度优先搜索与回溯剪枝这两个思想有一个非常重要的优势。它是一条路经走到黑。如果这条路径合适的话，就可以直接返回。另外。当前所有的搜索选项中，只有一条路径在工作。也就是说只需要记录当前一条路径的状态。所以解决迷宫问题的时候，不需要复杂的状态记录方法。只需要记录当前这一个分支的路径状态即可。 要素 解向量-问题解的表示：回溯法将问题的解表示成n元式$(x_1,x_2,\cdots,x_n)$。 显示约束：对分量xi的取值限定。 隐式约束：对满足问题的解而对不同分量之间施加约束 解空间：对于一个实例，解向量满足显示约束条件的所有多元组，构成了该实例的一个解空间。 回溯法的适用条件 适用于搜索问题和优化问题 多米诺性质：叶子节点的解一定...

N皇后问题1 N皇后问题-回溯法问题描述在N×N的棋盘中放置N个皇后，使得任何两个皇后之间不能相互攻击，试给出所有的放置方法。 问题分析 问题解向量：(x1, x2, … , xn) 显约束：xi=1,2, … ,n 隐约束： 不同列：xi不等于xj； 不处于同一正、反对角线：|i-j|不等于|xi-xj| 算法时间复杂度（1）搜索1+n+n2+…+nn=(nn+1-1)/n-1≤2nn;（2）每个节点判断是否符合规则，最多要判断3n个位置（列方向、主与副对角线方向是否有皇后）故最坏情况下时间复杂度O(3n×2nn)=O(nn+1) 算法实现123456789101112131415bool Queen::Place(int k) { for (int j=1;j<k;j++) if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true;} void Queen::Backtr...

旅行商问题1 旅行商问题-回溯法问题描述某售货员要到若干城市去推销商品，已知各城市间的路程耗费（代价），如何选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使得总路程耗费最小。 问题分析 解向量为<i1=1,i2,i3,…,in>，其中i2,i3,…,in为{2,3,…,n}的一个排列。搜索空间为排列树 显约束： i=n时，检查是否存在一条从顶点x[n-1]到x[n]的边和一条从顶点x[n]到顶点1的边，若存在，需要判断当前回路代价是否优于已找到的当前最优回路代价bestc，若为真，更新当前最优值bestc和最优解bestx。 当i<n时，当前扩展结点位于排列树的第i-1层。若图中存在从顶点x[i-1]到顶点x[i]的边，且x[1:i]的代价小于当前最优值bestc时，进入排列树的第i层，否则剪去相应子树。 算法时间复杂度算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。 算法原理 算法实现1234567891011...

01背包问题1 01背包问题-回溯法问题描述将物品放到背包中。 n件物品 每件物品的重量为w[i] 价值为v[i] m个背包 每个背包的容量为c[j] 求背包装载的最大价值。或者是否能装下所有。 具体问题n=3，C=20，(v1,v2,v3)=(20,15,25)， (w1,w2,w3)=(10,5,15)，求X=(x1,x2,x3)使背包价值最大？ 问题分析 解空间是子集树 可行性约束函数（剪枝函数）$\sum w_ix_i\leq c_i$ 算法原理 算法实现123456789101112131415template<class Typew, class Typep>Typep Knap<Typew, Typep>::Bound(int i){// 计算上界 Typew cleft = c - cw; // 剩余容量 Typep b = cp; // 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cle...

作业调度问题1 作业调度问题-回溯法问题描述给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。 批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。 问题分析 解空间：排列树问题。

完全背包问题1 完全背包问题将物品放到背包中。 无限件物品 每件物品的重量为w[i] 价值为v[i] m个背包 每个背包的容量为c[j] 求背包装载的的最大价值。

迷宫问题1 矩阵中的路径问题描述 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。 123[["a","b","c","e"],["s","f","c","s"],["a","d","e","e"]] 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。 链接 问题分析 最典型的回溯剪枝算法。 问题分类 二维数组，矩阵 回溯剪枝、dfs、递归 迷宫问题 策略选择 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符...

分支限界1 概述基本思想 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 常见的两种分支界限法 队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 使用条件 问题的多米诺性质叶子节点的解一定满足其父节点。叶子结点为真则父节点一定为真。同理父节点为假则叶子结点一定为假（逆否命题）。用父节点为假的情况进行剪枝操作。 求解最优解或一个可行解 设计要素 针对问题定义解空间 问题解向量 解向量分量取值集合 构造解空间树 判断是否满足多米诺性质 确定剪枝函数 确定存储搜索路径的数据结构 分支限界发的核心思想在于界的设计 分支限界法的程序结构 队列+循环的方法 2 分治限界实现...