Оптимальный дизайн сети ⇐ Васина Википедия

[wiki_en]

'''Оптимальное проектирование сети''' является проблемой комбинаторной оптимизации. Это абстрактное представление проблемы, с которой сталкиваются штаты и муниципалитеты при планировании своей дорожной сети. Нам дан набор локаций, которые мы хотели бы соединить дорогами. Для каждых двух локаций у нас есть число, обозначающее стоимость строительства прямой дороги между ними. У нас есть фиксированный бюджет, и мы должны решить, какие дороги построить на этот бюджет. Цель состоит в том, чтобы расстояние между каждыми двумя точками было коротким. Более конкретно, цель состоит в том, чтобы минимизировать «сумму» кратчайших расстояний, где сумма берется по всем парам точек.

== Формальное определение ==
Входными данными для задачи оптимального проектирования сети является взвешенный граф G = (V,E), где вес каждого ребра (u,v) в графе представляет стоимость строительства дороги от u до v; и бюджет «Б».

«Возможная сеть» — это подмножество S в E, такое, что сумма w(u,v) для всех (u,v) в S не превосходит B, и существует путь между любыми двумя узлами u и v (то есть S содержит остовное дерево G).

Для каждой допустимой сети S «общая стоимость» S представляет собой сумму по всем парам (u,v) в E длины кратчайшего пути от u до v, который использует только ребра. в S. Цель состоит в том, чтобы найти осуществимую сеть с минимальной общей стоимостью.

== Результаты ==
Джонсон, Ленстра и Кан
Дионн и Флориан
Аншелевич, Дасгупта, Тардос и Векслер
Боффи и Хинксманhttps://www.sciencedirect.com/science/article/a ... 1779901188 представляют эвристический метод и показывают, что он дает результаты высокого качества. Они также изучают методы решения, основанные на методе ветвей и границ, и оценивают эффекты различных приближений при вычислении нижних границ. Они также обобщают проблему на сети, в которых стоимость строительства линии связи не пропорциональна длине, а требования к отключению не все одинаковы.

== См. также ==

* Планирование и проектирование сети
*Связующее дерево с минимальной стоимостью маршрутизации — аналогичная задача, в которой выбранный набор должен быть связующим деревом.

Комбинаторная оптимизация
Сети
Транспорт
Связующее дерево

Подробнее: https://en.wikipedia.org/wiki/Optimal_network_design