看板 dinos
作者 標題 程序算法与人生选择
時間 2012年12月28日 Fri. AM 10:16:21
http://coolshell.cn/articles/8790.html
程序算法与人生选择 | 酷壳 - CoolShell.cn
比如在找零钱的时候，如果要找补36元，我们一般会按这样的顺序找钱：20元，10元，5元，1元。
你不可能要所有的东西，所以你只能要你最重要的东西，你要知道什么东西最重要，你就需要对你心内的那些欲望和抱负有清楚的认识，“冒泡排序”——这种算法的思路就是每次冒泡出一个最大的数。所以，你有必要问问你自己，面对那些影响你选择的因子，如果你只能要一个的话，你会要哪个？而剩下的都可以放弃。于是，当你把最大的数，一个一个冒泡出来的时候，并用这个决策因子来过滤选项的时候，你就能比较容易地知道知道你应该选什么了。这个算法告诉我们，人的杂念越少，就越容易做出选择。
比如：你分不清楚，工资>业务前景吗？业务前景>能力提升吗？所以你完全没有办法进行冒泡法。那你，你不妨参考一个“快速排序”的思路——这个算法告诉我们，我们一开始并不需要找到最大的数，我们只需要把你价值观中的某个标准拿出来，然后，把可以满足这个价值的放到右边，不能的放到左边去。比如，你的标准是：工资大于5000元&&业务前景长于3年的公司，你可以用这个标准来过滤你的选项。然后，你可以再调整这个标准再继续递归下去。这个算法告诉我们，我们的选择标准越清晰，我们就越容易做出选择。
所谓贪婪算法是指，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择（注意：是当前状态下），从而希望导致结果是最好或最优的算法。贪婪算法最经典的一个例子就是哈夫曼编码。
比如在找零钱的时候，如果要找补36元，我们一般会按这样的顺序找钱：20元，10元，5元，1元。
但是我们知道，对于大部分的问题，贪婪法通常都不能找出最优解，因为他们一般没有测试所有可能的解。因为贪婪算法是一种短视的行为，只会跟据当前的形式做判断，也就是过早做决定，因而没法达到最佳解。
动态规划和贪婪算法的最大不同是，贪心算法做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
动态规划算法至少告诉我们两个事：
1）承前启后非常重要，当你准备去做遍历的时候，你的上次的经历不但能开启你以后的经历，而且还能为后面的经历所用。你的每一步都没有浪费。
2）是否可以回退也很重要。这意思是——如果你面前有两个选择，一个是A公司一个是B公司，如果今天你错失了B公司，那到你明天还能不能找回来？
比如说：你有两个offer，一个是Yahoo，一个是Baidu，上述的第一点会让我们思考，Yahoo和Baidu谁能给我们开启更大的平台？上述的第二点告诉我们，是进入Yahoo后如果没有选好，是否还能回退到Baidu公司？还是进入Baidu公司后能容易回退到Yahoo公司？
Dijkstra最短路径
最短路径是一个Greedy + DP的算法。相当经典。这个算法的大意如下：
1）在初始化的时候，所有的结点都和我是无穷大，默认是达不到的。
2）从离自己最近的结点开始贪婪。
3）走过去，看看又能到达什么样的结点，计算并更新到所有目标点的距离。
4）再贪婪与原点最短的结点，如此反复。
--
※ 作者: dinos 時間: 2012-12-28 10:16:21
※ 看板: dinos 文章推薦值: 0 目前人氣: 0 累積人氣: 94
回列表(←)
分享