Вопрос, пожалуй, несколько нестандартный, но может кто подскажет...
Есть такая задача: в небольшом населенном пункте прокладывается сеть, волокно (впрочем, это не очень принципиально). Топология — дерево с пассивными элементами и ограниченной каскадностью ( извините, если не очень грамотно выражаюсь, в терминологии пока не очень силен). Необходимо оценить число сплиттеров (разветвителей), их расположение, а также прикинуть расположение самого кабеля так, чтобы свести к минимуму расходы на оборудование и работы по прокладке. Насколько я знаю, такая работа часто выполняется вручную — "на глазок", но в данном случае требуется несколько автоматизировать процесс. В идеале нужен алгоритм, который при самых разнообразных начальных данных позволит выполнять такие оценки. Посоветуйте что-нибудь, plz. Хотя в каком направлении искать, алгоритмы из какой области могут здесь применяться. Интуиция подсказывает, что можно попробовать применить графы, рассматривать что-то вроде транспортной задачи или задачи коммивояжера. Но, может быть, кто-нибудь сможет дать более определенный ответ?
Заранее спасибо всем, кто откликнется.

Здравствуйте, WiP, Вы писали:

Есть множество неучитываемых факторов, например

Недовольство соседей
Там могут спереть, здесть нет
Стоимость лицензирования воздушки

Короче, если радиус больше 200м, то "на глазок" точнее всего.

Здравствуйте, WiP, Вы писали:

WiP> plz. Хотя в каком направлении искать, алгоритмы из какой области могут здесь применяться. Интуиция подсказывает, что можно попробовать применить графы, рассматривать что-то вроде транспортной задачи или задачи коммивояжера. Но, может быть, кто-нибудь сможет дать более определенный ответ?
WiP>Заранее спасибо всем, кто откликнется.
Задача коммивояжера — оно самое.

Здравствуйте, WiP, Вы писали:

WiP>Вопрос, пожалуй, несколько нестандартный, но может кто подскажет...
WiP>Есть такая задача: в небольшом населенном пункте прокладывается сеть, волокно ...коммивояжера. Но, может быть, кто-нибудь сможет дать более определенный ответ?
WiP>Заранее спасибо всем, кто откликнется.

По сути все можно свести к оптимизации решения задачи о многополюсной кратчайшей цепи на полном графе.
А можно и "на глазок" — берем какую — нибудь точку за центр сети, ведем из нее n ветвей, затем изо всех новых узлов ведем еще n/2 ветвей, затем n/4 и т. д. — должно получиться достаточно дешево и заодно довольно надежно.

Здравствуйте, Аноним, Вы писали:



А>Есть множество неучитываемых факторов, например

А>Недовольство соседей
А>Там могут спереть, здесть нет
А>Стоимость лицензирования воздушки

А>Короче, если радиус больше 200м, то "на глазок" точнее всего.

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

Здравствуйте, Grey2002, Вы писали:

WiP>>Вопрос, пожалуй, несколько нестандартный, но может кто подскажет...
WiP>>Есть такая задача: в небольшом населенном пункте прокладывается сеть, волокно ...коммивояжера. Но, может быть, кто-нибудь сможет дать более определенный ответ?
WiP>>Заранее спасибо всем, кто откликнется.

G>По сути все можно свести к оптимизации решения задачи о многополюсной кратчайшей цепи на полном графе.

G>А можно и "на глазок" — берем какую — нибудь точку за центр сети, ведем из нее n ветвей, затем изо всех новых узлов ведем еще n/2 ветвей, затем n/4 и т. д. — должно получиться достаточно дешево и заодно довольно надежно.

Нужно отдельно отметить, что топология сети — с ограниченной каскадностью. То есть для каждого сплиттера существует вполне определенное ограничение по количеству ветвлений. Один сплиттер может работать в режиме 1x32 -если речь идет о каналах до конечных пользователей или 1x8, если к нему подсоединяются 8 сплиттеров в режиме 1x4. То есть общее число ветвей, которые прямо или косвенно выходят из одного сплиттера не может превышать 32. Количество самих сплиттеров также очень важный фактор, поскольку затраты на них и магистральный канал от главного терминала до каждого сплиттера очень велики. Практически число сплиттеров — главный фактор, который должен оптимизироваться. Кроме того, сам кабель может прокладываться не где попало, а только вдоль дорог. Следует также учитывать, что переход через асфальт осуществляется с помощью горизонтальных проколов — это тоже отдельный денежный фактор. Существуют также принципиальные ограничения на количество каналов в одной магистрали.
В общем, много всего. Ко всему прочему, необходимо сделать оценку, насколько увеличатся расходы на прокладку, если изначально заложить в сеть значительные возможности для расширения.

Здравствуйте, WiP, Вы писали:

WiP>Здравствуйте, Grey2002, Вы писали:

WiP>>>Вопрос, пожалуй, несколько нестандартный, но может кто подскажет...
WiP>>>Есть такая задача: в небольшом населенном пункте прокладывается сеть, волокно ...коммивояжера. Но, может быть, кто-нибудь сможет дать более определенный ответ?
WiP>>>Заранее спасибо всем, кто откликнется.

G>>По сути все ...
G>>А можно и "на глазок" ... и заодно довольно надежно.

WiP>Нужно отдельно отметить, что топология сети — с ограниченной каскадностью. То есть ... одной магистрали.
WiP>В общем, много всего. Ко всему прочему, необходимо сделать оценку, насколько увеличатся расходы на прокладку, если изначально заложить в сеть значительные возможности для расширения.

Ну, практически любая топология имеет запас для расширения (кроме кольца, пожалуй), а по поводу ограничений — можно воспользоваться задачей о нахождении минимального пути со взыманием штрафа за разворот. — по сути то же самое, здесь главное — правильно сформулировать задачу в матенматической форме — то есть, как я это себе представляю, над задачей о нахождении кратчайшего пути можно навернуть задачу оптимизации (функции или функционала) + все то, что не учли в графе будет для этой задачи записываться в виде ограничений.

Здравствуйте, Grey2002, Вы писали:



G>Ну, практически любая топология имеет запас для расширения (кроме кольца, пожалуй), а по поводу ограничений — можно воспользоваться задачей о нахождении минимального пути со взыманием штрафа за разворот... над задачей о нахождении кратчайшего пути можно навернуть задачу оптимизации (функции или функционала) + все то, что не учли в графе будет для этой задачи записываться в виде ограничений.

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

Здравствуйте, WiP, Вы писали:

WiP>Здравствуйте, Grey2002, Вы писали:



G>>Ну, ... задачи записываться в виде ограничений.

WiP>Насчет задачи о нахождении минимального пути со взиманием платы за разворот чуть-чуть поподробнее, если можно. Про такую не слышал

Ну, постановок задачи о нахождении кратчайшего пути достаточно много, алгоритмов решения — тоже, а данная постановка называется по-научному так: "Задача о кратчайшем пути с фиксированными платежами". Такие задачи не могут решаться в соответствии с принципом динамического программирования Бэллмана — часть оптимального пути не всегда оптимальна. В качестве примера можно рассмотреть проезд по улицам, когда за разворот на перекрестках взымается плата (штраф).

Также для транспортных сетей (к которым отнасится и ваша задача) можно использовать решение задачи о кратчайшем остовном дереве, о многополюсном максимальном потоке (алг-м Гомори и Ху) и т. д.

Здравствуйте, Grey2002, Вы писали:

Типичная задача о кратчайшем оставном дереве!!