6 ms·
I thought the knapsack problem had a pretty good deterministic solution via the magic of dynamic programming? That said, isn't it usually best to use GA algori
by Swizec 14y ago
I thought the knapsack problem had a pretty good deterministic solution via the magic of dynamic programming?
That said, isn't it usually best to use GA algorithms only where a simpler algorithm does not exist? Or does the GA version actually produce better results than dynamic programming?
- bkanber 14y agoCorrect and correct. The knapsack problem does have an excellent dynamic programming solution. And of course, where there's a simpler algorithm, you should use it. This article isn't about the knapsack problem; it's about learning GAs. The knapsack problem is just an easy-to-visualize and easy-to-implement problem to solve in order to demonstrate features of genetic algorithms.
- Swizec 14y agoFair point. I once used genetic algorithms for path planning where A* would do. While it was fun to implement, the scoring was based on "goodness of path found in time X" ... I didn't get a very high score on that homework. On the other hand, I got a surprisingly high score for what was essentially "random guessing until you run out of time".