Ещё раз оптимальный поиск наверх...

[Профессор Снэйп]

Предыдущую тему в Computer Science унесли, хотя задумывалась она немного не так. Ну да ладно, сформулируем всё по новому.

Задача такая. Человек стоит на $\mathbb{Z}^2$ в точке $(0,0)$. Перемещается по шагам. Из точки $(a,b)$ в точку $(c,d)$ можно сделать шаг тогда и только тогда, когда $|a-c| + |b-d| = 1$. Допустим, что человек голоден и что для некоторого $e \in \mathbb{Z}$ (про которое известно лишь то, что оно существует) множество точек, в которых находится еда, совпадает либо с $\{ (e,z) : z \in \mathbb{Z} \}$, либо с $\{ (z,e) : z \in \mathbb{Z} \}$. Каков оптимальный маршрут, выводящий человека к еде?

Честно говоря, не уверен, что постановка задачи вообще корректна. Ведь про $e$ ничего не известно!... С другой стороны, есть маршруты явно не оптимальные: например, $(0,0) \to (0,1) \to (0,0) \to (0,1) \to (1,1) \to \ldots$ содержит явно лишние шаги.

Попробуем для простоты рассмотреть одномерный случай. Ходим по $\mathbb{Z}$ из $0$ налево-направо, еда находится в точке $e \in \mathbb{Z}$. Мы не знаем, положительно $e$ или отрицательно, так что любой маршрут, гарантирующий поиск еды, выглядит так: $n_1$ шагов направо, $n_1+m_1$ шагов налево, $m_1 + n_2$ шагов направо, $n_2 + m_2$ шагов налево и т. д. для некоторых целочисленных последовательностей $0 < n_1 < n_2 < \ldots$, $0 < m_1 < m_2 < \ldots$. Как должны быть устроены эти две последовательности? За $2n_1 + 2m_1 + 2n_2 + \ldots + 2n_s + m_s$ шагов мы обходим все клетки в отрезке $[-m_s,n_s]$, всего $n_s + m_s + 1$ клетку. По-видимому, следует добиваться того, чтобы

$$ f(s) = \frac{n_s + m_s + 1}{2n_1 + 2m_1 + \ldots + 2n_s + m_s} $$

принимало как можно большие значения при достаточно больших $s$. Ясно, что $f(s)$ всегда меньше $1$ и что с ростом $s$ это значение можно сколь угодно быстро приближать к $1$, очень быстро увеличивая $m_s$ и очень медленно наращивая $n_s$. Но!.. в этом случае получается, что мы отдаём предпочтение отрицательным $e$ по сравнению с положительными. Хорош ли такой "перекос" влево?

Перекоса, безусловно, можно избежать, если очень быстро растить последовательность $n_1 < m_1 < n_2 < m_2 < n_3 < \ldots$. Но опять же насколько быстро? Пределов роста не существует. С одной стороны, чем быстрее растёт последовательность, тем быстрее движется к $1$ величина $f(s)$, тем лучше. Однако если рост очень велик, то уже на достаточно малых итерациях нашего челнокоподобного движения мы будем периодически убегать далеко в одну из сторон, забывая про другую. То есть опять будет постоянный "перекос" то влево, то вправо...

Есть ли смысл думать над лучшей мерой оптимальности, чем скорость роста $f(s)$, или задача, в-принципе, не формализуема?

[Sonic86]

Если задать вероятностное распределение для $e$, то можно, конечно, и побольше сказать, чем когда его нет...

[Профессор Снэйп]

Ну а нет вот никакого распределения! Все $e \in \mathbb{Z}$ равновероятны.

Кстати, это тоже ещё тот вопрос: что значит случайно выбрать $e \in \mathbb{Z}$, не отдавая никакого предпочтения одним числам перед другими. Счётно-аддитивную вероятностную меру, понятное дело, не построишь :) Так что аппарат тервера здесь во многом работать не будет. Но не факт, что постановка вопроса бессмысленна.

[Sonic86]

Профессор Снэйп писал(а):

Все $e \in \mathbb{Z}$ равновероятны.

А вот так как раз нельзя...

Профессор Снэйп писал(а):

Ну а нет вот никакого распределения!

Да, понял, так сложнее и интереснее...
Можно оценку сверху на число шагов в зависимости от $e$ сделать (ну $O(e^2)$ понятно)...

-- Чт янв 13, 2011 18:49:48 --

Вот такую меру оптимальности можно использовать: $g(n) = \frac{1}{2n+1} \sum\limits_{k=-n}^n c(k)$, где $c(k)$ - число шагов алгоритма до точки $k=e$.
Если для $n \geq n_0$ $g_2(n) \geq g_1(n)$, то алгоритм с функцией $g_1(n)$ лучше (не факт, что множество $g(n)$ имеет нижнюю грань...)

[Профессор Снэйп]

Sonic86 в сообщении #399331 писал(а):

А вот так как раз нельзя...

Кто-то из классиков (то ли Гёдель, то ли Тьюринг) как-то раз заморачивались на тему того, что значит случайное натуральное число. Давно читал уже статейку, лет 10 назад. В деталях не помню, но какие-то подходы были намечены.

Да и потом, есть же колмогоровская сложность и прочие подобные штуки. Тут, правда, наверное, всё же другое...

Вообще, когда мы говорим о распределении, подразумевается, что есть целое вероятностное пространство, на нём функция --- случайная величина и т. п. А тут нам просто дано одно-единственное число! Непонятно, о каком распределении речь.

[Circiter]

2Профессор Снэйп
А почему бы не сделать $n_i=m_i$, $n_{i+1}=n_i+1$? Это для 1D. В 2D надо будет бегать по почти тому-же алгоритму, но под 45 градусов к осям координат (по лесенке)...

[Профессор Снэйп]

Circiter в сообщении #399386 писал(а):

2Профессор Снэйп
А почему бы не сделать $n_i=m_i$, $n_{i+1}=n_i+1$? Это для 1D.

Ну... Я так понимаю, у Вас $n_1 = 1$. Давайте сравним с $n_1 = 1$, $m_i = 2n_i$, $n_{i+1} = 2m_i$.

Пусть $e > 0$. В Вашем случае оно достигается за

$$1 + 1 \cdot 4 + 1 + 2 \cdot 4 + 1 + 3 \cdot 4 + \ldots + (e-1) \cdot 4 + 1 = 2e(e-1)+e$$

шагов. В моём --- за

$$1 + (1 + 2) + (2 + 4) + (4 + 8) + \ldots + (2^{2k} + 2^{2k+1}) + 2^{2k+1} + e = (2 + 4 + 8 + \ldots + 2^{2k+2}) + e = 2^{2k+3}-2 + e$$

шагов, где $k$ таково, что $2^{2k} < e$ и $2^{2k+2} \geqslant e$. Из $2^{2k} < e$ получаем $2^{2k+3} - 2 < 8e$. Таким образом, все положительные $e$, для которых $2e^2 - 2e > 8e$ (то есть все $e > 5$), достигаются моим способом быстрее, чем Вашим!

С отрицательными та же история, можете проверить

[Circiter]

Все ясно; магия; так не честно.

[Xaliuss]

Просто надо определить критерий оптимальности. Для одномерного случая для каждого e и данного алгоритма $A$ определим $F(A,e)$ - число ходов, за которые алгоритм $A$ проходит и точку $+e$, и точку $-e$. В качестве критерия оптимальности думаю оптимально выбрать характеристику $G(A)=\sup_e\frac{F(A,e)}{e}$ - она заставляет следить за поведением алгоритма и при больших, и при малых $e$. Очевидно, что $F(A,e)\ge 3e$, поэтому $G(A)\ge 3$. Алгоритм с $n_s=2^{2s-2}$ и $m_s=2^{2s-1}$ дает $G(A)=9$ (экстремумы локальные достигаются на $e=2^s+1$, тогда$ F(A,e)=9\cdot 2^s-1$. Ставится вопрос о нахождении $\inf G(a)$, и тут надо думать... По идее должна идти какая-то геометрическая прогрессия, но надо считать.

[В.О.]

inf G(A) по А будет равен 3. Достигается на последовательности алгоритмов Ак, у которых каждый длинный шаг с фиксированным номером s стремится к бесконечности при к стремится к бесконечности. Для вычисления нужно переставить sup и inf.
Длинный шаг это суммарная длинна шагов сделанных подряд в одном направлении.

Вообще, для любого естественного симметричного критерия F(A,e) inf по алгоритмам А будет тривиальным.

Если, конечно, не ошибаюсь.

[Xaliuss]

Откуда 3? Если первый шаг больше 1, то $F(A,1)\ge 5$ Если же 1, то $F(A,2)\ge 8$, и $G(A)\ge 4$. Соответственно так можно сделать и для $e=3$ и $e=4$. Экстремальный алгоритм должен вести себя как прогрессия в каком-то смысле...

[В.О.]

Мы поменяли местами sup и inf. Вычислим inf F(A,e) по А при фиксированном е. Минимизирующий алгоритм: е шагов вправо и 2е шагов влево.
inf F(A,e) = 3е.

Теперь нужно рассмотреть произвольный "естественный" критерий G(A).

[Gortaur]

Оптимальность сложно исследовать раз критерия нет, но по-моему, двигаться неплохо по спирали.

[Gortaur]

Сглупил, признаю - даже движение по диагонали каждый раз с возвратом дает в два раза меньше шагов (хотя порядок все равно тот же).