Русская Википедия:Задача о размещении объектов
Задача о размещении объектов, известная также как анализ расположения оборудования или задача k-центра, — это ветвь исследования операций и вычислительной геометрии, исследующей оптимальное расположение объектов с целью минимизировать цены перевозок с учётом таких ограничений, как размещение опасных материалов вблизи жилищ. Техника применима также к кластерному анализу.
Задача о размещении объектов с минимизацией
Простая задача о размещении объектов — это задача Вебера, в которой размещается один объект с целью минимизации взвешенной суммы расстояний до заданного множества точек. Более сложные задачи этой дисциплины возникают при ограничениях на размещение объектов и при использовании более сложных критерий оптимизации.
В базовой формулировке задача о размещении объектов состоит из потенциальных точек размещения L, где объекты могут быть открыты и точек D, которые должны быть обслужены. Цель — выбрать подмножество F точек размещения объектов с целью минимизировать сумму расстояний от каждой точки обслуживания до ближайшего обслуживающего объекта, плюс сумма стоимостей размещения объектов.
Задачу о размещении объектов на общих графах NP-трудно решить оптимально, и можно решить путём сведения (например) от задачи о покрытии множества. Было разработано несколько алгоритмов для задач о размещении объектов и многих вариантов этой задачи.
Без допущений о свойствах расстояний между клиентами и местами размещения объектов (в частности, без допущения, что расстояние удовлетворяет неравенству треугольника), задача известна как неметрическая задача о размещении объектов и она может быть аппроксимирования с множителем O(log n)Шаблон:Sfn. Множитель тесен, что следует из Шаблон:Не переведено 5 из задачи покрытия множества.
Если мы предполагаем, что расстояния между клиентами и местами размещения объектов неориентированны и удовлетворяют неравенству треугольника, мы говорим о задаче метрического размещения объектов (МРО). МРО остаётся NP-трудной задачей и её трудно аппроксимировать с множителем, лучшим 1.463Шаблон:Sfn. На настоящее время лучший аппроксимационный алгоритм имеет коэффициент 1.488.Шаблон:Sfn.
Минимаксное размещение объектов
Минимаксная задача о размещении объектов ищет размещение, минимизирующее максимальные расстояния до мест размещения, где расстояние от некоторой точки до мест размещения — это расстояние от точки до ближайшего места размещения. Формальное определение следующее: Если задано множество точек P ⊂ ℝd, нужно найти множество точек S ⊂ ℝd, |S| = k, такое, что значение maxp ∈ P(minq ∈ S(d(p, q)) ) будет минимальным.
В случае евклидовой метрики при k = 1 задача известна как задача о наименьшей ограничивающей сфере или задача 1-центра. Изучение задачи прослеживается по меньшей мере до 1860 года, см. статью «Ограничивающая сфера» для деталей.
NP-трудность
Было доказано, что точное решение задачи k-центра является NP-труднойШаблон:SfnШаблон:SfnШаблон:Sfn. Было обнаружено, что аппроксимация задачи будет тоже NP-трудной, если ошибка мала. Уровень ошибки в аппроксимационном алгоритме измеряется коэффициентом аппроксимации, который определяется как отношение аппроксимированного решения к оптимальному. Было доказано, что аппроксимация задачи k-центра является NP-трудной, если коэффициент аппроксимации меньше, чем 1.822 (для размерности =2)Шаблон:Sfn или 2 (для размерности >2)Шаблон:Sfn.
Алгоритмы
Точное решение
Существуют алгоритмы, дающие точное решение задачи. Один из таких алгоритмов даёт решение за время <math>n^{O(\sqrt{k})}</math>Шаблон:SfnШаблон:Sfn.
Аппроксимация 1 + ε
Аппроксимация 1 + ε находит решение с аппроксимационным коэффициентом, не превосходящим 1 + ε. Такая аппроксимация NP-трудна в случае произвольного ε. Был предложен подход, основанный на концепции Шаблон:Не переведено 5, со сложностью выполнения <math>O(2^{O(k \log k/\varepsilon^2)}dn)</math>Шаблон:Sfn. Доступен альтернативный алгоритм, также базирующийся на базовых наборах. Он работает за время <math>O(k^n)</math> Шаблон:Sfn. Автор утверждает, что время работы много меньше времени худшего случая и существует возможность решить некоторые задачи в случае малых k (скажем, k < 5).
Выделение отдалённых точек
Из-за трудности задачи непрактично искать точное решение или близкую аппроксимацию. Вместо этого для больших k широко используется аппроксимация с коэффициентом 2. Эта аппроксимация известна под названием «Алгоритм выделения отдалённых точек» (ВОТ = Farthest-point clustering, FPC) или как алгоритм Шаблон:Не переведено 5 Шаблон:Sfn. Алгоритм довольно прост — выбираем произвольную точку множества как центр, находим самую дальнюю из оставшегося множества и считаем её следующим центром. Продолжаем процесс, пока не наберём k центров.
Легко видеть, что алгоритм работает за линейное время. Поскольку доказано, что аппроксимация с коэффициентом, меньшим 2, NP-трудна, ВОТ считается лучшей аппроксимацией.
Временная сложность выполнения позднее была улучшена до O(n log k) с помощью техники рамочной декомпозицииШаблон:Sfn.
Максиминное размещение объектов
Задача максиминного размещения объектов ищет расположение, которое максимизирует минимальные расстояния до сторон. В случае евклидовой метрики задача известна как задача о наибольшей пустой сфере. Плоский случай (Шаблон:Не переведено 5) может быть решён за время Θ(n \log n)Шаблон:SfnШаблон:Sfn.
Свободно распространяемое программное обеспечение для решения задач размещения объектов
| Название (в алфавитном порядке) |
Лицензия | Язык API | Краткая информация |
|---|---|---|---|
| FLP Spreadsheet Solver | Creative Commons Attribution 4.0 International License | Система на основе Microsoft Excel и VBA с открытым кодом для решения задачи о размещении объектов со ссылкой на ГИС общего доступа. link Видео уроки link Шаблон:Sfn. | |
| ODL Studio | LGPL | Ограниченный кластерный компонент в ODL Studio решает задачу P-медианы (размещения с минимизацией взвешенной суммы расстояний). Программа включает планы размещения, отчёты и загрузку/выгрузку в Excel. [1] | |
| SITATION | freeware | Может решать пяти классов задач, включая: P-медиана, P-центр, Покрытие множествами, Максимальное покрытие и Задача с фиксированными затратами без ограничения пропускной способности. [2] Шаблон:Sfn |
См. также
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
Ссылки
- INFORMS section on location analysis, профессиональное общество изучения проблем размещения.
- Библиография по задачам размещения, собранная Тревором Хале и содержащая более 3400 статей.
- Библиотека алгоритмов размещения
- Утилита размещения производства в Web-варианте)
- Оптимизатор производства размещения, основанное на MATLAB средство решения задач размещения производства.
