Задача про розміщення об'єктів

Зада́ча про розмі́щення об'є́ктів, відома також як ана́ліз розташува́ння обла́днання або зада́ча 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).

Вільно поширюване програмне забезпечення для розв'язування задач розміщення об'єктів

Назва (за абеткою)	Ліцензія	Мова API	Коротка інформація
FLP Spreadsheet Solver	Creative Commons Attribution 4.0 International License		Система на основі Microsoft Excel і VBA з відкритим кодом для розв'язування задачі про розміщення об'єктів із посиланням на ГІС загального доступу (посилання). Відео уроки [Архівовано 15 березня 2022 у Wayback Machine.] .
ODL Studio	LGPL		Обмежений кластерний компонент в ODL Studio розв'язує задачу про P-медіану (розміщення з мінімізацією зваженої суми відстаней). Програма включає плани розміщення, звіти та завантаження/вивантаження в Excel. (Уроки з ODL Studio [Архівовано 12 квітня 2022 у Wayback Machine.])
SITATION	freeware		Може розв'язувати задачі п'яти класів: P-медіана, P-центр, покриття множинами, максимальне покриття і задача з фіксованими витратами без обмеження пропускної здатності[1] [Архівовано 28 березня 2022 у Wayback Machine.].

Див. також

• Центр графа
• Квадратична задача про призначення
• Алгоритм Дейкстри
• Розташування об'єктів (конкурентна гра)

Література

• Препарата Ф., Шеймос М. . Вычислительная геометрия: Введение. — М. : Мир, 1989. — ISBN 5-03-001041-6. Архівовано з джерела 15 березня 2022
• 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. — 21 квітня. — С. 250–257. Архівовано з джерела 4 березня 2016. Процитовано 15 березня 2022.
• Csoke M. [2] — Governors State University, 2015. Архівовано з джерела 22 серпня 2020
• Feder T., Greene D. . Optimal algorithms for approximate clustering // Proceedings of the twentieth annual ACM symposium on Theory of Computing. — 1988. — 21 квітня. — С. 434–444. Архівовано з джерела 7 травня 2021. Процитовано 15 березня 2022.
• Fowler R. J., Paterson M. S., Tanimoto S. L. . Optimal packing and covering in the plane are NP-complete // Information Processing Letters. — 1981. — Т. 12 (21 квітня). — С. 133–137. — DOI:10.1016/0020-0190(81)90111-3.
• Gonzalez T. . Clustering to minimize the maximum intercluster distance // Theoretical Computer Science. — 1985. — Т. 38 (21 квітня). — С. 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. — Т. 31 (21 квітня). — С. 228. — DOI:10.1006/jagm.1998.0993.
• Hochbaum D. S. . Heuristics for the fixed cost median problem // Mathematical Programming. — 1982. — Т. 22 (21 квітня). — С. 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. — Т. 9, no. 1 (21 квітня). — С. 1–22. — DOI:10.1007/BF01185335. Архівовано з джерела 15 березня 2022. Процитовано 15 березня 2022.
• 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. — Т. 9, no. 4 (21 квітня). — С. 398–423. — DOI:10.1007/bf01228511. Архівовано з джерела 15 березня 2022. Процитовано 15 березня 2022.
• Kumar P., Kumar P. . Almost optimal solutions to k-clustering problems // International Journal of Computational Geometry & Applications. — 2010. — Т. 20, no. 4 (21 квітня). Архівовано з джерела 28 серпня 2010. Процитовано 15 березня 2022.
• Li Shi. . A 1.488. Approximation Algorithm for the Uncapacitated Facility Location Problem // Automata, Languages and Programming. — Lecture Notes in Computer Science. — 2011. — Т. 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. — Т. 1, no. 5 (21 квітня). — С. 194–197. — DOI:10.1016/0167-6377(82)90039-6. Архівовано з джерела 7 грудня 2012. Процитовано 15 березня 2022.
• Toussaint G. T. . Computing largest empty circles with location constraints // International Journal of Computer and Information Sciences. — 1983. — Т. 12, no. 5 (21 квітня). — С. 347–358.

Посилання

• INFORMS section on location analysis [Архівовано 24 лютого 2012 у Wayback Machine.], професійна спільнота з вивчення проблем розміщення.
• Бібліографія щодо задач розміщення, зібрана Тревором Гале, яка містить понад 3400 статей.
• Бібліотека алгоритмів розміщення
• Утиліта для розміщення виробництва (у вебваріанті).
• Оптимізатор розміщення виробництва [Архівовано 5 квітня 2022 у Wayback Machine.], заснований на MATLAB, засіб для розв'язування задач розміщення виробництва.