写在前面
昨晚网络咕了,而且比较晚,没交作业。解题报告写成书面的了,代码另发 + 博客。
1. 爬山算法
概述
-
随机算法
-
通过牺牲正确性来换取速度。
示例
在这个图中,如果当前在 (1) 位置,判断出这个位置的斜率,发现这个点右边要更靠上一些,于是往右走,然后发现走到了 (2) 位置,走过头了,就往回走,最后走到了 (3),即峰顶。
2. 模拟退火
概述
-
随机算法
-
同样是通过牺牲正确性以换取速度。
-
它具有一定的概率接受更劣的解,因此比爬山算法更为科学合理一些。
在这张图中,正确的解为绿勾,红叉是错误的解。我们现在在 (1) 号位置,如果用爬山算法,就会爬到红叉的位置。
虽然已经是一个极优解,但无论如何跑不到最优了。
而模拟退火算法它有一定的几率允许程序往绿色箭头方向跑,从而使得它跑到最优解的可能性更大。
3. Meet in the Middle
不是叫双向广搜嘛。