Есть набор датчиков в 2-мерном пространстве, для каждого заданы координаты (х,у). Есть набор точек (х,у) потенциального размещения станций беспроводной связи (WiFi/ZigBee/etc). Каждый датчик подсоединяется проводом макс. длиной L к ближайшей станции.  Макс. радиус действия беспроводной связи (т.е. макс. расстояние между 2мя соседними станциями) = R. Естественно, что R >> L. Также установлено ограничение на макс. кол-во датчиков, подключенных к одной станции. Каждая станция должна находиться в области действия другой, т.е. в целом они должны образовывать связный граф, без "островков". Нужно оптимально разместить станции так, чтобы их было минимальное количество.

В дальнейшем эта задача будет усложняться (3-мерное пространство, ограничение по пропускной способности станций, возможность регулировать R для некоторых станций и т.д.), но нужно хотя бы решить в нынешней формулировке. Поиск в Гугле подсказал, что это - "задача размещения" (Facility location), но в ее формулировках (по крайней мере тех, что я нашел) важно лишь расположение станций относительно клиентов (в моем случае - датчиков), и не принимается во внимание расположение станций друг относительно друга. Скорее всего, на 1м этапе решается чисто Facility location (алгоритмы известны, жаль только, что они NP-hard), а потом если граф станций получился разъединенным, буду как-то подгонять размещение станций и добавлять новые.

К сожалению, в универе я не уделял много внимания предметам по теории алгоритмов, линейному программированию, функциям оптимизации и пр. - сдал лабу и забыл  моя нынешняя работа связана с построением GUI на C++. А вот моя дипломная работа будет по теме, описанной в первых 2 абзацах. И перед бесстрастной строкой поиска Гугла понимаю, что без достаточного опыта и знаний в этой области искать иголку в стоге сена буду доооооолго :(
Собственно вопросы такие:
1) Встречались ли вы с программами для автоматизированного проектирования сетей, которые сами рассчитывают оптимальное размещение узлов примерно по таким принципам, как я написал?
2) Какую литературу, сайты и ключевые слова для поиска можете подсказать? Можно и на русском, и на английском, я этот язык знаю достаточно хорошо.
3) и какие в общем возникают предположения, какими алгоритмами и методами лучше всего решить эту задачу? Какой мат. аппарат может в этом помочь?
Заранее спасибо.

Это сообщение отредактировал(а) Radagast - 28.11.2009, 00:07

Задача (насколько я её понял: за чем нужны датчики - не догнал) об упаковке шаров, в предложеном случае - дисков на проскости. Фундаментальный труд по этой теме: Ласло Фейеш Тот "Расположение на плоскости на сфере и в пространстве" - рекомендую к прочтению.

В случае плоскости она решена: строго доказано, что круги расположенные в верщинах гексогональной рёшетки (в углах пчелиных сот) образуют оптимальное минимальное накрытие/плотнейшую упаковку. Малейшее шевеление условий задачи, например, если круги разноколиберные, приводит к NP-сложным агоритмам... Собственно, накой стоит вопрос сложности? Раз посчитал, вкопал вышки и загарай под вайфаем?..

Это сообщение отредактировал(а) KQT - 10.12.2009, 02:13