Алгоритмы решения можно разделить на два типа:
Применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора).
Жадный алгоритм.
Алгоритм называется приближенным алгоритмом с гарантированной абсолютной точностью , если для любого примера алгоритм находит значение с отклонением от оптимума не более , то есть , для всех .
Теорема:
Пусть — приближенный алгоритм с гарантированной абсолютной точностью и трудоемкостью . Тогда алгоритм для любого примера позволяет найти точное решение задачи о рюкзаке с той же трудоемкостью.
Жадный алгоритм:
В случае применения жадного алгоритма поступаем так: сортируем предметы по убыванию стоимости единицы каждого. , где - относительная стоимость единицы предмета , - вес предмета , - стоимость предмета . Всего предметов. Пытаемся поместить в рюкзак все что помещается, и одновременно наиболее дорогое по параметру . Оценим сложность метода. Для сортировки нам потребуется плюс проход по N предметам в цикле. Итого , что в общем случае равно . Скорость работы относительно других алгоритмов высока, но если посмотреть более внимательно, видно, что точное решение мы получим не всегда.
Плюсы жадного алгоритма:
Высокое время работы, ограниченное только скоростью сортировки, в среднем .
Может работать с большими значениями .
Не использует дополнительных ресурсов компьютера.
Простота реализации.
Минусы жадного алгоритма:
Задача коммивояжёра, варианты, методы решения. Алгоритм имитации отжига. Муравьиный алгоритм. Метод роя частиц.
Задача математического программирования по определению оптимального маршрута коммивояжера, цель которого состоит в том, чтобы посетить все объекты, записанные в задании, за кратчайший срок и с наименьшими затратами. В теории графов задача о коммивояжёре — это поиск пути, связывающего два или более узла, с использованием критерия оптимальности.
Достарыңызбен бөлісу: |
