Задача покрытия области мин числом одинаковых кругов.

[eugrita]

Полная постановка задачи, интересна для практического применения -мобильной или радио-связи но сложна. В некоторых работах рассматриваются постановки для областей в виде т.н. ортогональных полигонов с препятствиями. Я ставлю задачу
1)практического нахождения и расчета оптимальных покрытий сначала для простейших областей - прямоугольника и круга
Допущения.
Из всего множества вариантов покрытий выберем только T- и Q - решетки. Т.е треугольные и прямоугольные
Покрытие T1 - любые 3 попарно смежные узла решетки – вершины равностороннего треугольника со стороной $\sqrt{3}$
Покрытие Q1 - любые 4 попарно смежные узла решетки – вершины квадрата со стороной $\sqrt{2}$
1)Простейшая область - прямоугольник со сторонами a,b

Асимптотические оценки количеств покрытий при увеличении R/r показывает преимущество Т-покрытий.
Некую сложность составляет сравнение нескольких разновидностей Q- и R-покрытий. Так, если обозначить $ n_0=[D]=[2R] $
а $ny,nx$ - количества интервалов между рядами и столбцами то возможны 3 варианта Q-покрытий
1)$nx=ny=n__$ 2)$nx=n_0 , ny=n_0-1$ 3)$nx=ny= n_0-1$ При этом кажущийся выигрыш за счет уменьшения кол-ва внутренних точек в 3 вар компенсируется
увеличением в этом же случае необходимых внешних точек для обеспечения полного покрытия границ круга.
В случае треугольной решетки также возможно 3 варианта - 1)узел в центре обл.$w=h=0$ , 2)середина ребра в центре обл $w=\sqrt{3}/2, h=0$
3)ц.т. треугольника в центре обл $w=\sqrt{3}/2, h=0.5$
Полный расчет и сравнение всех вариантов - некий начальный но законченный этап работы.
Результаты в виде сравнительных графиков приведены ниже



-----------------------------------------------------------------------------------------
2 этап. - расчет Q- и T-покрытий для выпуклых многоугольных областей.
Алгоритм так же как и ранее разбивается на 2 части
а)расчет количества внутренних точек решетки б)расчет необходимого числа внешних точек для покрытия приграничной области
-----------------------------------------------------------------------------------------
ВОПРОСЫ.
1)Проекту не хватает математической строгости. Приняты искусственные допущения об поиске оптимума только в классах чисто прямоугольных и треугольных решетках. Комбинирование не допускается.
2)Вопрос практического применения. Хотелось бы если заниматься, то действительно задачей с практическим применением.
А тогда надо учитывать как любые пожелания заказчика, т.е. на яз.математики - произвольные области, в т.ч. не выпуклые, в т.ч. с искусственными
препятствиями, в т.ч с некоторыми обязательными узлами (в жизни - транслятор на вершине горы)
3)Тянут ли полученные результаты 1 этапа (расчеты и сравнения для Q- и R-областей) на курсовую? на статью?
4)Данная задача относится к классу т.н. комбинаторной оптимизации. Допустимы ли как в этой так и в схожих задачах раскроя уменьшение вариантов перебора с помощью искусственно введенных и необоснованных допущений (1)?

-- Пт апр 12, 2013 19:36:22 --

5)сложность задачи резко возрастает уже для многоугольных областей:
Каждая решетка характеризуется 3 непрерывными параметрами
h, w - смещения узла по горизонтали (вертикали) относительно фиксированной точки (ранее центр круга)
$\varphi$ -угол поворота решетки (или области относительно
горизонтально-расположенной решетки)

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

[B@R5uk]

Если необходимо построить алгоритм, который для фиксироанной произвольной области строит весьма приличный вариант размещения, но не важно время рассчёта -- то воспользуйтесь методом Монте-Карло.

Если нужно САМОЕ оптимальное с математической строгостью решение -- то это уже не программистский вопрос.

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

[B@R5uk]

Я тут ещё одну концепцию придумал. Вернее вспомнил её существование, так как она лежит в основе игры "Майнкрафт". Коль скоро решение приблизительное, то не обязательно работать с правильными геометрическими фигурами. Их можно представить в виде "кубиков". В нашем случае все фигуры станут матрицами с цифрами. А с матрицами работать одно удовольствие.

Вот накатал в MATLABе за пару часиков примеры с прямоугольными областями:

К сожалению, на форуме нету тэга "спойлер", чтобы спрятать картинки

Работа с областями не прямоугольной формы допиливается без проблем.

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

[Pavlovsky]

А зачем все так сложно? Чем вам не нравится покрытие плоскости правильными шестиугольниками? Собственно название "сотовая связь" произошло от этого алгоритма.

[eugrita]

Здесь попытка рассмотрения общей задаче мин покрытия любой многоугольной области (пока хотя бы выпуклой) треугольным покрытием. Ясно что 6-угольники в общем случае дают лишние точки. Для круга еще куда ни шло - может быть 6-угольные

[Aritaborian]

B@R5uk в сообщении #709727 писал(а):

К сожалению, на форуме нету тэга "спойлер", чтобы спрятать картинки

Есть тег [off].