Citeseer/Average-Case Performance of Rollout Algorithms for Knapsack Problems (2013) 10.1.1.367.776 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{citeseerlink|citeseer/Average-Case Performance of Rollout Algorithms for Knapsack Problems (2013) 10.1.1.367.776|<html> {{@|тут немного…») |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
{{citeseerlink|citeseer/Average-Case Performance of Rollout Algorithms for Knapsack Problems (2013) 10.1.1.367.776|<html> | {{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}} | {{enddiv}} | ||
[[Категория:CiteSeerArticles]] | [[Категория:CiteSeerArticles]] | ||
Текущая версия на 14:45, 23 ноября 2021
Хотя во многих случаях гарантируется, что ролл-аут алгоритмы работают так же хорошо, как и их базовые политики, теоретических результатов, показывающих дополнительное улучшение производительности, было немного.
В данной работе мы проводим вероятностный анализ проблемы суммы подмножеств и проблемы ранца, приводя теоретические доказательства того, что алгоритмы выкатывания работают строго лучше, чем их базовые политики.
Используя стохастическую модель из существующей литературы, мы анализируем два метода свертывания, которые мы называем последовательным свертыванием и исчерпывающим свертыванием, оба из которых используют простую жадную базовую политику.
Для задачи о сумме подмножеств мы доказываем, что после всего одной итерации алгоритма выкатывания оба метода дают по крайней мере 30%-ное сокращение ожидаемого разрыва между значением решения и мощностью по сравнению с базовой политикой.
Аналогичные результаты показаны для задачи о ранце. …»
тут немного круто, но можно наверно опустить все доказательства, но хотя бы постановки-сами алгоритмы, …