Skip to content

Latest commit

 

History

History
51 lines (38 loc) · 1.44 KB

File metadata and controls

51 lines (38 loc) · 1.44 KB

贪心算法 & 动态规划

贪心算法:
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心

举个列子 比如有 1 5 10 20 硬币  如果需要凑到37块怎么凑 而且硬币数最少

1 第一步剪支 选择最优的 即选择最大的  20
2 选了20 还差17 在选最大的 10
3 还差7块 ,在选择最大的5
4 还差2块 ,只能选择1 1

结果是 20 10 5 1 1 
eg:MinCount.java



换个币比如 
2 ,4 ,7 ,9 ,10  要凑成16 
按照贪心算法 
10 + 4 + 2  很显然需要3个
而 最优的可能直接是 9 + 7  2个了 
显然 贪心算法不一定找的是最优解,只是找的相对最优解  
calcite cbo其实就是贪心的,配合一些剪枝的技巧 ,并不是全局最优解   
注意:calcite的代价优化都是需要自己实现过的,
1 实现统计 比如表的count 
2 实现算子的代价,默认是按行数实现的

算法实现:  DFS  =>  寻找到相对最优的解  先自己想想?
详见:

如果你要寻找到全局最优解 ,其实需要回朔所有的子问题解 选出最优的解,所以搜索的路径会很大
相对最优解实现只需要DFS每次按照最大的选取:
eg  x1 代表解的第一位 ,x2第二位 
 x1   x2   x2    x4  ....   
 10   10 
 9    9
 7    7
 4    4 
 2    2 
 
这样就是一个2维素组了 这样就很简单了 DFS 
实现 DFSGreedy.java



如果实现全局最优解了? 后续补充 
基于DFS
基于BFS