2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 камни на доске
Сообщение26.09.2013, 16:46 
Экс-модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 17:01 
Заслуженный участник


08/04/08
8497
photon в сообщении #767985 писал(а):
на каждом шаге очищая предыдущие данные и записывая координаты новых чисел в coord
т.е. после $k$-го шага в массиве coord лежат только точки с номерами $k$?

photon в сообщении #767985 писал(а):
при этом за один шаг перемещаться можно на одну клетку в любом направлении, включая диагональные.
а можно только влево, вправо, вверх, вниз?

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 17:08 
Экс-модератор
Аватара пользователя


23/12/05
11395
Sonic86 в сообщении #767997 писал(а):
т.е. после $k$-го шага в массиве coord лежат только точки с номерами $k$?

да

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

Sonic86 в сообщении #767997 писал(а):
а можно только влево, вправо, вверх, вниз?
Нет, можно еще влево-вниз, влево-вверх, вправо-вниз, вправо-вверх:
photon в сообщении #767985 писал(а):
включая диагональные

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 17:22 
Заслуженный участник


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

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 17:28 
Заслуженный участник


08/04/08
8497
Можно явно подобрать "фрактальную" конфигурацию, в которой максимум составит $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}$, откуда получаем требуемое.

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 17:32 
Заслуженный участник


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

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 17:39 
Заслуженный участник


08/04/08
8497
venco в сообщении #768012 писал(а):
Можно подобрать нефрактальную конфигурацию, в которой максимум $4nm\over9$.
Пока не понял, как :-(
А если точка попала в массив, потом была стерта оттуда, то она потом туда снова может попасть или нет?

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 17:51 
Экс-модератор
Аватара пользователя


23/12/05
11395
Sonic86 в сообщении #768015 писал(а):
А если точка попала в массив, потом была стерта оттуда, то она потом туда снова может попасть или нет?


нет, на клетках, на которых мы уже побывали на каком-то шаге записаны номера этих шагов и туда идти нельзя:
photon в сообщении #767985 писал(а):
Затем, для всех клеток, координаты которых записаны в coord находим соседние клетки, на которых еще не написано число и не стоит камень, ставим там число на единицу больше

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 18:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 18:43 
Заслуженный участник


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

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 19:45 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 20:39 
Заслуженный участник


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

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 20:45 
Заслуженный участник


04/05/09
4487
Начинаем с конфигурации ($\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$.

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 20:55 
Заслуженный участник


28/04/09
1885
Null
Null в сообщении #768084 писал(а):
Кто-нибудь может показать рисунок где нужен массив больше $m+n$?
Вот тут на странице 14 нарисованы 2 примера фрактальных структур (правда, для досок, где у клетки только 4 соседа, т.е. по диагонали ходить нельзя).

 Профиль  
                  
 
 Re: камни на доске
Сообщение26.09.2013, 21:05 
Заслуженный участник


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

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

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

Код:
-*хххxxxx
-*х-----x
-*х-----x
-*х-*-*-x
-****-*xx
------*--
*****-*xx
-х----*-x
-х------x
-х------x
-xхххxxxx

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group