4551
правка
Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Альтернативные показатели эффективности онлайновых алгоритмов (посмотреть исходный код)
Версия от 23:27, 23 августа 2019
, 23 августа 2019→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Несмотря на то, что онлайновые алгоритмы изучались более тридцати…») |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
R = max | R = max | ||
A(x) opt(x) ; | A(x) opt(x) ; | ||
где x пробегает все возможные входные данные задачи, а A(x) и opt(x) представляют собой стоимость решений, полученных алгоритмом A, и оптимальный оффлайновый алгоритм для входного значения | где x пробегает все возможные входные данные задачи, а A(x) и opt(x) представляют собой стоимость решений, полученных алгоритмом A, и оптимальный оффлайновый алгоритм для входного значения x(1), соответственно. Это понятие может быть расширено для определения коэффициента конкурентности задачи как минимального коэффициента конкурентности алгоритма ее решения, а именно | ||
R = min RA = min max A Ax opt(x) | R = min RA = min max A Ax opt(x) | ||
1 Все задачи в данной статье предполагаются онлайновыми задачами минимизации, следовательно, цель заключается в минимизации затрат. Все представленные здесь результаты действительны и для онлайновых задач максимизации с соответствующими корректировками в определениях. | |||
Основная критика данного подхода заключалась в том, что из-за характерного пессимизма, присущего всем типам анализа наихудших вариантов, ему не удается различать алгоритмы, демонстрирующие разную эффективность при разных условиях. Кроме того, алгоритмам, которые «пытаются» работать лучше по сравнению со своими метриками для наихудшего случая, часто не удается показать эффективное поведение для различных «типичных» входных данных. Эти аргументы проще проверить в тех (редких) сценариях, где выполняется очень сильное предположение, заключающееся в том, что о распределении входных данных ничего не известно. Однако на практике такое редко встречается. | |||