Оптимальная конструкция сети

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

Формальное определение

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

Допустимая сеть — это подмножество 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]

Смотрите также

Планирование и проектирование сети
Минимальная стоимость маршрутизации по остовному дереву – похожая задача, в которой выбранный набор должен быть остовным деревом.

Ссылки

^ Джонсон, Д.С.; Ленстра, Дж.К.; Кан, А.Х.Г. Ринной (декабрь 1978 г.). «Сложность проблемы проектирования сетей» (PDF) . Сети . 8 (4): 279–285 . doi :10.1002/net.3230080402.
^ Дионн, Р.; Флориан, М. (март 1979). «Точные и приближенные алгоритмы для оптимального проектирования сетей». Networks . 9 (1): 37–59 . doi :10.1002/net.3230090104.
^ Аншелевич, Эллиот; Дасгупта, Анирбан; Тардос, Ева; Векслер, Том (2003). «Почти оптимальная конструкция сети с эгоистичными агентами». Труды тридцать пятого ежегодного симпозиума ACM по теории вычислений . С. 511– 520. doi :10.1145/780542.780617. ISBN 1-58113-674-9.
^ Боффи, ТБ; Хинксман, АИ (сентябрь 1979 г.). «Решение проблемы оптимальной сети». Европейский журнал операционных исследований . 3 (5): 386– 393. doi :10.1016/0377-2217(79)90118-8.

[1] Джонсон, Д.С.; Ленстра, Дж.К.; Кан, А.Х.Г. Ринной (декабрь 1978 г.). «Сложность проблемы проектирования сетей» (PDF) . Сети . 8 (4): 279–285 . doi :10.1002/net.3230080402.

[2] Дионн, Р.; Флориан, М. (март 1979). «Точные и приближенные алгоритмы для оптимального проектирования сетей». Networks . 9 (1): 37–59 . doi :10.1002/net.3230090104.

[3] Аншелевич, Эллиот; Дасгупта, Анирбан; Тардос, Ева; Векслер, Том (2003). «Почти оптимальная конструкция сети с эгоистичными агентами». Труды тридцать пятого ежегодного симпозиума ACM по теории вычислений . С. 511– 520. doi :10.1145/780542.780617. ISBN 1-58113-674-9.

[4] Боффи, ТБ; Хинксман, АИ (сентябрь 1979 г.). «Решение проблемы оптимальной сети». Европейский журнал операционных исследований . 3 (5): 386– 393. doi :10.1016/0377-2217(79)90118-8.