камни на доске

[photon]

Была алгоритмическая задачка, которая натолкнула меня на другую задачу, скорее математическую. Попытаюсь ее сформулировать.

Имеется прямоугольная доска $m\times n$ клеток. На некоторых клетках могут лежать камни, проход через такие клетки запрещен. Необходимо проложить кратчайший маршрут из левого верхнего в правый нижний угол (в этих двух угловых клетках камней точно нет), при этом за один шаг перемещаться можно на одну клетку в любом направлении, включая диагональные.
Решение организовано следующим образом: на текущей начальной клетке ставим единичку, затем на всех соседних, если они не заняты камнями и не выходят за края доски ставим двоечки, сохраняем координаты клеток, на которых проставили двойки, в отдельный временный массивчик coord (считаем, что для хранения координат одной клетки нужен один элемент этого массива). Затем, для всех клеток, координаты которых записаны в coord находим соседние клетки, на которых еще не написано число и не стоит камень, ставим там число на единицу больше и координаты этих новонайденных клеток снова сохраняем в наш массив coord. Так движемся по доске, проставляя новые числа по мере удаления от начальной точки, пока не дойдем до конечной точки, на каждом шаге очищая предыдущие данные и записывая координаты новых чисел в coord. Вопрос с том, какой минимальный размер coord является достаточным для хранения координат клеток для любого шага.

[Sonic86]

photon в сообщении #767985 писал(а):

на каждом шаге очищая предыдущие данные и записывая координаты новых чисел в coord

т.е. после $k$-го шага в массиве coord лежат только точки с номерами $k$?

photon в сообщении #767985 писал(а):

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

а можно только влево, вправо, вверх, вниз?

[photon]

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

т.е. после $k$-го шага в массиве coord лежат только точки с номерами $k$?

да

-- Thu Sep 26, 2013 16:21:22 --

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

а можно только влево, вправо, вверх, вниз?

Нет, можно еще влево-вниз, влево-вверх, вправо-вниз, вправо-вверх:

photon в сообщении #767985 писал(а):

включая диагональные

[venco]

Мне кажется, можно подобрать конфигурацию, которая потребует массив размера $\Omega(mn)$.
Вопрос только в ассимптотическом коэффициенте.

[Sonic86]

Можно явно подобрать "фрактальную" конфигурацию, в которой максимум составит $Cn^{\log_{2}3}$ ($m=n$), что меньше $\Omega(n^2)$ (как сделать последнюю, мне неведомо).

(тут сама конфигурация)

Нумеруем клетки парами точек.
$\Phi_1=\{(0;0)\}$
$\Phi_{n+1}=\Phi_0\cup (\Phi_n+c_n\cdot(1;1))\cup (\Phi_n+c_n\cdot(-1;1))\cup$
$\cup(\Phi_n+c_n\cdot(1;-1))\cup (\Phi_n+c_n\cdot(-1;-1))$. Здесь $A+c$ - сдвиг множества $A$ на вектор $c$.
Высота узорчика $h_n$ будет удовлетворять соотношению $h_{n+1}=2h_n+1$, т.е. $h_n=2^n-1$, а число клеток в крае, до которых мы дойдем на последнем шаге, будет равно $3^{n-1}$, откуда получаем требуемое.

[venco]

Можно подобрать нефрактальную конфигурацию, в которой максимум $4nm\over9$. Это с учётом подводящих линий ширины 3. На самом деле они будут толще, так что максимум будет меньше, но не принципиально.

[Sonic86]

venco в сообщении #768012 писал(а):

Можно подобрать нефрактальную конфигурацию, в которой максимум $4nm\over9$.

Пока не понял, как
А если точка попала в массив, потом была стерта оттуда, то она потом туда снова может попасть или нет?

[photon]

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

А если точка попала в массив, потом была стерта оттуда, то она потом туда снова может попасть или нет?

нет, на клетках, на которых мы уже побывали на каком-то шаге записаны номера этих шагов и туда идти нельзя:

photon в сообщении #767985 писал(а):

Затем, для всех клеток, координаты которых записаны в coord находим соседние клетки, на которых еще не написано число и не стоит камень, ставим там число на единицу больше

[venco]

Ну, с коэффициентом я ошибся немного, но порядок такой.
Идея такая - подводим линии в центр к одинаковым квадратным ячейкам. Каждая ячейка заполняется к стенкам и в конце потребует $4s-11$ элементов, где $s$ - нечётный размер ячейки.
Подводящии линии надо синхронизировать, так что их толщина увеличивается лоарифмически. Размер ячеек надо тоже увеличивать, чтобы их доля во всём поле не убывала. Так что рост будет медленный.
Попробую картинку нарисовать.

[EtCetera]

Можно найти оценку сверху для константы при $mn$, рассматривая последовательность длин фронтов волны как геометрическую прогрессию со знаменателем $x-1$ ($x$ $\text{---}$ число соседей у клетки, в данном случае $x=8$). Получается чуть больше $1-\frac{1}{x-1}=\frac{6}{7}$. Так что есть, куда стремиться .

[venco]

Придумал фрактальную структуру, которая сходится к $3\over16$.

-- Чт сен 26, 2013 13:26:19 --

Ещё лучше - $1\over5$.

[Null]

Кто-нибудь может показать рисунок где нужен массив больше $m+n$?

[venco]

Начинаем с конфигурации ($\frac{15}{42} = \frac 5 {14}$):

----*--
***-*xx
х-*-*-x
х-----x
х-----x
хххxxxx

Вход - левый верхний угол, * - камни, х - требуемый фронт.
Теперь многократно делаем такую операцию:
1. отражаем наверх относительно первой строки:

хххxxxx
х-----x
х-----x
х-*-*-x
***-*xx
----*--
***-*xx
х-*-*-x
х-----x
х-----x
хххxxxx

2 пристраиваем две колонки слева с коридором:

-*хххxxxx
-*х-----x
-*х-----x
-*х-*-*-x
-****-*xx
------*--
*****-*xx
--х-*-*-x
--х-----x
--х-----x
--хххxxxx

Новое отношение $\frac{30}{99} = \frac{10}{33}$.
В следующий раз отражаем налево и пристраиваем коридор сверху.
Предельная доля фронта в поле - $3\over14$.

[EtCetera]

Null

Null в сообщении #768084 писал(а):

Кто-нибудь может показать рисунок где нужен массив больше $m+n$?

Вот тут на странице 14 нарисованы 2 примера фрактальных структур (правда, для досок, где у клетки только 4 соседа, т.е. по диагонали ходить нельзя).

[venco]

Я выше пропустил одну точку фронта, на самом деле предел чуть-чуть больше - $3\over14$.

-- Чт сен 26, 2013 14:20:55 --

После первого отражения можно убрать один камень и улучшить предел до $31\over140$:

-*хххxxxx
-*х-----x
-*х-----x
-*х-*-*-x
-****-*xx
------*--
*****-*xx
-х----*-x
-х------x
-х------x
-xхххxxxx