Interested Article - Задача о размещении объектов
- 2020-12-31
- 1
Задача о размещении объектов , известная также как анализ расположения оборудования или задача 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) .
Алгоритмы
Точное решение
Существуют алгоритмы, дающие точное решение задачи. Один из таких алгоритмов даёт решение за время .
Аппроксимация 1 + ε
Аппроксимация 1 + ε находит решение с аппроксимационным коэффициентом, не превосходящим 1 + ε . Такая аппроксимация NP-трудна в случае произвольного ε . Был предложен подход, основанный на концепции , со сложностью выполнения . Доступен альтернативный алгоритм, также базирующийся на базовых наборах. Он работает за время . Автор утверждает, что время работы много меньше времени худшего случая и существует возможность решить некоторые задачи в случае малых k (скажем, k < 5).
Выделение отдалённых точек
Из-за трудности задачи непрактично искать точное решение или близкую аппроксимацию. Вместо этого для больших k широко используется аппроксимация с коэффициентом 2. Эта аппроксимация известна под названием «Алгоритм выделения отдалённых точек» (ВОТ = Farthest-point clustering, FPC) или как алгоритм . Алгоритм довольно прост — выбираем произвольную точку множества как центр, находим самую дальнюю из оставшегося множества и считаем её следующим центром. Продолжаем процесс, пока не наберём k центров.
Легко видеть, что алгоритм работает за линейное время. Поскольку доказано, что аппроксимация с коэффициентом, меньшим 2, NP-трудна, ВОТ считается лучшей аппроксимацией.
Временная сложность выполнения позднее была улучшена до O( n log k ) с помощью техники рамочной декомпозиции .
Максиминное размещение объектов
Задача максиминного размещения объектов ищет расположение, которое максимизирует минимальные расстояния до сторон. В случае евклидовой метрики задача известна как задача о наибольшей пустой сфере . Плоский случай ( ) может быть решён за время Θ( n \log n) .
Свободно распространяемое программное обеспечение для решения задач размещения объектов
Название
(в алфавитном порядке) |
Лицензия | Язык API | Краткая информация |
---|---|---|---|
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.
Ссылки
- , профессиональное общество изучения проблем размещения.
- , собранная Тревором Хале и содержащая более 3400 статей.
- , основанное на MATLAB средство решения задач размещения производства.
- 2020-12-31
- 1