Проблемът за поставяне на обекти

Проблемът за поставяне на обекти, като същевременно минимизират

А просто задача за поставяне на обекти - това е задачата на Вебер. в което един обект се намира, за да се сведе до минимум изчислената сума на разстоянията до даден набор точки. Още предизвикателства възникват в тази дисциплина ограничения относно разполагането на обекти, както и с помощта на по-сложни критерий за оптимизация.

Основният състав на проблема за поставяне на предмети се състои от потенциалната поставянето на точки L., където могат да бъдат отворени обекти и D. точки, които трябва да бъдат взети под внимание. Целта - да изберете подмножество на F поставяне точка на обекти с цел минимизиране на сумата от разстоянията от всяка точка на обслужване до най-близкия сервизен център, плюс сумата на разходите за съоръжения за настаняване.

Проблемът с поставянето на предмети върху същите графики NP-трудни за решаване на оптимално и може да бъде решен с информация (например) от проблема с набор настилки. Той разработи няколко алгоритми за поставянето на предмети, както и много варианти на този проблем.

Не предположения относно свойствата на разстоянията между клиентите и местоположението на обекта (по-специално, без да се предположи, че разстоянието удовлетворява неравенството триъгълник), проблемът е, известни като не-метричен проблем на разположение на обекти и може да се сближават фактор О (влизане п) [1]. Модификатор тесен, което следва от сближаването запазване шофиране [ен] покритие на набор задача.

Ако приемем, че разстоянието между клиента и местоположението на обекта ненасочена и отговарят на неравенството триъгълник, ние говорим за проблема с метричната местоположението на обекти (МПО). MPO остава NP-трудно проблем, и е трудно да се сближат с множител от най-добрите 1.463 [2]. В момента най-добрият алгоритъм приближение има коефициент на 1.488. [3].

Минимакс места за настаняване

Минимакс проблем на разположение на обектите, които търсят настаняване, което свежда до минимум на максималното разстояние до настаняването, където разстоянието от точка до настаняването - разстоянието от точка до най-близките места за настаняване. Официалното определение за следното: Ако посочения множеството точки за P ⊂ ℝ г. Трябва да намерим набор от точки S ⊂ ℝ г. | S | = К. така че стойността на maxp ∈ P (minq ∈ S (г (стр. р))) е сведена до минимум.

В случай на показателя Euclidean за к = 1, проблемът е известен като проблемът на най-малкия областта очертаващ или задача-1 центъра. Проучването на проблема може да се проследи до най-малко 1860, вижте. Член "ограничава обхвата" за подробности.

NP-твърдост

Беше доказано, че точното решение -Център к е NP-трудно [4] [5] [6]. Установено е, че проблемът на сближаване също е NP-трудно ако грешката е малка. процент на грешки в измерва коефициент сближаване алгоритъм сближаване, която се определя като съотношение на разтвора приблизително до оптимума. Доказано е, че проблемът с приближение -Център к е NP-трудно, ако коефициентът на сближаване по-малка от 1,822 (за измерение = 2) [7], или 2 (за измерение> 2) [6].

Има алгоритми, които осигуряват точното решение на проблема. Един такъв алгоритъм осигурява разтвор за време п О (к)>) >> [8] [9].

Сближаване 1 + ε

Изолиране отдалечени точки

Поради трудността на задачата не е практично да се търси точно решение или близко приближение. Вместо това, за голям к широко използвани сближаване коефициент 2. Това приближение е известен като "Алгоритъм за подбор отдалечени точки" (СТО = далечната точка групиране, FPC) или като алгоритъм прекосява "първи дисталния» [ен] [6]. Алгоритъмът е съвсем проста - изберете произволна точка на комплекта като център, е най-отдалечена от останалия набор и вярвам, че следва центъра. Процесът продължава, докато naberom к центрове.

Лесно е да се види, че алгоритъмът работи за линейно време. Тъй като е доказано, че сближаването с коефициент на по-малко от 2, NP-трудно, тук се счита за най-доброто сближаване.

сложността време на извършване на по-късно е подобрена до О (п влизане к) чрез техниката на рамка разлагане [7].

Максимин места за настаняване

Максимин задача на поставяне на предмети, които търсят оформление, което увеличава минималното разстояние от стените. В случай на Euclidean показател проблем е известен като проблемът на областта най празен [ен]. Плосък случай (големина празен кръг [ен]) може да бъде решен за Θ време (п \ дневник н) [12] [13].

Софтуер с отворен код за решаване на проблемите на места за настаняване