Альтернативные показатели эффективности онлайновых алгоритмов

Постановка задачи

Несмотря на то, что онлайновые алгоритмы изучались более тридцати лет, явное введение сравнительного (конкурентного) анализа в основополагающих статьях Слейтора и Тарьяна [8] и Манасса, Макгиоха и Слейтора [ ] привело к взрывному росту количества исследований этого класса задач и алгоритмов, и с тех пор оба понятия (онлайновые алгоритмы и конкурентный анализ) остаются тесно связанными друг с другом. Онако уже на раннем этапе этих исследований возникли вопросы к реалистичности и практичности модели, связанные главным образом с ее пессимизмом. Эта характеристика в некоторых случаях сказывается на способности модели к различению хороших и плохих алгоритмов. В статье 1994 года «За пределами конкурентного анализа» [ ] Кутсупиас и Пападимитриу предложили и исследовали два альтернативных показателя эффективности онлайновых алгоритмов, тесно связанные с конкурентным анализом и при этом лишенные вышеупомянутых слабостей. Окончательная версия этой работы вышла в 2000 году [4].

В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его всемогущего соперника на входных данных, относящихся к наихудшему случаю. Коэффициент конкурентоспособности алгоритма A определяется как наихудшее возможное отношение R = max A(x) opt(x) ; где x пробегает все возможные входные данные задачи, а A(x) и opt(x) представляют собой стоимость решений, полученных алгоритмом A, и оптимальный оффлайновый алгоритм для входного значения x(1), соответственно. Это понятие может быть расширено для определения коэффициента конкурентности задачи как минимального коэффициента конкурентности алгоритма ее решения, а именно R = min RA = min max A Ax opt(x)

1 Все задачи в данной статье предполагаются онлайновыми задачами минимизации, следовательно, цель заключается в минимизации затрат. Все представленные здесь результаты действительны и для онлайновых задач максимизации с соответствующими корректировками в определениях.

Основная критика данного подхода заключалась в том, что из-за характерного пессимизма, присущего всем типам анализа наихудших вариантов, ему не удается различать алгоритмы, демонстрирующие разную эффективность при разных условиях. Кроме того, алгоритмам, которые «пытаются» работать лучше по сравнению со своими метриками для наихудшего случая, часто не удается показать эффективное поведение для различных «типичных» входных данных. Эти аргументы проще проверить в тех (редких) сценариях, где выполняется очень сильное предположение, заключающееся в том, что о распределении входных данных ничего не известно. Однако на практике такое редко встречается.

В статье Кутсупиаса и Пападимитриу предложены и исследованы два варианта уточнения подхода на базе конкурентного анализа, призванные устранить эти претензии. Первым из них является диффузная модель соперника, относящаяся к случаям, в которых о входных данных кое-что известно, а именно – их вероятностное распределение. Учитывая его, оценивается эффективность алгоритма в сравнении его ожидаемой стоимости со стоимостью оптимального алгоритма для входных данных, соответствующих этому распределению.

Второе уточнение носит название сравнительного анализа и основывается на понятии информационных режимов. В данном контексте конкурентный анализ определяется как сравнение между двумя информационными режимами – онлайновым и оффлайновым. Из него следует, что эти режимы являются только частными предельными случаями большого множества возможностей, среди которых, к примеру, имеется множество алгоритмов, заранее знающих некоторых префикс ожидающего входного значения (алгоритмов с ограниченным просмотром вперед).