Завдання про розміщення об'єктів
Завдання про розміщення об'єктів з мінімізацією
Проста задача про розміщення об'єктів - це завдання Вебера. в якій розміщується один об'єкт з метою мінімізації зваженої суми відстаней до заданої множини точок. Більш складні завдання цієї дисципліни виникають при обмеженнях на розміщення об'єктів і при використанні більш складних критерій оптимізації.
У базовій формулюванні завдання про розміщення об'єктів складається з потенційних точок розміщення 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].
Існують алгоритми, що дають точне рішення задачі. Один з таких алгоритмів дає рішення за час n O (k)>) >> [8] [9].
Апроксимація 1 + ε
Виділення віддалених точок
Через труднощі завдання непрактично шукати точне рішення або близьку апроксимацію. Замість цього для великих k широко використовується апроксимація з коефіцієнтом 2. Ця апроксимація відома під назвою «Алгоритм виділення віддалених точок» (ВОТ = Farthest-point clustering, FPC) або як алгоритм обходу «спочатку дальній» [en] [6]. Алгоритм досить простий - вибираємо довільну точку безлічі як центр, знаходимо найдальшу з залишився безлічі і вважаємо її наступним центром. Продовжуємо процес, поки не наберемо k центрів.
Легко бачити, що алгоритм працює за лінійний час. Оскільки доведено, що апроксимація з коефіцієнтом, меншим 2, NP-важка, ОСЬ вважається кращою апроксимацією.
Тимчасова складність виконання пізніше була поліпшена до O (n log k) за допомогою техніки рамкової декомпозиції [7].
Максимін розміщення об'єктів
Завдання максимінної розміщення об'єктів шукає розташування, яке максимізує мінімальні відстані до сторін. У разі евклідової метрики завдання відома як задача про найбільшу порожній сфері [en]. Плоский випадок (найбільшою порожній окружності [en]) може бути вирішене за час Θ (n \ log n) [12] [13].
Вільне програмне забезпечення для вирішення завдань розміщення об'єктів