Итак, чтобы ответить на этот вопрос, важно рассмотреть то, что вы считаете наиболее важным: Скорость или Точность
Генетические алгоритмы сделатьНе гарантируется нахождение наиболее оптимального решения , однако они обычно работают очень быстро.
Некоторые краткие описания генетического алгоритма могут привести к:
- Это оценка функция и не гарантирует нахождение оптимальной в глобальном масштаберешение
- Обычно оно выполняется очень быстро (как по объему памяти, так и по сложности).
- Фактические вычисления трудны, поскольку генетические алгоритмы, как правило, специфичны для конкретной проблемы и хаотичны по своей природе.Хорошая база для того, как может выглядеть ее сложность:
O( O(Fitness) * (O(mutation) + O(crossover)))
Тем не менее, динамическое программирование гарантирует , чтобы найти наиболее оптимальное решение с гораздо более длительным временем выполнения.Некоторые краткие описания динамического программирования могут дать:
- Это точная функция - гарантирует сходимость для наиболее оптимального в глобальном масштабе решения
- Высокое использование памяти и очень длительное время выполнения
- Сложность для проблемы рюкзака 01 выглядит примерно так:
O(numItems * knapsackCapacity), а сложность памяти, например, O(knapsackCapacity) (кредиты в этом посте за это)
Если выспросить, что является предпочтительным, это конкретный предмет.Если вы хотите быстро получить достаточно правильное предположение, возможно, GA - это то, что вам нужно.Но если вам нужно гарантированное и поддающееся проверке решение, DP - это путь.
Это должно удовлетворить базовое сравнение.