Citeseer/Average-Case Performance of Rollout Algorithms for Knapsack Problems (2013) 10.1.1.367.776
Хотя во многих случаях гарантируется, что ролл-аут алгоритмы работают так же хорошо, как и их базовые политики, теоретических результатов, показывающих дополнительное улучшение производительности, было немного.
В данной работе мы проводим вероятностный анализ проблемы суммы подмножеств и проблемы ранца, приводя теоретические доказательства того, что алгоритмы выкатывания работают строго лучше, чем их базовые политики.
Используя стохастическую модель из существующей литературы, мы анализируем два метода свертывания, которые мы называем последовательным свертыванием и исчерпывающим свертыванием, оба из которых используют простую жадную базовую политику.
Для задачи о сумме подмножеств мы доказываем, что после всего одной итерации алгоритма выкатывания оба метода дают по крайней мере 30%-ное сокращение ожидаемого разрыва между значением решения и мощностью по сравнению с базовой политикой.
Аналогичные результаты показаны для задачи о ранце. …»
тут немного круто, но можно наверно опустить все доказательства, но хотя бы постановки-сами алгоритмы, …
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.