Проблема с обновлением списка - List update problem

В Обновление списка или Доступ к списку проблема - это простая модель, используемая при изучении Конкурентный анализ из онлайн-алгоритмы. Дан набор элементов в списке, где стоимость доступа к элементу пропорциональна его расстоянию от заголовка списка, например а Связанный список, и последовательность запросов доступа, проблема состоит в том, чтобы придумать стратегию переупорядочения списка, чтобы минимизировать общую стоимость доступа. Изменить заказ можно в любое время, но это требует затрат. Стандартная модель включает два действия переупорядочивания:

Свободное перемещение элемента, к которому осуществляется доступ, в любое место перед его текущим положением;
Платная перестановка стоимости единицы для обмена любых двух соседних элементов в списке. Производительность алгоритмов зависит от построения злоумышленниками последовательностей запросов при различных Модели противника

Онлайн-алгоритм для этой проблемы должен переупорядочивать элементы и обслуживать запросы, основанные только на знании ранее запрошенных элементов, и, следовательно, его стратегия может не иметь оптимальной стоимости по сравнению с автономным алгоритмом, который может видеть всю последовательность запроса и разрабатывать завершите стратегию до обслуживания первого запроса.

Было высказано предположение, что наряду с ее первоначальным использованием эта проблема имеет сильное сходство с проблемами улучшения глобального контекста и сжимаемости после Преобразование Барроуза-Уиллера. После этого преобразования файлы имеют тенденцию иметь большие области с локально высокими частотами, а эффективность сжатия значительно повышается за счет методов, которые стремятся перемещать часто встречающиеся символы к нулю или к началу «списка». Из-за этого методы и варианты Move-to-Front и частотных подсчетов часто следуют алгоритму BWT для улучшения сжимаемости.

Модели противника

Противник - это объект, который может выбирать последовательность запроса. ${ displaystyle sigma}$ для алгоритма ALG. В зависимости от того, ${ displaystyle sigma}$ могут быть изменены в зависимости от стратегии ALG, противникам предоставляются различные полномочия, и выполнение ALG измеряется против этих противников.

An невнимательный противник должен построить всю последовательность запроса ${ displaystyle sigma}$ перед запуском ALG, и платит оптимальную офлайн-цену, ${ displaystyle OPT ( sigma)}$ который сравнивается с ${ Displaystyle ALG ( sigma)}$

An адаптивный онлайн-противник получает возможность сделать следующий запрос на основе предыдущих результатов онлайн-алгоритма, но оплачивает запрос оптимально и онлайн.

An адаптивный офлайн-противник получает возможность сделать следующий запрос на основе предыдущих результатов онлайн-алгоритма, но оплачивает оптимальную автономную стоимость.

Автономные алгоритмы

Конкурентный анализ для многих проблем обновления списков проводился без каких-либо конкретных знаний о точной природе оптимального автономного алгоритма (OPT). Существующий алгоритм работает за O (п2^л(л-1)!) Время и O (л!) место, где п - длина последовательности запроса и л длина списка.^[1] Самый известный оптимальный автономный алгоритм, зависящий от длины последовательности запросов, выполняется за время O (l ^ 2 (l − 1)! N), опубликованный доктором Срикришнаном Дивакараном в 2014 году.^[2]

Платные транспозиции обычно необходимы для оптимальных алгоритмов. Рассмотрим список (а,б,c) куда а находится во главе списка, а последовательность запроса c,б,c,б. Оптимальный автономный алгоритм, использующий только бесплатные обмены, будет стоить 9 (3 + 3 + 2 + 1), тогда как оптимальный автономный алгоритм, использующий только платные обмены, будет стоить 8. Таким образом, мы не можем просто использовать бесплатные транспозиции для оптимального автономного алгоритма. .

Доказано, что оптимальной проблемой обновления списка является NP-жесткий к (Ambühl 2000 ).

Онлайн алгоритм

Онлайн-алгоритм ALG имеет конкурентное соотношение c если для любого входа он работает как минимум так же хорошо, как c раза хуже ОПТ. т.е. если существует ${ displaystyle alpha geq 0}$ такой, что для всех последовательностей запросов конечной длины ${ displaystyle sigma}$ , ${ Displaystyle ALG ( sigma) -c.OPT ( sigma) leq alpha}$ . Онлайн-алгоритмы могут быть детерминированными или рандомизированными, и оказывается, что рандомизация в этом случае действительно может помочь против невнимательных злоумышленников.

Детерминированный

Большинство детерминированных алгоритмов являются вариантами этих трех алгоритмов:

MTF (перейти вперед): После доступа к элементу переместите его в начало списка, не меняя порядок других элементов.
TRANS (транспонировать): Получив доступ к элементу, переместите его на предыдущий элемент.
FC (счетчик частоты): Для каждого элемента ведите подсчет частоты числа обращений к нему - при обращении к элементу увеличивайте его счетчик частоты и переупорядочивайте список в порядке убывания частот.

Обратите внимание, что все они используют только свободные транспозиции. Получается, что и TRANS, и FC неконкурентоспособны. В классическом результате с использованием Возможный метод анализ (Слеатор и Тарьян 1985 ) доказал, что MTF 2-конкурентна. Доказательство не требует явного знания OPT, но вместо этого подсчитывает количество инверсий, то есть элементов, встречающихся в противоположном порядке в списках MTF и OPT.

Любой детерминированный алгоритм имеет нижнюю границу ${ displaystyle 2 - { frac {2} {l + 1}}}$ для списка длины л, а MTF фактически является оптимальным детерминированным алгоритмом обновления списка. Тип злоумышленника не имеет значения в случае детерминированных алгоритмов, потому что злоумышленник может самостоятельно запустить копию детерминированного алгоритма, чтобы предварительно вычислить наиболее опасную последовательность.

Рандомизированный

Рассмотрим следующий простой рандомизированный алгоритм:

КУСОЧЕК: Для каждого элемента в списке оставьте немного. Инициализируйте все биты равномерно и случайным образом на 0 или 1. При обращении к элементу переверните бит, и если он равен 1, переместите его вперед, иначе не делайте этого.

Этот алгоритм почти не случайный - он делает все свои случайные выборы в начале, а не во время выполнения. Оказывается, BIT нарушает детерминированную границу - это лучше чем МОГ против невнимательных противников. Это 7/4-конкурентоспособный. Существуют и другие рандомизированные алгоритмы, такие как COMB, которые работают лучше, чем BIT. Борис Тейя доказал нижнюю границу 1,5 для любого алгоритма обновления рандомизированного списка.^[3]

Связанные проблемы

Проблема обновления списка, при которой элементы могут быть вставлены и удалены, называется проблемой обновления динамического списка, в отличие от проблемы обновления статического списка, когда разрешен только доступ к элементам списка. Верхняя граница ${ displaystyle 2 - { frac {2} {l + 1}}}$ справедливо и для динамической модели.

Также существуют разные модели стоимости. В обычной модели полной стоимости доступ к элементу, находящемуся в позиции я расходы я, но последнее сравнение неизбежно для любого алгоритма, т.е. есть я-1 элементы, стоящие на пути я. В модели частичных затрат эти затраты на окончательное сравнение, составляющие в сумме количество элементов в последовательности запроса, игнорируются. Для расходов на оплаченные транспозиции, отличные от единицы, п^d используются модели.

Смотрите также

Примечания

^ Н. Рейнгольд и Дж. Вестбрук. Оптимальные автономные алгоритмы для правил обновления списка и разбивки на страницы. Технический отчет YALE / DcS / TR-805, Йельский университет, Нью-Хейвен, Коннектикут, август 1990 г.
^ Дивакаран, Шрикришнан (30 апреля 2014 г.). «Оптимальный автономный алгоритм обновления списка». arXiv:1404.7638 [cs.DS ].
^ Тея, Борис, Нижняя граница для алгоритмов обновления рандомизированных списков, Инф. Процесс. Lett. (1993), стр. 5-9.