Сравнительный анализ методов

Минусы Полного перебора

· Входные данные не велики, для N=7 программа укладывается в 1с. Уже для N=10 требуется примерно 40с.

· Временная сложность O(N!)

Плюсы Полного перебора

· Полный перебор дает точное решение.

· Простота реализации

Минусы Метода ветвей и границ

· В худшем случае работает как полный перебор.

Плюсы Метода ветвей и границ

· Возможно значительное сокращение времени работы.

· Простота реализации.

Минусы Жадного алгоритма

· Всегда можно предоставить такой набор, при котором решение будет не точным.

Плюсы Жадного алгоритма

· Высокое время работы, ограниченное только скоростью сортировки, в среднем O(NlogN).

· Может работать с большими значениями N.

· Не использует дополнительных ресурсов компьютера.

· Простота реализации.

Минусы ДП – алгоритма:

· Веса предметов целые, если брать вещественные значения, ДП - алгоритм неприменим!

· Использование большого количества оперативной памяти для хранения таблиц промежуточных решений.

· Для больших значений N количества предметов ДП – алгоритм работает O().

Плюсы ДП – алгоритма:

· Высокая скорость работы по сравнению с другими алгоритмами (для не больших значений N<50).

· Получаем точное решение.

· Имеем оптимальные загрузки рюкзака для всех его весов от 1 до MaxW

На диаграмме 1. показано соотношение времени работы алгоритмов. По вертикальной оси в 1/10000 секунд. По горизонтальной оси в зависимости от количества предметов. Для ДП алгоритма для количества n предметов брался вес w=10*n, так как скорость работы ДП алгоритма зависит от произведения w *n.

Дата добавления: 2014-10-17