Страница Алексея Яшунского

Задача о Васе в интернете.

Задача навеяна условием задачи "на соображение" из журнала Компьютерра. Программист Вася играет в интернете в такую игру: начиная с какой-то страницы он начинает ходить по страницам, переходя всегда по первой ссылке со страницы. Известно, что с каждой страницы есть хотя бы одна ссылка.

Как ему понять, что он уже "зациклился", если его браузер умеет сохранять только конечное число "закладок"? (в оригинальном условии — 2 закладки).

Участвовали: Володя, Лёша, Катя, Саша, Лена, Алёша, Настя, я.

Саша довольно быстро заметил, что на самом деле достаточно одной закладки, после чего мы занялись подсчётом сложности алгоритма в зависимости от размера и конфигурации той части сети, по которой Вася "путешествует".

Текст получился путаным, но, боюсь, что ничего более толкового я в ближайшее время не напишу, а потом — и подавно 🙁

Конфигурация той части сети, по которой будет ходить Вася, всегда состоит из начальной "предпериодической" последовательности из k страниц и цикла длины l, где k и l Васе неизвестны.

Алгоритм, позволяющий достоверно определить, что мы уже "зациклились", в общем виде выглядит следующим образом:

закладка обновляется в p-ый раз перед f(p)-ым шагом, где f(p) — функция, такая что f(p+1) - f(p) > f(p) - f(p-1), т.е. число переходов между двумя "заложенными" страницами возрастает. При этом до установки очередной закладки мы переходим между страницами, сравнивая каждую текущую с "заложенной".

Далее анализировался алгоритм, в котором число шагов между соседними закладками равно степени двойки, т.е. первая закладка ставится в самой первой вершине, вторая — через 1 вершину, третья — ещё через 2, потом через 4, через 8, и т.д. Таким образом в качестве функции f(p) была выбрана функция 2^p-1.

Возникает вопрос о том, сколько шагов потребуется такому алгоритму на сети с "хвостом" длины k и циклом длины l.

Легко заметить, что номер P первой закладки, попавшей в цикл, удовлетворяет неравенству
2^P-1 ≥ k. Наименьшее такое целое P = ]log₂(k+1)[.

Если 2^P ≥ l, то пройдя от закладки l шагов (ещё до установки следующей закладки) мы узнаем, что мы в цикле.

Если же 2^P < l, то сначала придётся довести номер закладки до Q, такого что 2^Q ≥ l. Наименьшее такое целое Q = ]log₂l[.

Обозначая число шагов на сети с хвостом из k страниц и циклом из l через S(k,l) получаем, что

S(k,l) = 2^{]log₂(k+1)[}-1+l при 2^{]log₂(k+1)[} ≥ l
S(k,l) = 2^]log₂l[-1+l при 2^{]log₂(k+1)[} < l

Пусть теперь k+l = n. Зафиксируем значение n и рассмотрим среднее число шагов по сетям с различными k и l, 0 ≤ k ≤ n-1.

где под S^*(k,n-k) понимается 2^{]log₂(k+1)[} или 2^{]log₂(n-k)[} в зависимости от соотношения между 2^{]log₂(k+1)[} и n-k.

Остаётся получить значение суммы S^*(k,n-k).

Заметим, что k+1 ≤ 2^{]log₂(k+1)[} ≤ 2(k+1).

Если k+1 ≥ n-k, то 2^{]log₂(k+1)[} тем более превышает n-k, а значит при k≥(n-1)/2 выполнено S^*(k,n-k) = 2^{]log₂(k+1)[}.

Если 2(k+1) < n-k, то 2^{]log₂(k+1)[} тем более не превышает n-k, а значит при k < (n-2)/3 выполнено S^*(k,n-k) = 2^{]log₂(n-k)[}.

"Сомнительным" для функции S^*(k,n-k) является только промежуток от (n-2)/3 до (n-1)/2, но на нём легко проверить выполнение оценки

2^{]log₂(k+1)[} ≤ S^*(k,n-k) ≤ 2^{]log₂(n-k)[}.

Таким образом,

В действительности, это суммы отличаются не больше, чем в одном слагаемом. Для того, чтобы их вычислить, получим формулу для

Обозначим ]log₂m[ через ψ. Тогда 2^ψ-1 < m ≤ 2^ψ, откуда следует, что в нашей сумме не более 2^ψ-1 слагаемых со значением 2^ψ (а на самом деле, за исключением последней группы слагаемых, их ровно 2^ψ-1).

Поэтому искомую сумму можно представить в виде

Обозначив ]log₂n[ через φ и выполнив кучу преобразований с полученной формулой, можно получить, что

Разделив сумму на n и с учётом уже полученного ранее добавка, получаем, что среднее время не превышает величины

Асимтотически эта оченка, по-видимому, колеблется от 7n/4 (для "хороших" n=2^s) до 2n (для "плохих" n=2^s+1).

Параллельно с приведённой выше кучей вычислений анализировался алгоритм, в котором функция f(p) основывалась на арифметической, а не на геометрической прогрессии, а найти требовалось не просто "вершину в цикле", но и значения параметров k и l. Для построенного там алгоритма среднее время (как утверждает Володя) получилось квадратичным по n.

По итогам всего написанного можно сформулировать некоторые открытые вопросы:

• Насколько точна полученная верхняя оценка для среднего времени? (Требуется куча аккуратных вычислений...?)
• Насколько лучше можно сделать результат, если использовать более одной закладки?
• Как можно ли оптимизировать время нахождения цикла, подбирая подходящую функцию для точек установки закладок? ("Арифметический" шаг, по-видимому, ухудшает дело. Возможно надо использовать "прогрессию" с основанием e? — такая идея озвучивалась...)
• Сколько шагов требуется для точного нахождения k и l? (И как на это влияет количество доступных закладок?)