首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >用遗传算法解决0-1背包问题更好吗?

用遗传算法解决0-1背包问题更好吗?
EN

Stack Overflow用户
提问于 2019-04-23 17:14:45
回答 1查看 758关注 0票数 2

背包问题是一个组合优化问题,它使背包中的对象在不超过其能力的情况下最大化。解决这一问题的方法有遗传算法、动态规划和贪婪方法。我想知道与动态规划相比,遗传算法的优缺点是什么?空间复杂性、时间复杂度和最优性?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2019-04-24 13:29:49

因此,为了回答这个问题,重要的是要考虑您认为最重要的是什么:或精确性

然而,遗传算法不要保证找到最优的解决方案通常运行得非常快。

对遗传算法的一些快速描述可能会产生:

  • 它是一个估计函数,不能保证找到全局最优解。
  • 它通常运行得非常快(无论是在内存使用还是在复杂性方面)。
  • 实际的计算是困难的,因为遗传算法在本质上是典型的特定问题和混沌问题。它的复杂性有一个很好的基础:O( O(Fitness) * (O(mutation) + O(crossover)))

但是,动态规划确实保证能够找到最优的解决方案,允许运行时间更长。对动态规划的一些快速描述可能会产生:

  • 它是一个精确的函数--保证了最全局最优解的收敛性。
  • 内存使用率高,运行时间长
  • 背包01问题的复杂性类似于:O(numItems * knapsackCapacity),内存复杂性类似于O(knapsackCapacity) (这归功于这个职位 )。

如果你问的是什么是首选,这是特定的主题。如果你想要一个足够好的快速猜测,GA可能是要走的路。但是,如果您需要一个有保证的、可验证的解决方案,则需要使用DP。

这应该满足一个基本的比较。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/55816310

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档