Просмотр исходного текста страницы Citeseer/Average-Case Performance of Rollout Algorithms for Knapsack Problems (2013) 10.1.1.367.776

{{checked|}}
{{citeseerlink|citeseer/Average-Case Performance of Rollout Algorithms for Knapsack Problems (2013) 10.1.1.367.776|<html>
«Алгоритмы развертывания» (Rollout algorithms) продемонстрировали отличную производительность при решении различных задач динамической и дискретной оптимизации. 
<p>
Хотя во многих случаях гарантируется, что ролл-аут алгоритмы работают так же хорошо, как и их базовые политики, теоретических результатов, показывающих дополнительное улучшение производительности, было немного. 
<p>
В данной работе мы проводим вероятностный анализ проблемы суммы подмножеств и проблемы ранца, приводя теоретические доказательства того, что алгоритмы выкатывания работают строго лучше, чем их базовые политики. 
<p>
Используя стохастическую модель из существующей литературы, мы анализируем два метода свертывания, которые мы называем последовательным свертыванием и исчерпывающим свертыванием, оба из которых используют простую жадную базовую политику. 
<p>
Для задачи о сумме подмножеств мы доказываем, что после всего одной итерации алгоритма выкатывания оба метода дают по крайней мере 30%-ное сокращение ожидаемого разрыва между значением решения и мощностью по сравнению с базовой политикой. 
<p>
Аналогичные результаты показаны для задачи о ранце.
</html>}}
{{@|тут немного круто, но можно наверно опустить все доказательства,  но хотя бы постановки-сами алгоритмы, …}} 

{{enddiv}}

[[Категория:CiteSeerArticles]]