| 共 5 篇文章 |
|
常用算法五（分支限界法）一、基本描述。所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点... 阅249 转2 评0 公众公开 14-04-19 23:16 |
当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。class Position{ public Position(){ } public Position(int row, int col){ this.col = col; 阅399 转6 评0 公众公开 14-04-19 23:15 |
常用算法三（贪心算法）一、基本概念： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。五、贪心策略的选择 因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。值得注意的是，贪心算法并不是完全不可以使用，贪心... 阅167 转5 评0 公众公开 14-04-19 23:14 |
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。* * NOTE: 使用动态规划法求解 背包问题 * 设 前 n 个背包，总承重为 j 的最优值为 v[n,j], 最优解背包组成为 b[n]; * 求解最优值： * 1. 若 j < wn, 则 ： v[n,j] = v[n-1,j]; * 2. 若 j >= wn, 则：v[n,... 阅492 转11 评0 公众公开 14-04-19 23:13 |
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么... 阅57 转3 评0 公众公开 14-04-19 23:11 |
