![]() |
|
![]() ![]() ![]() |
|
Radagast |
|
|||
Новичок Профиль Группа: Участник Сообщений: 2 Регистрация: 17.7.2008 Репутация: нет Всего: нет |
Есть набор датчиков в 2-мерном пространстве, для каждого заданы координаты (х,у). Есть набор точек (х,у) потенциального размещения станций беспроводной связи (WiFi/ZigBee/etc). Каждый датчик подсоединяется проводом макс. длиной L к ближайшей станции. Макс. радиус действия беспроводной связи (т.е. макс. расстояние между 2мя соседними станциями) = R. Естественно, что R >> L. Также установлено ограничение на макс. кол-во датчиков, подключенных к одной станции. Каждая станция должна находиться в области действия другой, т.е. в целом они должны образовывать связный граф, без "островков". Нужно оптимально разместить станции так, чтобы их было минимальное количество.
В дальнейшем эта задача будет усложняться (3-мерное пространство, ограничение по пропускной способности станций, возможность регулировать R для некоторых станций и т.д.), но нужно хотя бы решить в нынешней формулировке. Поиск в Гугле подсказал, что это - "задача размещения" (Facility location), но в ее формулировках (по крайней мере тех, что я нашел) важно лишь расположение станций относительно клиентов (в моем случае - датчиков), и не принимается во внимание расположение станций друг относительно друга. Скорее всего, на 1м этапе решается чисто Facility location (алгоритмы известны, жаль только, что они NP-hard), а потом если граф станций получился разъединенным, буду как-то подгонять размещение станций и добавлять новые. К сожалению, в универе я не уделял много внимания предметам по теории алгоритмов, линейному программированию, функциям оптимизации и пр. - сдал лабу и забыл ![]() Собственно вопросы такие: 1) Встречались ли вы с программами для автоматизированного проектирования сетей, которые сами рассчитывают оптимальное размещение узлов примерно по таким принципам, как я написал? 2) Какую литературу, сайты и ключевые слова для поиска можете подсказать? Можно и на русском, и на английском, я этот язык знаю достаточно хорошо. 3) и какие в общем возникают предположения, какими алгоритмами и методами лучше всего решить эту задачу? Какой мат. аппарат может в этом помочь? Заранее спасибо. Это сообщение отредактировал(а) Radagast - 28.11.2009, 00:07 |
|||
|
||||
KQT |
|
|||
Новичок Профиль Группа: Участник Сообщений: 14 Регистрация: 17.10.2007 Репутация: нет Всего: нет |
Задача (насколько я её понял: за чем нужны датчики - не догнал) об упаковке шаров, в предложеном случае - дисков на проскости. Фундаментальный труд по этой теме: Ласло Фейеш Тот "Расположение на плоскости на сфере и в пространстве" - рекомендую к прочтению.
В случае плоскости она решена: строго доказано, что круги расположенные в верщинах гексогональной рёшетки (в углах пчелиных сот) образуют оптимальное минимальное накрытие/плотнейшую упаковку. Малейшее шевеление условий задачи, например, если круги разноколиберные, приводит к NP-сложным агоритмам... Собственно, накой стоит вопрос сложности? Раз посчитал, вкопал вышки и загарай под вайфаем?.. Это сообщение отредактировал(а) KQT - 10.12.2009, 02:13 |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |