Оптимальный дизайн сети
Оптимальное проектирование сети является проблемой комбинаторной оптимизации . Это абстрактное представление проблемы, с которой сталкиваются штаты и муниципалитеты при планировании своей дорожной сети. Учитывая набор мест, которые можно соединить дорогами, цель состоит в том, чтобы между каждыми двумя точками было короткое расстояние. Более конкретно, цель состоит в том, чтобы минимизировать сумму кратчайших расстояний, где сумма берется по всем парам точек. Для каждых двух локаций указано число, обозначающее стоимость строительства прямой дороги между ними. Необходимо принять решение о том, какие дороги строить при фиксированном бюджете.
Формальное определение
[ редактировать ]Входными данными для задачи оптимального проектирования сети является взвешенный граф 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. Цель состоит в том, чтобы найти возможная сеть с минимальной общей стоимостью.
Результаты
[ редактировать ]Джонсон, Ленстра и Кан доказывают, что проблема NP-трудна даже для простого случая, когда все веса ребер равны, а бюджет ограничивает выбор остовными деревьями. [ 1 ]
Дионн и Флориан изучили алгоритмы ветвей и границ и показали, что они работают за разумное время на входных данных среднего размера, но не на больших входных данных. Поэтому они представили эвристические алгоритмы аппроксимации . [ 2 ]
Аншелевич, Дасгупта, Тардос и Векслер изучают игру по проектированию сети, в которой каждый агент имеет набор терминалов и хочет построить сеть, в которой его терминалы будут соединены, но платить как можно меньше. Они изучают вычислительную проблему проверки существования равновесия по Нэшу . Для некоторых особых случаев они предлагают алгоритм с полиномиальным временем, который находит (1+ε) -приблизительное равновесие по Нэшу. [ 3 ]
Боффи и Хинксман представляют эвристический метод и показывают, что он дает результаты высокого качества. Они также изучают методы решения, основанные на методе ветвей и границ, и оценивают эффекты различных приближений при вычислении нижних границ. Они также обобщают проблему на сети, в которых стоимость строительства линий связи не пропорциональна длине, а требования к поездкам не все одинаковы. [ 4 ]
См. также
[ редактировать ]- Планирование и проектирование сети
- Связующее дерево с минимальной стоимостью маршрутизации — аналогичная задача, в которой выбранный набор должен быть связующим деревом.
Ссылки
[ редактировать ]- ^ Джонсон, Д.С.; Ленстра, Дж. К.; Кан, AHG Ринной (декабрь 1978 г.). «Сложность проблемы проектирования сети» (PDF) . Сети . 8 (4): 279–285. дои : 10.1002/net.3230080402 .
- ^ Дионн, Р.; Флориан, М. (март 1979 г.). «Точные и приближенные алгоритмы оптимального проектирования сети». Сети . 9 (1): 37–59. дои : 10.1002/net.3230090104 .
- ^ Аншелевич, Эллиот; Дасгупта, Анирбан; Тардос, Ева; Векслер, Том (2003). «Почти оптимальный проект сети с эгоистичными агентами». Материалы тридцать пятого ежегодного симпозиума ACM по теории вычислений . стр. 511–520. дои : 10.1145/780542.780617 . ISBN 1-58113-674-9 .
- ^ Боффи, ТБ; Хинксман, AI (сентябрь 1979 г.). «Решение задачи оптимальной сети». Европейский журнал операционных исследований . 3 (5): 386–393. дои : 10.1016/0377-2217(79)90118-8 .