4551
правка
Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Альтернативные показатели эффективности онлайновых алгоритмов (посмотреть исходный код)
Версия от 14:52, 26 октября 2019
, 26 октября 2019нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | |||
Диффузная модель соперника для онлайновых алгоритмов; сравнительный анализ онлайновых алгоритмов | |||
== Постановка задачи == | == Постановка задачи == | ||
Несмотря на то, что онлайновые алгоритмы изучались более тридцати лет, явное введение ''конкурентного анализа'' в основополагающих статьях Слейтора и Тарьяна [8] и Манасса, Макгиоха и Слейтора [6] привело к взрывному росту объема исследований этого класса задач и алгоритмов, и с тех пор оба понятия (онлайновые алгоритмы и конкурентный анализ) остаются тесно связанными друг с другом. Однако уже на раннем этапе этих исследований возникли вопросы к реалистичности и практичности модели, связанные главным образом с ее пессимизмом. Эта характеристика в некоторых случаях сказывается на способности модели к различению хороших и плохих алгоритмов. В статье 1994 года «За пределами конкурентного анализа» [3] Кутсупиас и Пападимитриу предложили и исследовали два альтернативных показателя эффективности онлайновых алгоритмов, тесно связанные с конкурентным анализом и при этом лишенные вышеупомянутых слабостей. Окончательная версия этой работы вышла в 2000 году [4]. | Несмотря на то, что онлайновые алгоритмы изучались более тридцати лет, явное введение ''конкурентного анализа'' в основополагающих статьях Слейтора и Тарьяна [8] и Манасса, Макгиоха и Слейтора [6] привело к взрывному росту объема исследований этого класса задач и алгоритмов, и с тех пор оба понятия (онлайновые алгоритмы и конкурентный анализ) остаются тесно связанными друг с другом. Однако уже на раннем этапе этих исследований возникли вопросы к реалистичности и практичности модели, связанные главным образом с ее пессимизмом. Эта характеристика в некоторых случаях сказывается на способности модели к различению хороших и плохих алгоритмов. В статье 1994 года «За пределами конкурентного анализа» [3] Кутсупиас и Пападимитриу предложили и исследовали два альтернативных показателя эффективности онлайновых алгоритмов, тесно связанные с конкурентным анализом и при этом лишенные вышеупомянутых слабостей. Окончательная версия этой работы вышла в 2000 году [4]. | ||
В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его всемогущего соперника на входных данных, относящихся к наихудшему случаю. Коэффициент конкурентоспособности алгоритма A определяется как наихудшее возможное отношение <math>R_A = max_x \frac{A(x)}{opt(x)}</math>, где x пробегает все возможные входные данные задачи, а A(x) и opt(x) представляют собой стоимость решений, полученных алгоритмом A | В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его всемогущего соперника на входных данных, относящихся к наихудшему случаю. Коэффициент конкурентоспособности алгоритма A определяется как наихудшее возможное отношение <math>R_A = max_x \frac{A(x)}{opt(x)}</math>, где x пробегает все возможные входные данные задачи, а A(x) и opt(x) представляют собой стоимость решений, полученных алгоритмом A и оптимальным оффлайновым алгоритмом для входного значения x, соответственно. [''Все задачи в данной статье предполагаются онлайновыми задачами минимизации, следовательно, цель заключается в минимизации затрат. Все представленные здесь результаты действительны и для онлайновых задач максимизации с соответствующими корректировками в определениях'']. Это понятие может быть расширено для определения коэффициента конкурентоспособности задачи как минимального коэффициента конкурентоспособности алгоритма ее решения, а именно <math>R = min_A R_A = min_A max_x \frac{A(x)}{opt(x)}.</math> | ||