4551
правка
Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
Альтернативные показатели эффективности онлайновых алгоритмов (посмотреть исходный код)
Версия от 23:50, 23 августа 2019
, 23 августа 2019→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
Основная критика данного подхода заключалась в том, что из-за характерного пессимизма, присущего всем типам анализа наихудших вариантов, ему не удается различать алгоритмы, демонстрирующие разную эффективность при разных условиях. Кроме того, алгоритмам, которые «пытаются» работать лучше по сравнению со своими метриками для наихудшего случая, часто не удается показать эффективное поведение для различных «типичных» входных данных. Эти аргументы проще проверить в тех (редких) сценариях, где выполняется очень сильное предположение, заключающееся в том, что о распределении входных данных ничего не известно. Однако на практике такое редко встречается. | Основная критика данного подхода заключалась в том, что из-за характерного пессимизма, присущего всем типам анализа наихудших вариантов, ему не удается различать алгоритмы, демонстрирующие разную эффективность при разных условиях. Кроме того, алгоритмам, которые «пытаются» работать лучше по сравнению со своими метриками для наихудшего случая, часто не удается показать эффективное поведение для различных «типичных» входных данных. Эти аргументы проще проверить в тех (редких) сценариях, где выполняется очень сильное предположение, заключающееся в том, что о распределении входных данных ничего не известно. Однако на практике такое редко встречается. | ||
В статье Кутсупиаса и Пападимитриу предложены и исследованы два варианта уточнения подхода на базе конкурентного анализа, призванные устранить эти претензии. Первым из них является диффузная модель противника, относящаяся к случаям, в которых о входных данных кое-что известно, а именно – их вероятностное распределение. Учитывая его, оценивается эффективность алгоритма в сравнении его ожидаемой стоимости со стоимостью оптимального алгоритма для входных данных, соответствующих этому распределению. | |||
Второе уточнение носит название сравнительного анализа и основывается на понятии информационных режимов. В данном контексте конкурентный анализ определяется как сравнение между двумя информационными режимами – онлайновым и оффлайновым. Из него следует, что эти режимы являются только частными предельными случаями большого множества возможностей, среди которых, к примеру, имеется множество алгоритмов, заранее знающих некоторых префикс ожидающего входного значения (алгоритмов с ограниченным просмотром вперед). | |||
== Основные результаты == | |||