背包问题是一个组合优化问题,它使背包中的对象在不超过其能力的情况下最大化。解决这一问题的方法有遗传算法、动态规划和贪婪方法。我想知道与动态规划相比,遗传算法的优缺点是什么?空间复杂性、时间复杂度和最优性?
发布于 2019-04-24 13:29:49
因此,为了回答这个问题,重要的是要考虑您认为最重要的是什么:或精确性。
然而,遗传算法不要保证找到最优的解决方案通常运行得非常快。
对遗传算法的一些快速描述可能会产生:
O( O(Fitness) * (O(mutation) + O(crossover)))
但是,动态规划确实保证能够找到最优的解决方案,允许运行时间更长。对动态规划的一些快速描述可能会产生:
O(numItems * knapsackCapacity)
,内存复杂性类似于O(knapsackCapacity)
(这归功于这个职位 )。如果你问的是什么是首选,这是特定的主题。如果你想要一个足够好的快速猜测,GA可能是要走的路。但是,如果您需要一个有保证的、可验证的解决方案,则需要使用DP。
这应该满足一个基本的比较。
https://stackoverflow.com/questions/55816310
复制相似问题