Что читать дальше
Читатель сайта отметил несколько любимых страниц, и сайт хочет посоветовать, что читать дальше. Модель такая. Читатель бродит по ссылкам: на каждой странице с вероятностью d = 0,85 он идёт по одной из её ссылок, выбранной случайно и равновероятно, а с вероятностью 1 − d ему надоедает, и он открывает одну из своих любимых страниц, тоже случайно и равновероятно. Со страницы, где ссылок нет вовсе, он всегда открывает одну из любимых. Если бродить так очень долго, доля времени на каждой странице перестаёт меняться; это и есть её важность для этого читателя. Посоветуйте десять самых важных страниц, не считая любимых.
Два теста — граф ссылок трёх учебников этого сайта: курса CS, «Царицы наук» и каталога алгоритмов.
Вход
В первой строке n и m (2 ≤ n ≤ 10 000, 1 ≤ m ≤ 50 000) — число страниц и ссылок. Дальше m строк a b: ссылка со страницы a на страницу b (a ≠ b, одинаковых ссылок нет). В последней строке k (1 ≤ k < n) и k различных номеров любимых страниц.
Выход
Номера страниц, кроме любимых, в порядке убывания важности, по одному в строке: десять, а если страниц, кроме любимых, меньше десяти, — все. Тесты подобраны так, что важности первых одиннадцати страниц различаются больше чем на 10⁻⁷.
Примеры
Пример 1
6 8 1 2 1 3 2 3 3 4 4 5 5 2 4 6 2 6 1 1
3 2 4 6 5
Пример 2
7 8 1 2 2 3 2 4 4 5 5 6 6 4 3 7 1 7 2 1 3
7 4 2 5 6
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это PageRank, но прыжки — не на любую страницу, а только на любимые. Как изменится формула одного шага степенного метода?
2Подсказка 2
Куда девать важность страницы без ссылок? Прочитайте условие ещё раз: оттуда читатель всегда прыгает.
3Идея
Персонализированный PageRank. Вектор прыжков v равен 1/k на любимых страницах и нулю на остальных. Шаг: каждая страница со ссылками отдаёт долю d своей важности поровну по ссылкам; всё остальное — доля 1 − d у всех и вся важность страниц без ссылок, умноженная на d, — уходит на любимые страницы по вектору v. Повторяем, пока суммарное изменение не станет меньше 10⁻¹¹, и сортируем.
4Разбор
Почему сходится. Шаг — это линейное отображение, которое сохраняет сумму важностей, а разность двух распределений сжимает хотя бы в d раз: прыжки одинаковы для обоих, и меняется только та часть, что идёт по ссылкам. Значит, ошибка после t шагов не больше dt от начальной, и для точности 10⁻¹¹ хватает пары сотен шагов, а на практике меньше. Каждый шаг — O(n + m).
Любопытная деталь. Если важность страниц без ссылок просто терять, числа выйдут другими, но порядок страниц — тем же: такое решение отличается от правильного умножением всего вектора на одно число. Это верно именно потому, что потерянное здесь возвращается по тому же вектору v, что и прыжки скучающего читателя. А вот обычный PageRank с прыжками на любую страницу — уже другой ответ: в настоящем графе сайта он советует главы «Царицы наук», на которые много ссылаются все, а не статьи по соседству с прочитанным. Читателю, которому понравились статьи о поиске в ширину и в глубину, Дейкстре, топологической сортировке и остовных деревьях, правильный ответ первыми советует A*, двоичную кучу, главу курса «Шесть рукопожатий» и компоненты сильной связности.
4+Решение
5Сложность
O((n + m) · T), где T — число шагов, не больше log(10⁻¹¹) / log d ≈ 156 при d = 0,85; плюс сортировка O(n log n).
6Типичные ошибки
- Обычный PageRank. Прыжки на любую страницу — другой рейтинг, первый же пример.
- Мало шагов. Фиксированные десять-двадцать шагов не всегда успевают: оценка гарантирует лишь, что ошибка убывает хотя бы в 1/d ≈ 1,18 раза за шаг.
- Забыть исключить любимые. Они сами по себе важнее всех.