Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Зада ча про розмі щення об є ктів відома також як ана ліз розташува ння обла днання або зада ча k це нтра це гілка дослі

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

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

Зада́ча про розмі́щення об'є́ктів, відома також як ана́ліз розташува́ння обла́днання або зада́ча k-це́нтра — це гілка дослідження операцій і обчислювальної геометрії, яка досліджує оптимальне розташування об'єктів з метою мінімізувати ціни перевезень з урахуванням таких обмежень, як розміщення небезпечних матеріалів поблизу житла та об'єктів конкурентів. Ці методи також знаходять застосування у кластерному аналізі.

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

Проста задача про розміщення об'єктів — це задача Вебера, в якій розміщується один об'єкт з метою мінімізації зваженої суми відстаней до заданої множини точок. Складніші завдання цієї дисципліни виникають за обмежень на розміщення об'єктів і за використання складніших критеріїв оптимізації.

У базовому формулюванні задача про розміщення об'єктів складається з потенційних точок забудови L, де об'єкти можуть бути створені, і точок D, які слід обслужити. Мета — вибрати підмножину F точок розміщення об'єктів з метою мінімізувати суму відстаней від кожної точки обслуговування до найближчого обслуговувального об'єкта, плюс суму вартостей розміщення об'єктів.

Задачу про розміщення об'єктів на загальних графах NP-складно розв'язати оптимально, зведенням, наприклад, від задачі про покриття множини. Розроблено кілька алгоритмів для задач про розміщення об'єктів і багатьох варіантів цієї задачі.

Без припущень про властивості відстаней між клієнтами та місцями розташування об'єктів (зокрема, без допущення, що відстань задовольняє нерівність трикутника), задача відома як неметри́чна зада́ча про розмі́щення об'є́ктів і її можна апроксимувати з множником O (log n). Множник тісний, що випливає зі [en] із задачі покриття множини.

Якщо ми припускаємо, що відстані між клієнтами та місцями розміщення об'єктів неорієнтовані й задовольняють нерівність трикутника, ми говоримо про задачу метри́чного розмі́щення об'є́ктів (МРО). МРО залишається NP-складною задачею і її важко апроксимувати зі множником, кращим ніж 1,463. На даний час кращий апроксимаційний алгоритм має коефіцієнт 1,488.

Мінімаксне розміщення об'єктів

Мініма́ксна зада́ча про розмі́щення об'є́ктів шукає розміщення, яке мінімізує максимальні відстані до місць розміщення, де відстань від деякої точки до місць розміщення — це відстань від точки до найближчого місця розміщення. Формальне визначення таке: Якщо задано множину точок P ⊂ ℝd, потрібно знайти множину точок S ⊂ ℝd, |S| = k, таку, що значення maxp ∈ P(minq ∈ S(d(p, q))) буде мінімальним.

У разі евклідової метрики при k = 1 задача відома як задача про найменшу обмежувальну сферу або задача про 1-центр. Вивчення задачі простежується щонайменше до 1860 року, див. докладніше в статті «Обмежувальна сфера».

NP-складність

Доведено, що точне розв'язання задачі k-центра є NP-складним. Виявлено, що апроксимація задачі буде теж NP-складною, якщо похибка мала. Рівень похибки в апроксимаційному алгоритмі вимірюється коефіцієнтом апроксимації, який визначається як відношення апроксимованого розв'язку до оптимального. Доведено, що апроксимація задачі k-центра є NP-складною, якщо коефіцієнт апроксимації менший, ніж 1,822 (для розмірності 2) або 2 (для розмірності >2).

Алгоритми

Точний розв'язок

Існують алгоритми, що дають точний розв'язок задачі. Один із таких алгоритмів дає розв'язок за час image.

Апроксимація 1 + ε

Апроксимація 1 + ε знаходить розв'язок з апроксимаційним коефіцієнтом, що не перевершує 1 + ε. Така апроксимація NP-складна у випадку довільного ε. Запропоновано підхід, заснований на концепції [en], зі складністю виконання image. Доступний альтернативний алгоритм, що також ґрунтується на базових наборах. Він працює за час image. Автор стверджує, що час роботи значно менший від часу гіршого випадку і існує можливість розв'язати деякі задачі в разі малих k (приміром,  k < 5).

Виділення віддалених точок

Через складність задачі, непрактично шукати точний розв'язок або близьку апроксимацію. Замість цього для великих k широко використовують апроксимацію з коефіцієнтом 2. Ця апроксимація відома під назвою «Алгоритм виділення віддалених точок» (ВВТ = англ. Farthest-point clustering, FPC) або як алгоритм [en]. Алгоритм досить простий: вибираємо як центр довільну точку множини, знаходимо найдальшу з решти множини і вважаємо її наступним центром. Продовжуємо процес, поки не наберемо 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.].

Див. також

Примітки

  1. Hochbaum, 1982, с. 148–162.
  2. Guha, Khuller, 1999, с. 228.
  3. Li, 2011, с. 77–88.
  4. Fowler, Paterson, Tanimoto, 1981, с. 133–137.
  5. Megiddo, Tamir, 1982, с. 194–197.
  6. Gonzalez, 1985, с. 293–306.
  7. Feder, Greene, 1988, с. 434–444.
  8. Hwang, Lee, Chang, 1993, с. 1–22.
  9. Hwang, Chang, Lee, 1993, с. 398–423.
  10. Bādoiu, Har-Peled, Indyk, 2002, с. 250–257.
  11. Kumar & Kumar, 2010.
  12. Препарата и Шеймос, 1989.
  13. Toussaint, 1983, с. 347–358.
  14. Csoke, 2015.

Література

  • Препарата Ф., Шеймос М. . Вычислительная геометрия: Введение. — М. : Мир, 1989. — . з джерела 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. — 28 червня. — С. 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. — 28 червня. — С. 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 (28 червня). — С. 133–137. — DOI:10.1016/0020-0190(81)90111-3.
  • Gonzalez T. . Clustering to minimize the maximum intercluster distance // . — 1985. — Т. 38 (28 червня). — С. 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 (28 червня). — С. 228. — DOI:10.1006/jagm.1998.0993.
  • Hochbaum D. S. . Heuristics for the fixed cost median problem // . — 1982. — Т. 22 (28 червня). — С. 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 (28 червня). — С. 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 (28 червня). — С. 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 (28 червня). з джерела 28 серпня 2010. Процитовано 15 березня 2022.
  • Li Shi. . A 1.488. Approximation Algorithm for the Uncapacitated Facility Location Problem // Automata, Languages and Programming. — . — 2011. — Т. 6756. — P. 77–88. — . — 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 (28 червня). — С. 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 (28 червня). — С. 347–358.

Посилання

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

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Zada cha pro rozmi shennya ob ye ktiv vidoma takozh yak ana liz roztashuva nnya obla dnannya abo zada cha k ce ntra ce gilka doslidzhennya operacij i obchislyuvalnoyi geometriyi yaka doslidzhuye optimalne roztashuvannya ob yektiv z metoyu minimizuvati cini perevezen z urahuvannyam takih obmezhen yak rozmishennya nebezpechnih materialiv poblizu zhitla ta ob yektiv konkurentiv Ci metodi takozh znahodyat zastosuvannya u klasternomu analizi Zadacha pro rozmishennya ob yektiv z minimizaciyeyuProsta zadacha pro rozmishennya ob yektiv ce zadacha Vebera v yakij rozmishuyetsya odin ob yekt z metoyu minimizaciyi zvazhenoyi sumi vidstanej do zadanoyi mnozhini tochok Skladnishi zavdannya ciyeyi disciplini vinikayut za obmezhen na rozmishennya ob yektiv i za vikoristannya skladnishih kriteriyiv optimizaciyi U bazovomu formulyuvanni zadacha pro rozmishennya ob yektiv skladayetsya z potencijnih tochok zabudovi L de ob yekti mozhut buti stvoreni i tochok D yaki slid obsluzhiti Meta vibrati pidmnozhinu F tochok rozmishennya ob yektiv z metoyu minimizuvati sumu vidstanej vid kozhnoyi tochki obslugovuvannya do najblizhchogo obslugovuvalnogo ob yekta plyus sumu vartostej rozmishennya ob yektiv Zadachu pro rozmishennya ob yektiv na zagalnih grafah NP skladno rozv yazati optimalno zvedennyam napriklad vid zadachi pro pokrittya mnozhini Rozrobleno kilka algoritmiv dlya zadach pro rozmishennya ob yektiv i bagatoh variantiv ciyeyi zadachi Bez pripushen pro vlastivosti vidstanej mizh kliyentami ta miscyami roztashuvannya ob yektiv zokrema bez dopushennya sho vidstan zadovolnyaye nerivnist trikutnika zadacha vidoma yak nemetri chna zada cha pro rozmi shennya ob ye ktiv i yiyi mozhna aproksimuvati z mnozhnikom O log n Mnozhnik tisnij sho viplivaye zi en iz zadachi pokrittya mnozhini Yaksho mi pripuskayemo sho vidstani mizh kliyentami ta miscyami rozmishennya ob yektiv neoriyentovani j zadovolnyayut nerivnist trikutnika mi govorimo pro zadachu metri chnogo rozmi shennya ob ye ktiv MRO MRO zalishayetsya NP skladnoyu zadacheyu i yiyi vazhko aproksimuvati zi mnozhnikom krashim nizh 1 463 Na danij chas krashij aproksimacijnij algoritm maye koeficiyent 1 488 Minimaksne rozmishennya ob yektivMinima ksna zada cha pro rozmi shennya ob ye ktivshukaye rozmishennya yake minimizuye maksimalni vidstani do misc rozmishennya de vidstan vid deyakoyi tochki do misc rozmishennya ce vidstan vid tochki do najblizhchogo miscya rozmishennya Formalne viznachennya take Yaksho zadano mnozhinu tochok P ℝd potribno znajti mnozhinu tochok S ℝd S k taku sho znachennya maxp P minq S d p q bude minimalnim U razi evklidovoyi metriki pri k 1 zadacha vidoma yak zadacha pro najmenshu obmezhuvalnu sferu abo zadacha pro 1 centr Vivchennya zadachi prostezhuyetsya shonajmenshe do 1860 roku div dokladnishe v statti Obmezhuvalna sfera NP skladnist Dovedeno sho tochne rozv yazannya zadachi k centra ye NP skladnim Viyavleno sho aproksimaciya zadachi bude tezh NP skladnoyu yaksho pohibka mala Riven pohibki v aproksimacijnomu algoritmi vimiryuyetsya koeficiyentom aproksimaciyi yakij viznachayetsya yak vidnoshennya aproksimovanogo rozv yazku do optimalnogo Dovedeno sho aproksimaciya zadachi k centra ye NP skladnoyu yaksho koeficiyent aproksimaciyi menshij nizh 1 822 dlya rozmirnosti 2 abo 2 dlya rozmirnosti gt 2 Algoritmi Tochnij rozv yazok Isnuyut algoritmi sho dayut tochnij rozv yazok zadachi Odin iz takih algoritmiv daye rozv yazok za chas n O k displaystyle n O sqrt k Aproksimaciya 1 e Aproksimaciya 1 e znahodit rozv yazok z aproksimacijnim koeficiyentom sho ne perevershuye 1 e Taka aproksimaciya NP skladna u vipadku dovilnogo e Zaproponovano pidhid zasnovanij na koncepciyi en zi skladnistyu vikonannya O 2 O k log k e 2 d n displaystyle O 2 O k log k varepsilon 2 dn Dostupnij alternativnij algoritm sho takozh gruntuyetsya na bazovih naborah Vin pracyuye za chas O k n displaystyle O k n Avtor stverdzhuye sho chas roboti znachno menshij vid chasu girshogo vipadku i isnuye mozhlivist rozv yazati deyaki zadachi v razi malih k primirom k lt 5 Vidilennya viddalenih tochok Cherez skladnist zadachi nepraktichno shukati tochnij rozv yazok abo blizku aproksimaciyu Zamist cogo dlya velikih k shiroko vikoristovuyut aproksimaciyu z koeficiyentom 2 Cya aproksimaciya vidoma pid nazvoyu Algoritm vidilennya viddalenih tochok VVT angl Farthest point clustering FPC abo yak algoritm en Algoritm dosit prostij vibirayemo yak centr dovilnu tochku mnozhini znahodimo najdalshu z reshti mnozhini i vvazhayemo yiyi nastupnim centrom Prodovzhuyemo proces poki ne naberemo k centriv Legko bachiti sho algoritm pracyuye za linijnij chas Oskilki dovedeno sho aproksimaciya z koeficiyentom menshim vid 2 NP skladna VVT vvazhayut krashoyu aproksimaciyeyu Piznishe za dopomogoyu tehniki ramkovoyi dekompoziciyi chasovu skladnist vikonannya pokrasheno do O n log k Maksiminne rozmishennya ob yektivZadacha maksimi nnogo rozmi shennya ob ye ktiv shukaye rozmishennya yake maksimizuye minimalni vidstani do storin U vipadku evklidovoyi metriki zadacha vidoma yak zadacha pro najbilshu porozhnyu sferu Ploskij vipadok mozhna rozv yazati za chas 8 n log n Vilno poshiryuvane programne zabezpechennya dlya rozv yazuvannya zadach rozmishennya ob yektivNazva za abetkoyu Licenziya Mova API Korotka informaciya FLP Spreadsheet Solver Creative Commons Attribution 4 0 International License Sistema na osnovi Microsoft Excel i VBA z vidkritim kodom dlya rozv yazuvannya zadachi pro rozmishennya ob yektiv iz posilannyam na GIS zagalnogo dostupu Video uroki 15 bereznya 2022 u Wayback Machine ODL Studio LGPL Obmezhenij klasternij komponent v ODL Studio rozv yazuye zadachu pro P medianu rozmishennya z minimizaciyeyu zvazhenoyi sumi vidstanej Programa vklyuchaye plani rozmishennya zviti ta zavantazhennya vivantazhennya v Excel Uroki z ODL Studio 12 kvitnya 2022 u Wayback Machine SITATION freeware Mozhe rozv yazuvati zadachi p yati klasiv P mediana P centr pokrittya mnozhinami maksimalne pokrittya i zadacha z fiksovanimi vitratami bez obmezhennya propusknoyi zdatnosti 1 28 bereznya 2022 u Wayback Machine Div takozhCentr grafa Kvadratichna zadacha pro priznachennya Algoritm Dejkstri en PrimitkiHochbaum 1982 s 148 162 Guha Khuller 1999 s 228 Li 2011 s 77 88 Fowler Paterson Tanimoto 1981 s 133 137 Megiddo Tamir 1982 s 194 197 Gonzalez 1985 s 293 306 Feder Greene 1988 s 434 444 Hwang Lee Chang 1993 s 1 22 Hwang Chang Lee 1993 s 398 423 Badoiu Har Peled Indyk 2002 s 250 257 Kumar amp Kumar 2010 Preparata i Shejmos 1989 Toussaint 1983 s 347 358 Csoke 2015 LiteraturaPreparata F Shejmos M Vychislitelnaya geometriya Vvedenie M Mir 1989 ISBN 5 03 001041 6 z dzherela 15 bereznya 2022 Badoiu M Har Peled S Indyk P Approximate clustering via core sets Proceedings of the thirty fourth annual ACM symposium on Theory of Computing 2002 28 chervnya S 250 257 z dzherela 4 bereznya 2016 Procitovano 15 bereznya 2022 Csoke M 2 Governors State University 2015 z dzherela 22 serpnya 2020 Feder T Greene D Optimal algorithms for approximate clustering Proceedings of the twentieth annual ACM symposium on Theory of Computing 1988 28 chervnya S 434 444 z dzherela 7 travnya 2021 Procitovano 15 bereznya 2022 Fowler R J Paterson M S Tanimoto S L Optimal packing and covering in the plane are NP complete Information Processing Letters 1981 T 12 28 chervnya S 133 137 DOI 10 1016 0020 0190 81 90111 3 Gonzalez T Clustering to minimize the maximum intercluster distance 1985 T 38 28 chervnya S 293 306 DOI 10 1016 0304 3975 85 90224 5 z dzherela 24 sichnya 2013 Guha S Khuller S Greedy Strikes Back Improved Facility Location Algorithms Journal of Algorithms 1999 T 31 28 chervnya S 228 DOI 10 1006 jagm 1998 0993 Hochbaum D S Heuristics for the fixed cost median problem 1982 T 22 28 chervnya S 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 T 9 no 1 28 chervnya S 1 22 DOI 10 1007 BF01185335 z dzherela 15 bereznya 2022 Procitovano 15 bereznya 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 T 9 no 4 28 chervnya S 398 423 DOI 10 1007 bf01228511 z dzherela 15 bereznya 2022 Procitovano 15 bereznya 2022 Kumar P Kumar P Almost optimal solutions to k clustering problems International Journal of Computational Geometry amp Applications 2010 T 20 no 4 28 chervnya z dzherela 28 serpnya 2010 Procitovano 15 bereznya 2022 Li Shi A 1 488 Approximation Algorithm for the Uncapacitated Facility Location Problem Automata Languages and Programming 2011 T 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 T 1 no 5 28 chervnya S 194 197 DOI 10 1016 0167 6377 82 90039 6 z dzherela 7 grudnya 2012 Procitovano 15 bereznya 2022 Toussaint G T Computing largest empty circles with location constraints International Journal of Computer and Information Sciences 1983 T 12 no 5 28 chervnya S 347 358 Posilannyasection on location analysis 24 lyutogo 2012 u Wayback Machine profesijna spilnota z vivchennya problem rozmishennya zibrana Trevorom Gale yaka mistit ponad 3400 statej Optimizator rozmishennya virobnictva 5 kvitnya 2022 u Wayback Machine zasnovanij na MATLAB zasib dlya rozv yazuvannya zadach rozmishennya virobnictva

Дата публікації:
Топ