Задача

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

Центральное место в таких приложениях занимает задача сравнения двух ран- жировок. Вы оцениваете множество из n фильмов, а система совместной фильтра- ции по своим базам данных ищет других людей с «похожими» оценками. Но как измерить сходство оценок двух людей на числовом уровне? Очевидно, идентичные оценки очень похожи, а полностью противоположные сильно различаются; нужна некая метрика, способная выполнять интерполяцию на середине шкалы.

Рассмотрим задачу сравнения двух ранжировок набора фильмов: вашей и чьей- то еще. Естественный метод — пометить фильмы от 1 до n в соответствии с вашей ранжировкой, затем упорядочить эти метки в соответствии с ранжировкой другого человека и посмотреть, сколько пар «нарушает порядок». Более конкретная фор- мулировка задачи выглядит так: имеется последовательность из n чисел a1, ..., an; предполагается, что все числа различны. Требуется определить метрику, которая сообщает, насколько список отклоняется от упорядочения по возрастанию; значе- ние метрики должно быть равно 0, если a1 < a2 < ...< an, и должно быть тем выше, чем сильнее нарушен порядок чисел.

Естественное количественное выражение этого понятия основано на подсчете инверсий.

Мы будем говорить, что два индекса i а, то есть если два элемента а. и а j идут «не по порядку». Нужно определить количе- ство инверсий в последовательности av ..., an.

Чтобы вы лучше поняли смысл определения, рассмотрим пример с последо- вательностью 2, 4, 1, 3, 5. В нем присутствуют три инверсии: (2, 1), (4, 1) и (4, 3). Также существует элегантный геометрический способ наглядного представления инверсий, изображенный на рис. 5.4: сверху записывается последовательность входных чисел в порядке, в котором они заданы, а ниже — эти же числа, упорядо- ченные по возрастанию. Затем каждое число соединяется отрезком со своей копией в нижнем списке. Каждая пересекающаяся пара отрезков соответствует одной паре, находящейся в обратном порядке в двух списках, — иначе говоря, инверсии.

5

5

Рис. 5.4. Подсчет инверсий в последовательности 2, 4, 1,3, 5. Каждая пересекающаяся пара отрезков соответствует паре, находящейся в обратном порядке во входном и упорядоченном

списках, — иначе говоря, инверсии

Обратите внимание, как количество инверсий плавно интерполируется между полным совпадением (когда последовательность упорядочена по возрастанию, инверсий нет) и полным несовпадением (если последовательность упорядочена по убыванию, каждая пара образует инверсию и общее количество инверсий

ар.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.
  17. Задачи и упражнения