遗传算法
{
最近向 我不容易 学习了遗传算法
他是专门研究这智能搜索这一方面的 水平很高
在我用 ID 算法解决"十滴水"小游戏时
他用遗传算法也写了 很强大
我用从他那所学的遗传算法 写了一个 01 背包问题的程序
}
01 背包问题 大家应该很熟悉
是背包问题的一种
不过值得注意的是
背包问题是 NPH 问题
(如果容量和体积是整数且有范围的话 自然用 DP 可以很好的解决)
对于此类没有多项式复杂度算法的问题
我们一般用搜索解决
对于 01 背包问题
最为朴素的做法是 枚举每个物品取还是不取 再选取最优解
不过这样的复杂度是 2^n 加了可行性和最优性剪枝也不能优化太多
这是我们就会考虑智能搜索算法
此类算法很强大 目前我只了解过遗传算法- -|||
于是我就用遗传算法写了一个
在理解 我不容易 的教导的基础之上 我还参考了这篇论文
http://www.docin.com/p-47510663.html
遗传算法本质是模拟达尔文的生物进化论思想
评论1