Задача о размещении объектов, известная также как анализ расположения оборудования или задача k-центра, — это ветвь исследования операций и вычислительной геометрии, исследующей оптимальное расположение объектов с целью минимизировать цены перевозок с учётом таких ограничений, как размещение опасных материалов вблизи жилищ. Техника применима также к кластерному анализу.
Задача о размещении объектов с минимизацией
Простая задача о размещении объектов — это задача Вебера, в которой размещается один объект с целью минимизации взвешенной суммы расстояний до заданного множества точек. Более сложные задачи этой дисциплины возникают при ограничениях на размещение объектов и при использовании более сложных критерий оптимизации.
В базовой формулировке задача о размещении объектов состоит из потенциальных точек размещения L, где объекты могут быть открыты и точек D, которые должны быть обслужены. Цель — выбрать подмножество F точек размещения объектов с целью минимизировать сумму расстояний от каждой точки обслуживания до ближайшего обслуживающего объекта, плюс сумма стоимостей размещения объектов.
Задачу о размещении объектов на общих графах NP-трудно решить оптимально, и можно решить путём сведения (например) от задачи о покрытии множества. Было разработано несколько алгоритмов для задач о размещении объектов и многих вариантов этой задачи.
Без допущений о свойствах расстояний между клиентами и местами размещения объектов (в частности, без допущения, что расстояние удовлетворяет неравенству треугольника), задача известна как неметрическая задача о размещении объектов и она может быть аппроксимирования с множителем O(log n)[1]. Множитель тесен, что следует из сохраняющего аппроксимацию приведения[en] из задачи покрытия множества.
Если мы предполагаем, что расстояния между клиентами и местами размещения объектов неориентированны и удовлетворяют неравенству треугольника, мы говорим о задаче метрического размещения объектов (МРО). МРО остаётся NP-трудной задачей и её трудно аппроксимировать с множителем, лучшим 1.463[2]. На настоящее время лучший аппроксимационный алгоритм имеет коэффициент 1.488.[3].
Минимаксное размещение объектов
Минимаксная задача о размещении объектов ищет размещение, минимизирующее максимальные расстояния до мест размещения, где расстояние от некоторой точки до мест размещения — это расстояние от точки до ближайшего места размещения. Формальное определение следующее: Если задано множество точек P ⊂ ℝd, нужно найти множество точек S ⊂ ℝd, |S| = k, такое, что значение maxp ∈ P(minq ∈ S(d(p, q)) ) будет минимальным.
В случае евклидовой метрики при k = 1 задача известна как задача о наименьшей ограничивающей сфере или задача 1-центра. Изучение задачи прослеживается по меньшей мере до 1860 года, см. статью «Ограничивающая сфера» для деталей.
NP-трудность
Было доказано, что точное решение задачи k-центра является NP-трудной[4][5][6]. Было обнаружено, что аппроксимация задачи будет тоже NP-трудной, если ошибка мала. Уровень ошибки в аппроксимационном алгоритме измеряется коэффициентом аппроксимации, который определяется как отношение аппроксимированного решения к оптимальному. Было доказано, что аппроксимация задачи k-центра является NP-трудной, если коэффициент аппроксимации меньше, чем 1.822 (для размерности =2)[7] или 2 (для размерности >2)[6].
Алгоритмы
Точное решение
Существуют алгоритмы, дающие точное решение задачи. Один из таких алгоритмов даёт решение за время [8][9].
Аппроксимация 1 + ε
Аппроксимация 1 + ε находит решение с аппроксимационным коэффициентом, не превосходящим 1 + ε. Такая аппроксимация NP-трудна в случае произвольного ε. Был предложен подход, основанный на концепции базового набора[en], со сложностью выполнения [10]. Доступен альтернативный алгоритм, также базирующийся на базовых наборах. Он работает за время [11]. Автор утверждает, что время работы много меньше времени худшего случая и существует возможность решить некоторые задачи в случае малых k (скажем, k < 5).
Выделение отдалённых точек
Из-за трудности задачи непрактично искать точное решение или близкую аппроксимацию. Вместо этого для больших k широко используется аппроксимация с коэффициентом 2. Эта аппроксимация известна под названием «Алгоритм выделения отдалённых точек» (ВОТ = Farthest-point clustering, FPC) или как алгоритм обхода «сначала дальний»[en] [6]. Алгоритм довольно прост — выбираем произвольную точку множества как центр, находим самую дальнюю из оставшегося множества и считаем её следующим центром. Продолжаем процесс, пока не наберём k центров.
Легко видеть, что алгоритм работает за линейное время. Поскольку доказано, что аппроксимация с коэффициентом, меньшим 2, NP-трудна, ВОТ считается лучшей аппроксимацией.
Временная сложность выполнения позднее была улучшена до O(n log k) с помощью техники рамочной декомпозиции[7].
Максиминное размещение объектов
Задача максиминного размещения объектов ищет расположение, которое максимизирует минимальные расстояния до сторон. В случае евклидовой метрики задача известна как задача о наибольшей пустой сфере. Плоский случай (наибольшей пустой окружности[en]) может быть решён за время Θ(n \log n)[12][13].
Свободно распространяемое программное обеспечение для решения задач размещения объектов
| Название (в алфавитном порядке) |
Лицензия | Язык API | Краткая информация |
|---|---|---|---|
| FLP Spreadsheet Solver | Creative Commons Attribution 4.0 International License | Система на основе Microsoft Excel и VBA с открытым кодом для решения задачи о размещении объектов со ссылкой на ГИС общего доступа. link Видео уроки link [14]. | |
| ODL Studio | LGPL | Ограниченный кластерный компонент в ODL Studio решает задачу P-медианы (размещения с минимизацией взвешенной суммы расстояний). Программа включает планы размещения, отчёты и загрузку/выгрузку в Excel. | |
| SITATION | freeware | Может решать пяти классов задач, включая: P-медиана, P-центр, Покрытие множествами, Максимальное покрытие и Задача с фиксированными затратами без ограничения пропускной способности. [14] |
См. также
Примечания
- ↑ Hochbaum, 1982, p. 148–162.
- ↑ Guha, Khuller, 1999, p. 228.
- ↑ Li, 2011, p. 77–88.
- ↑ Fowler, Paterson, Tanimoto, 1981, p. 133–137.
- ↑ Megiddo, Tamir, 1982, p. 194–197.
- 1 2 3 Gonzalez, 1985, p. 293–306.
- 1 2 Feder, Greene, 1988, p. 434–444.
- ↑ Hwang, Lee, Chang, 1993, p. 1–22.
- ↑ Hwang, Chang, Lee, 1993, p. 398–423.
- ↑ Bādoiu, Har-Peled, Indyk, 2002, p. 250–257.
- ↑ Kumar & Kumar, 2010.
- ↑ Препарата и Шеймос, 1989.
- ↑ Toussaint, 1983, p. 347–358.
- 1 2 Csoke, 2015.
Литература
- Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М.: Мир, 1989. — ISBN 5-03-001041-6.
- Bādoiu M., Har-Peled S., Indyk P. Approximate clustering via core-sets // Proceedings of the thirty-fourth annual ACM symposium on Theory of Computing. — 2002. — P. 250–257.
- Csoke M. The Facility Location Problem. — Governors State University, 2015.
- Feder T., Greene D. Optimal algorithms for approximate clustering // 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:10.1016/0020-0190(81)90111-3.
- Gonzalez T. Clustering to minimize the maximum intercluster distance // Theoretical Computer Science. — 1985. — Vol. 38. — P. 293–306. — DOI:10.1016/0304-3975(85)90224-5. Архивировано 24 января 2013 года.
- Guha S., Khuller S. Greedy Strikes Back: Improved Facility Location Algorithms // Journal of Algorithms. — 1999. — Vol. 31. — P. 228. — DOI:10.1006/jagm.1998.0993.
- Hochbaum D. S. Heuristics for the fixed cost median problem // Mathematical Programming. — 1982. — Vol. 22. — P. 148–162. — DOI:10.1007/BF01581035.
- Hwang R. Z., Lee R. C. T., Chang R. C. The slab dividing approach to solve the Euclidean p-center problem // Algorithmica. — 1993. — Vol. 9, no. 1. — P. 1–22. — DOI:10.1007/BF01185335.
- Hwang R. Z., Chang R. C., Lee R. C. T. The generalized searching over separators strategy to solve some NP-Hard problems in subexponential time // Algorithmica. — 1993. — Vol. 9, no. 4. — P. 398–423. — DOI:10.1007/bf01228511.
- Kumar P., Kumar P. Almost optimal solutions to k-clustering problems // International Journal of Computational Geometry & Applications. — 2010. — Vol. 20, no. 4.
- Li Shi. A 1.488. Approximation Algorithm for the Uncapacitated Facility Location Problem // Automata, Languages and Programming. — Lecture Notes in Computer Science. — 2011. — Vol. 6756. — P. 77–88. — ISBN 978-3-642-22011-1. — DOI:10.1007/978-3-642-22012-8_5.
- Megiddo N., Tamir A. On the complexity of locating linear facilities in the plane // Operations Research Letters. — 1982. — Vol. 1, no. 5. — P. 194–197. — DOI:10.1016/0167-6377(82)90039-6.
- 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.
Ссылки
- INFORMS section on location analysis, профессиональное общество изучения проблем размещения.
- Библиография по задачам размещения, собранная Тревором Хале и содержащая более 3400 статей.
- Библиотека алгоритмов размещения
- Утилита размещения производства в Web-варианте)
- Оптимизатор производства размещения, основанное на MATLAB средство решения задач размещения производства.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .