Алгоритмы без обратной связи (с сайта А.В.Шаповалова)

[Rak so dna]

EUgeneUS в сообщении #1613663 писал(а):

В "пошаговом алгоритме", без явного выражения значений в виде последовательности, от выбора начального шага ничего не зависит. Точнее: от выбора начального шага зависят все остальные, но его можно выбрать любым.

Я не про начальный шаг (в моем решении от него тоже ничего не зависит). Я о том, что можно выбрать такую последовательность шагов полиции, при которой не зависимо от соотношений скоростей, мы гарантированно догоним вора. Например, в моём решении, если мы фиксируем $a,$ то можно подобрать такое $\frac{v_1}{v_0}<1,$ что вор не будет пойман при некоторых начальных условиях.

[EUgeneUS]

Rak so dna в сообщении #1613665 писал(а):

. Я о том, что можно выбрать такую последовательность шагов полиции, при которой не зависимо от соотношений скоростей, мы гарантированно догоним вора.

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

[Rak so dna]

mihaild хорошо вот у нас конфигурация $X_n$ (пусть мы её угадали). Начинаем для неё перебор начальных клеток. Пусть реально мы находимся в клетке $z,$ а начинаем перебор, предполагая, что находимся в клетке $a.$ После выполнения программы мы оказываемся в клетке $c.$ Теперь мы запускаем программу для клетки $b,$ и так случилось, что после её выполнения мы оказались в клетке $a.$ Но программа для клетки $a$ уже отработала...

[mihaild]

Rak so dna в сообщении #1613667 писал(а):

хорошо вот у нас конфигурация $X_n$ (пусть мы её угадали). Начинаем для неё перебор начальных клеток

mihaild в сообщении #1613664 писал(а):

конфигурация - схема лабиринта + начальное положение

Если мы угадали схему и начальную клетку, то мы можем правильно определить, в какой клетке мы находимся.

[Rak so dna]

mihaild тут то ли Вы меня не понимаете, то ли я Вас. В общем моя мысль в том, что

mihaild в сообщении #1613664 писал(а):

конфигурация - схема лабиринта + начальное положение

постоянно изменяется из-за отсутствия возможности (по крайней мере очевидной) вернуть "всё как было", а значит при переборе, мы просто можем "перескочить" через правильный вариант.

[mihaild]

Rak so dna, я думаю, что Вы меня:)
Чуть формальнее (и с небольшими переобозначениями):
Пусть $(Y_i, c_i)$, $i > 0$ - последовательность всех возможных пар ("схема лабиринта", "клетка"). Пусть $f(\bar a, Y, c)$ - клетка, куда мы приходим, выполнив последовательность команд $\bar a$, в схеме $Y$, начиная с клетки $c$. Пусть $g(Y, d)$ - последовательность команд, обходящая все возможные клетки в схеме $Y$, стартуя в клетке $d$.
Тогда определим инструкции циклически: $\bar a_0 = \lambda$, $\bar a_n = \bar a_{n - 1} + g(Y_n, f(\bar a_{n - 1}, Y_n, c_n))$. Тогда, если настоящая конфигурация, предоставленная Васей, $(Y_i, c_i)$, то мы обойдем всё что можно на $i$-м шаге.

Нам не нужно ничего возвращать (хотя и можно), мы в каждый момент представляем что настоящая исходная конфигурация какая-то, и действуем в ней.

[Rak so dna]

mihaild хорошо, давайте для простоты считать, что конфигурацию лабиринта мы знаем. Далее происходит следующее:

Rak so dna в сообщении #1613667 писал(а):

Пусть реально мы находимся в клетке $z,$ а начинаем перебор, предполагая, что находимся в клетке $a.$ После выполнения программы мы оказываемся в клетке $c.$ Теперь мы запускаем программу для клетки $b,$ и так случилось, что после её выполнения мы оказались в клетке $a.$ Но программа для клетки $a$ уже отработала...

Что нам гарантирует, что запуская дальше программы для клеток $c,d,..,z$ вы сможем выполнить обход (ведь мы сейчас в клетке $a$) ?

[mihaild]

Rak so dna в сообщении #1613672 писал(а):

Что нам гарантирует, что запуская дальше программы для клеток $c,d,..,z$ вы сможем выполнить обход (ведь мы сейчас в клетке $a$) ?

Мы не запускаем программу для клетки $b$.
На первом шаге мы запускаем программу для клетки $a$.
На втором шаге мы запускаем программу для той клетки, в которой мы должны быть сейчас, если начальная клетка была $b$.
На третьем шаге мы запускаем программу для той клетки, в которой мы должны быть сейчас, если начальная клетка была $c$.
В какой-то момент мы дойдем до клетки, с которой на самом деле начинали (не текущую итерацию, а вообще весь алгоритм), правильно определим, в какой клетке мы сейчас, и обойдем всё.
Обратите внимание, что в моей формализации, вторым аргументом $g$ является $f(\bar a_{n - 1}, Y_n, c_n)$ - клетка, в которой мы оказались, если настоящая начальная клетка $c_n$, а не просто $c_n$.

[Rak so dna]

mihaild да, теперь понял, что Вы имели ввиду.

[TOTAL]

1. В четвёртой задаче всю инструкцию разбиваем на последовательность инструкций для каждого возможного лабиринта (даже для всего лишь каждой связной области, которых меньше, чем лабиринтов).
2. Для конкретной области записываем инструкцию A с клетки 1. Затем инструкцию B с клетки, в которую попадаем после A, если в A залезли на клетку 2. Затем инструкцию С с клетки, в которую попадаем после AB, если в A залезли на клетку 3. Затем инструкцию D с клетки, в которую попадаем после ABC, если в A залезли на клетку 4. И т.д.

[Rak so dna]

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

[TOTAL]

Цитата:

9. На бесконечной шахматной доске находятся ферзь и невидимый король, которому запрещено ходить по диагонали. Они ходят по очереди. Может ли ферзь ходить так, чтобы король рано или поздно попал под шах? (Е.Черепанов)

Ферзь - в начале координат. Предполагая, что король изначально на расстоянии 10 шагов от начала координат, прыгаем по диагонали в первый квадрант на 11. Затем по диагонали с шагом 1 идём обратно, чтобы замести короля (чуть больше 20 шагов потребуется). Если король ускользнул, то предполагаем, что король изначально на расстоянии 100 шагов от начала координат. Прыгаем куда надо и т.д.

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

[mihaild]

sergey1 в сообщении #1613636 писал(а):

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

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

[Rak so dna]

mihaild в сообщении #1613679 писал(а):

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

Наверное можно так: Есть кротчайший маршрут, соединяющий две клетки (для определенности возьмём последовательность ходов, чтобы первая клетка зашла на вторую). Повторяя конечное число раз этот маршрут, получим, что клетки рано или поздно совпадут, уперевшись в границы, зациклится они ведь не могут (хотя это, наверное, не очевидно).

[mihaild]

Rak so dna в сообщении #1613685 писал(а):

зациклится они ведь не могут (хотя это, наверное, не очевидно)

Не очевидно, и тут нужно как-то существенно использовать свойства графа: если у нас вместо лабиринта ориентированный цикл, то синхронизирующей последовательности нет.