Interested Article - Задача о размещении объектов

Задача о размещении объектов , известная также как анализ расположения оборудования или задача k -центра , — это ветвь исследования операций и вычислительной геометрии , исследующей оптимальное расположение объектов с целью минимизировать цены перевозок с учётом таких ограничений, как размещение опасных материалов вблизи жилищ. Техника применима также к кластерному анализу .

Задача о размещении объектов с минимизацией

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

В базовой формулировке задача о размещении объектов состоит из потенциальных точек размещения L , где объекты могут быть открыты и точек D , которые должны быть обслужены. Цель — выбрать подмножество F точек размещения объектов с целью минимизировать сумму расстояний от каждой точки обслуживания до ближайшего обслуживающего объекта, плюс сумма стоимостей размещения объектов.

Задачу о размещении объектов на общих графах NP-трудно решить оптимально, и можно решить путём сведения (например) от задачи о покрытии множества . Было разработано несколько алгоритмов для задач о размещении объектов и многих вариантов этой задачи.

Без допущений о свойствах расстояний между клиентами и местами размещения объектов (в частности, без допущения, что расстояние удовлетворяет неравенству треугольника ), задача известна как неметрическая задача о размещении объектов и она может быть аппроксимирования с множителем O(log n ) . Множитель тесен, что следует из из задачи покрытия множества.

Если мы предполагаем, что расстояния между клиентами и местами размещения объектов неориентированны и удовлетворяют неравенству треугольника, мы говорим о задаче метрического размещения объектов (МРО) . МРО остаётся NP-трудной задачей и её трудно аппроксимировать с множителем, лучшим 1.463 . На настоящее время лучший аппроксимационный алгоритм имеет коэффициент 1.488. .

Минимаксное размещение объектов

Минимаксная задача о размещении объектов ищет размещение, минимизирующее максимальные расстояния до мест размещения, где расстояние от некоторой точки до мест размещения — это расстояние от точки до ближайшего места размещения. Формальное определение следующее: Если задано множество точек P ⊂ ℝ ^d , нужно найти множество точек S ⊂ ℝ ^d , | S | = k , такое, что значение max _{p

∈

P} (min _{q

∈

S} (d( p , q )) ) будет минимальным.

В случае евклидовой метрики при k = 1 задача известна как задача о наименьшей ограничивающей сфере или задача 1-центра . Изучение задачи прослеживается по меньшей мере до 1860 года, см. статью « Ограничивающая сфера » для деталей.

NP-трудность

Было доказано, что точное решение задачи k -центра является NP-трудной . Было обнаружено, что аппроксимация задачи будет тоже NP-трудной, если ошибка мала. Уровень ошибки в аппроксимационном алгоритме измеряется коэффициентом аппроксимации , который определяется как отношение аппроксимированного решения к оптимальному. Было доказано, что аппроксимация задачи k -центра является NP-трудной, если коэффициент аппроксимации меньше, чем 1.822 (для размерности =2) или 2 (для размерности >2) .

Алгоритмы

Точное решение

Существуют алгоритмы, дающие точное решение задачи. Один из таких алгоритмов даёт решение за время $n^{O({\sqrt {k}})}$ .

Аппроксимация 1 + ε

Аппроксимация 1 + ε находит решение с аппроксимационным коэффициентом, не превосходящим 1 + ε . Такая аппроксимация NP-трудна в случае произвольного ε . Был предложен подход, основанный на концепции , со сложностью выполнения $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ . Доступен альтернативный алгоритм, также базирующийся на базовых наборах. Он работает за время $O(k^{n})$ . Автор утверждает, что время работы много меньше времени худшего случая и существует возможность решить некоторые задачи в случае малых k (скажем, k < 5).

Выделение отдалённых точек

Из-за трудности задачи непрактично искать точное решение или близкую аппроксимацию. Вместо этого для больших k широко используется аппроксимация с коэффициентом 2. Эта аппроксимация известна под названием «Алгоритм выделения отдалённых точек» (ВОТ = Farthest-point clustering, FPC) или как алгоритм . Алгоритм довольно прост — выбираем произвольную точку множества как центр, находим самую дальнюю из оставшегося множества и считаем её следующим центром. Продолжаем процесс, пока не наберём k центров.

Легко видеть, что алгоритм работает за линейное время. Поскольку доказано, что аппроксимация с коэффициентом, меньшим 2, NP-трудна, ВОТ считается лучшей аппроксимацией.

Временная сложность выполнения позднее была улучшена до O( n log k ) с помощью техники рамочной декомпозиции .

Максиминное размещение объектов

Задача максиминного размещения объектов ищет расположение, которое максимизирует минимальные расстояния до сторон. В случае евклидовой метрики задача известна как задача о наибольшей пустой сфере . Плоский случай ( ) может быть решён за время Θ( n \log n) .

Свободно распространяемое программное обеспечение для решения задач размещения объектов

Название (в алфавитном порядке)	Лицензия	Краткая информация
FLP Spreadsheet Solver	Creative Commons Attribution 4.0 International License	Система на основе Microsoft Excel и VBA с открытым кодом для решения задачи о размещении объектов со ссылкой на ГИС общего доступа. Видео уроки .
ODL Studio	LGPL	Ограниченный кластерный компонент в ODL Studio решает задачу P-медианы (размещения с минимизацией взвешенной суммы расстояний). Программа включает планы размещения, отчёты и загрузку/выгрузку в Excel.
SITATION	freeware	Может решать пяти классов задач, включая: P-медиана, P-центр, Покрытие множествами, Максимальное покрытие и Задача с фиксированными затратами без ограничения пропускной способности.

См. также

Примечания

, p. 148–162.
, p. 228.
, p. 77–88.
, p. 133–137.
, p. 194–197.
↑ , p. 293–306.
↑ , p. 434–444.
, p. 1–22.
, p. 398–423.
, p. 250–257.
.
.
, p. 347–358.
↑ .

Литература

Препарата Ф., Шеймос М. . . — М. : Мир , 1989. — ISBN 5-03-001041-6 .
Bādoiu M., Har-Peled S., Indyk P. // Proceedings of the thirty-fourth annual ACM symposium on Theory of Computing. — 2002. — P. 250–257.
Csoke M. . — Governors State University, 2015.
Feder T., Greene D. // Proceedings of the twentieth annual ACM symposium on Theory of Computing. — 1988. — P. 434–444.
Fowler R. J., Paterson M. S., Tanimoto S. L. Optimal packing and covering in the plane are NP-complete // Information Processing Letters. — 1981. — Vol. 12. — P. 133–137. — doi : .
Gonzalez T. // . — 1985. — Vol. 38. — P. 293–306. — doi : . 24 января 2013 года.
Guha S., Khuller S. Greedy Strikes Back: Improved Facility Location Algorithms // Journal of Algorithms. — 1999. — Vol. 31. — P. 228. — doi : .
Hochbaum D. S. Heuristics for the fixed cost median problem // . — 1982. — Vol. 22. — P. 148–162. — doi : .
Hwang R. Z., Lee R. C. T., Chang R. C. // Algorithmica. — 1993. — Vol. 9, no. 1. — P. 1–22. — doi : .
Hwang R. Z., Chang R. C., Lee R. C. T. // Algorithmica. — 1993. — Vol. 9, no. 4. — P. 398–423. — doi : .
Kumar P., Kumar P. // International Journal of Computational Geometry & Applications. — 2010. — Vol. 20, no. 4.
Li Shi. . // Automata, Languages and Programming. — . — 2011. — Vol. 6756. — P. 77–88. — ISBN 978-3-642-22011-1 . — doi : .
Megiddo N., Tamir A. // Operations Research Letters. — 1982. — Vol. 1, no. 5. — P. 194–197. — doi : .
Toussaint G. T. Computing largest empty circles with location constraints // International Journal of Computer and Information Sciences. — 1983. — Vol. 12, no. 5. — P. 347–358.