Помогите (+500 руб) решить задачу про дома на квадрат. участке

artur74

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

wawa321

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

artur74

Спасибо за ответ!
Задача из учебника Интрилигатора Mathematical optimization and economic theory. Раздел нелинейное программирование.

artur74

Скорее всего решается для произвольного N.

mtk79

нужно их смешать в кучу и потрясти всю коробку

BSCurt

Перед этим зарядив?!

dunkel68

учти, если у тебя практическая задача, на не теоретическая, то надо смотреть ещё на кучу факторов, снипов и прочей хрени

wawa321

Задача из учебника Интрилигатора Mathematical optimization and economic theory. Раздел нелинейное программирование.
Похоже, тебе надо не строгое доказательство, а численное оптимизирование?
Строгое доказательство легко получить только для малых N, ну может ещё для больших N специального вида. Для N=2013 навряд ли доказательство, если оно есть, будет простым :)
Если числено на компе гонять, то оптимальным заполнением скорее всего будет почти гексагональная решетка, модифицированная ближе к краям под конкретное N, что зависит от того насколько хорошо N кругов влезают в квадрат.

komBAR

Абсолютно уверен, что точный ответ для произвольных n не известен. Для маленьких n можно пытаться считать на компе. Но для квадратного тора (т.е. получающегося из квадрата отождествлением противоположных сторон) самые свежие результаты по такой задаче - это что-то типа n=9 или 10. С чего бы для квадрата это было проще, непонятно.
Если n стремится к бесконечности, то можно получить асимптотическую оценку с помощью гексагональной решетки.

artur74

Всем спасибо! Думал, что решение будет проще и для произвольного N.
Оставить комментарий
Имя или ник:
Комментарий: