Исследование некоторых задач размещения центров тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ЛКЛДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ

на правах рукописи

КУРУМА Сидшси Касбвдв

ИССШЩШШ НЕКОТОРЫХ ЗАДАЧ РАЗМЕЩАЙ ЦЕНТРОВ Специальность 01,01.09 - /ттс^ятпчеокая Ю!боряетш:а

АВТОРЕФЕРАТ диссертации на сс мсиаино ученоЛ степош! кандидата у.о-тчвиаттеата тук

Глист IS93

Работа выполнена в Белорусском государственном угишерсите

Научный руководитель - кандидат физико-штекатических ш

доцент Ковалев Михаил Шхайлович.

Официальные оппоненты - доктор физико-математических наук

Мотальсхий Николай Николаевич - кандидат физико-математических на;

Кравцов Шхаил Константинович. «

Ведущая организация - Институт кибернетики АН Украины.

Задата состоится " 27" ноября_1992 г. в / ^ час;

на заседании специализированного совета К 006.19.01 по присуждению ученой степени кандидата фязико-латештичесетп .наук в Институте ютеитика АН Беларуси по адресу:' 220072, г.Минск, ул.Сурганова, II

С диссертацией можно ознакомиться в библиотеке Института ьагештшда АН Беларуси,

Автореферат разослан "ку- октября__1992 г.

Ученый секретарь специализированного совета кандидат фиа, -хат. наук

А.Й.Астровскз;

'оссийпкдя I Т^Г"

»ИГ>Л;нШ:Ч4 "• -----^

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы Одна из первых и наиболее известиях здач оптимизации - задача о размещении центров, т.о. задача гнскания в некотором множестве Хр точек (центров) наименее цаленных в некоторой метрике от множество задавших точек У. ри это?.) в зависимости от значений р (р-1 или р > 1), типа этрического пространства, в котором заданы X и У, совпадения ли несовпадения X и У получаем пртшцнпиалыю различные задачи, ак, если X - евклидова плоскость Ея, ^ = 1. У е Е3, |У|=3, случаем ¡слаесаческум задачу поиска точют наименее удаленной от адашых трех, решение которой сало известно еще Торичелли в 640 г. Обобщениям* этой задачи являются классические задачи тейнера о зсрагчайией связующей сети в метриках X,, Ъ, Ь

1 2 <х>

очек на плоскости и задача Ферма о поиске точки метрического ространства, суша взвезсшшх расстояний от которой до аданной минимальна.

Задачи о центрах в различной постановке широко сследуются, особенно в последнее время, в связи о их рактическга.а значениям! для различит областей исследования яераций, синтеза сетей, кластеризации, диагностики, [роблематике задач размещения центров посвящены многие обзорггаэ :татьи и монографта. Ввиду трудности задач исследуются, как-правило, их специальные случаи.

Математическая структура задачи размещения центров шределяется метрикой в пространстве позмемшх точек размещения 1 способом оценки качества размещения (критерий оптимальности). 3 следствие отого существуют ¡того разнообразии:? постановок задач размещения и литература изобилует методам» их ревенис. Ограничимся перечислением осповшга типов задач ро^т^нил:

задача Штейнера на плоскости или в пространстве ¡Г (евклидова метрика Ь2. или сумма квадратов расстояшШ, прямоугольная метрика , чебшаевская метрика ;

задача Штейпера на графе, т.е. в графовой метрике;

задача о медианах графа (графовая метрика, взвешенная сумма кратчайших расстояний, минимизация суммы расстояний);

задача о центрах графа (графовая метрика, максимум кратчайших расстояний, минимизация максимального из кратчайших расстояний).

• Актуальной представляется проблема выделения как новых классов полиномиально разрешимых задач о центрах, так и построение алгоритмов более эффективных, чем известные хотя Си па частных классах задач.

Диссертационная работа посвящена исследовании следуздш задач размещения центров: задача о р-медианах графа, графовая задача Штейпера, специальная задача о р-модиане планарногс графа и динамическая задача Штейпера.

Цель работа :

исследовать связь размещения центров задач 1 субмодулярной оптимизации;

- изучить структуру оптимальных решений в специальна задачах о центрах (динамическая и звездочная задача Шхейнера).

Научная новизна работы :

- излокены град»1ент1ше методы решения задачи о р-медианаз графа, как задачи минимизации специальной супермодулярно; функции;

- установлена связь задачи Итейиера на графе I дополнительным услс дем отсутствия смежных точек Штейпера I задачей минимизации суиермодулярно!.' функции и • излояси

эадиентний алгоритм ее решения!

- для ыаксиыизационшх вариантов указанных задач найдены хетт точности градиентных алгоритмов;

- доказана оквивалентность специальной задачи о р-медианах зафа задаче покрытая гранями вершин трехмерного многогранника;

- изучена дшмшгаоская задача Штейнера на плоскости.

Методика исследования. Использована:

- теория субмодулярных функций;

- методики оценок точности грэдн, шшх алгоритмов;

- основные факт теории графов, дискретной оптимизации и злиэдральной комдннаторики.

Практическая значимость. Метода, разработанные в юсертации могут применяться при рекении многих задач 1т:шизащы размещения центров в сетях. Задачи размещения гнтров связаны с решением проблем наилучшего расположения в тределеншх регионах так:.1 систем обслуживания, как станции сорой медицинской помоец?, торговые цептрц, поста покарюй ipamj, фабрики, аоропортн, склада!, пункты производства зтрэбляемого в ото,\г регионе товара и т.д.

Пубдкка1?и. Результаты диссертации опубликованы п печатных зботах, список которых приведен в автореферате.

Структура и объем работы. Диссертация состоит из введения, эти параграфов, списка литературы 3& (наименования) и изложена з Sf- страницах машинописного теиста.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Во введении обосновывается актуальность исследований, дается обзор имеющихся результатов по теме диссертации t приводится краткая аннотация всех ее параграфов.

В первой параграфа дан обзор результатов о задачах размещения центров.

Второй параграф устанавливает связь задачи размещения центров с задачами субмодулярной оптимизации. Напомним, чтс Функция I: 2",—> R называется субмодулярной ( супермодулярной), если ■

Г (А) + I(B) г J(AuB) t Î(AaB) (fU) + Î(B) s f(AuB) + Î(AaB)).

Нусть дано множество N из n точек и задана метрика

r: N*II-î>B . Необходимо найти подмножество 1*с И из р тс

множества N, на котором достигается

min (Г(1): 1 s И, |1| - р) (1)

min tf*(I): I с H, |I| = р> (2)

Критерий в сформулированной задаче размещения центров (в данном

случае они называются ыедиани) шест вид: Очевидно, что при р=1

обе задачи мссивалентны.

ГЦ) = Z »in tr(i,3) ! ici) (3)

Jsn\J

г'П) = £ rnax ir(ij): i « I) (4)

1ÎTH\ T

Задача о нахоэдезши р-ыедиан графа введена в 1964 году Хаккми, является IIP-трудной и имеет многочисленные практические применения, выступает даскрэтннм аналогом известной задачи й-ерма-Вебера, в которой необходимо найти местоположение точек в метрическом пространстве, с да; а расстояний от которых до данных n точек минимально. Воздохни обобщения задаст, когда не все точки разрешены для размещения, т.е. I s X с H и не все точки

- б -

эебуется прикреплять, т.о. борется J е Y\I, где Y е и. ззможен случай так же что X и У непересекающиеся множества, .е.

min {f(I): I с N, |I| = p},

Г(1) (l"U)) = £ min (пах) (r(i,j): i e I}.

JCY

Заметил, что если r(i,j) - граФ°вая метрика, т.е. есть пина кратчайшей цепи мозду inj, то задача навивается задачей р-медиало графа и при р=1 это есть задача о медиане графа.

Известно, что задача о р-медаопе, как на графе, так и в ругах метриках является 1ГР-трудно2.

Теорема 2.1. Функция Т(1), заданная условием (_3), является невозрастахцей супермодулярпой, а функция 1^(1), заданная условлен (4.), является неубшапцеЛ суСмодулярноЯ.

Иогмо рассмотреть er,с две нетрадициошше задачи размещения ентров:

-¡rax lt(l): I s N. |l|=p} (5)

mix {i"(I): I - II,|lhp}. (6)

Отметим, что задача штимйзецяп еубнодалярнсй функции 1* ли максимизации сутгормодулярнсй t на веем шогэотве "являются ползночизльнкм'л.

На основании теореш 2.1 применим грэдаептше алгоритмы ;убмодулярной оптимизации для сфорхутроввттх задач.

Пусть ¡¡С ,| - матрица весов ребер. На начально?,! этапе с

i J "nxn

юмощыо алгоритма ©лайда , трудоемкостью 0(п3), находим матрицу сратчайдн росстолииЯ jr(ij)8 На порвсЯ итерация полагав! 0П~ j и вычисляем i-градиенты:

giKi&*Ha) = !({!}) - 1(a) - £ min r(i.J) - E r(1J) 1 . j-i j-i

- 7 -

для всех вершин i графа, и находим ту вершину ijt котор< соответствует минимальный (максимальный) i-градиент. 1 последующих итерациях к поступаем аналогично, т.е. ее. построено решение О = {1i^}," то добавляем к не» медиану доставляющую

min (пах) grad*f(G ),

где grad*i(G ) = i<Gk.1u Алгоритм закапчив!

работу на итерации к=р.

Предложение 2.1. Градиентное решение G при р=1 являет(

Р

оптимальным в задаче минимизации (1), (; (максимизации (5),(б)) супермодулярш функции f(I).

Следствие 2.1. Градиентное решение 0 является также опт!

малышм в задаче max {f(3): |I| s p) щ любом p.

Из известных результатов следует также, что для оче; специальных метрик, когда i(I) есть модулярная фушед (одновременно суб и супер,лодулярная), градиентный алгоритм дае оптимальное решение задачи о р-медаане.

Пусть OFT - оптимальное решение в задаче максимизаш

itt(I). Качество полученного градиентного решения G оценивае

р

следующая теорема.

i*(oPT)-lö(G

Теорема 2.2. Относительная погрешность i = -Е

1ö(dpt)

градиентного решения максимизациошой за; чи о р-медиане оценивается правилом

- а -

л * 0-4- )р « 4- «

р ' s - 2.4 •

В третьей параграфа вводится супермодулярная задача ]тейнера на неориентированл-w графа G-(V,E). Каждому ребру з е Е приписан вес о и необходимо найти дерево ШтеЯнера m о лшималышм суммарным весом, т.е. минимизирующее Функцию

Х(Т) = Е о ,

в<ГЕ °

где Т - ациклически спязшй подграф графа G , покрывающий зершпш из мноз;ества X.

Утверждение' 3-1 • Допустимое множество в задаче Штейнера на графе является обобщенным матроидом.

Если бл функция Г(Т) являлась линейной, то градиентный алгоритм (координатный или бикоордипатный) гарантировал Cu получение оптимального решения. Этим алгоритма ; возмозз-га воспользоваться /. з об;аем случае, однако оценки качества градиенпшх peisemiñ известии только если Г(1) - супермодулярпяя функция.

Исследуем случай, когда функция Г(1) является супермодулярной, точнее заменим функции 1(1) ее супермодулярноЯ аппроксимацией Г(1), где Г'(1) есть длина минимального оотопиого дерева для графа К*, который получен из К1 удалением всех ребер, имеющих обэ концевые вершины в S. Фактически f'(I) есть целевая функция в классе задач ШтеЯнера с лсполнчтелышч условием: в дереве Штейнера нет .двух сиетлпп точек 1ИгрПнпгп. назовем такую задачу звездной зядячеЛ Штейиера.

Теорема 3.1. Функция f'(I) ясляртол оупорлолулягп"Я.

Доказательство теоремы вытекает из иснотошост градиентов :

grad*r(I') s grad*f(3), если I s I', которая в свою очередь непосредственно следует из описали нетривиального алгоритма вычисления градиента. Для вычислеш: grad i(I) необходимо к графу К1 добавить вершину i и в ново графе К найти минимальное остошюе дерево.

Начальный шаг. Пусть т =(1,Е') минимальное дерево в Находим среди peöep смелагл вершине i кратчайшее:

С = min С 3 (l.j)ex м

Тогда ï'= (lui, Е' и (1,3 )) - минимальное остошюе дерево

К при условии, что степень вершины i равна 1.

Общий ïi-îi шаг. Пусть TU(I и 1, Ек) - шшшалыюе сстовно дерево в К при условии, что степень вершшщ i равна к Очевидно, что Е1 получено из Е удалением к-1 ребра добавлением Ii ребер кшшдетшшх 1. Пусть ето будут ребр Определяем дерево Гк +1 е помощью расетаноьк меток fj. ГДЭ Tj - есть длина ребра максимальной дашш в в тс. цепи. Тогда для всех (1,3), 3=3 ,•..,3k_t определяем стоимоот.

добавления ребра (1,3) и удаления ребра «

к

Пусть Зк - вершина , па которой достигается

min СО, тт.>-

J-J ,.. • J 'J J J Ji' Jk

.Если о - т < О, то T,i + 1 получается из l,k добавле-Jk 1

кием ребра (1,3*) и удалением ребра а, .

k Ч

Если о , - т * й 0, то 1к - минимальное дерево j

алгоритм закончен.

Сложность итерации алгоритма 0(п) и повтолу слсяаюст:

всего алгоритма 0(пр), где р - етвшшь вегамнн i а до^м.о д.п*

1С . Очевидно, что р s ISI, ток как ми кдрм писанное м-р:-: о

" IUI .

Лтейнера.

Приводе?.! пример;; зпездиоЛ родэчи [IheiSiiepa.

Пусть строительство павода в путаете 3 стоит с , а

транспортировка по дуге (j,i) - о . Получаем зпездную задачу

йтейперз с весами торгаш ß для j g S л Сйсаил ребир

а, = о.,Ь. исгользуется известное свойство оптимал; пего М * j 3

ромонпя каждой поотощпк снабжается от одного завода.

Градиопзшй алгоритм ревешвя звездооЛ задачи ЕтбЕнв-ра Полагаем I = X.

Общая итерация. С псиоцьа изложошюго вше олгор-дг.гй вычисляем градпепгч grad*f(I ) фуницга 1(1 ) для его

1 иг I :

к

graa; x(ik)=2 с= - г сок '-J1 к

Здесь дерево i, , в гра^э К , , поягшакдез" iui I иг

к

множества X.

Шгаодам вералну i с яеамвпьпял традаентем л лол'!гае;--' -

Т — Т V i Ф - Т1

" Je1 ~ V V Хи->Г "I vi •

jt jf

Зшепагле 3.2. Если G не является полллл rpai-сл».то- свс!Г» ство монотонности шзпш&шпа грал^ятс/В mosgt не соблюдаться. 1 Иояпо рассмотреть тгасае серию из градиен-лт ат'оглтг.'со. а именно. не сЗраздя втшавм па знак гродданга тк.стрс^.тъ -тс у

деревьев Г и за результат работы алгоритма взять лучпее к к к

построенных деревьев, т.е. найти дерево Г° такое, что

С(Т°) = min С(Т ). к к Й

Двойственной градиентный алгоритм Общая итерация.

Вычисляем градиенты функции ) для каздог

1 с тк\Х- Для втого о помощью алгоритма вычисления градиентов :

графе К1 находим минимальное остовное дерево Т и к

покрывающее вершшш из X. Тогда

ёгасГ 1(1 ) - £ С - I С

аСТ " е>€Т °

кЧ1 ' к В

Находим вершину с максимальным градиентом и полагаем

^ = V V V

и

.Алгоритм заканчивает свои работу на шаге, когд ёгай^(1к) а 0.

Аналогично предыдущему случаи мокно рассмотреть серию и: деревьев, построенных на всех шагах двойственного градиентного алгоритма и выбрать лучшее.

В четвертое парогрв$9 изучается динамическая задач; Штешера в цредпилихокт, что точки движутся по прямолинейны! траекториям.

Ес л прямые - траектории движения с любга скоростью точек составляют меааду собой угол 120°, то точк; Щг^Лнс^.о остается неподвижной и совладает с'точкой пересечет.

траекторий.

Предложение 4-2. Пусть три точки движутся в одном направлении по параллельным пряыш, причем третья движется точно посреди мезщу втими двумя (и возможно в противоположном направлении). Тогда

а) если их скорости равны то траектория S(t) движения точки Штейнера совпадает с траекторией точки Аз; ( tVt, i .л)

б) если третья движется с отличной скоростью V =Va*V , то траектория S(t) движения точки Штейнера есть такке прямая; совпадающая с прямой A3(t); Сс^* Рис -i. S)

в) если скорости всех трех точек отлични V ^ , то траектория S(t) движения точки Штейнера есть дуга окружности радиуса а/43" и далее совпадает о одной из траекторий.

Замечаьие 4.1. Отметим, что если третья точка движется- не точно посреди между двумя, тогда случаи а) и б) сох; мняют место.

Во всех других случаях траектория Sit) движения точки Штейнера есть дуга окрукности радиуса а/43 и далее совладает с одной из траекторий.

л

✓ 1

AifL

V

v

( Put Л ) - 13 -

ЛгШ

Предложение 4.3. Если траектории трех точек и-параллельные пряше, то траектория S(t) движения точш Штейнер; есть прямая только тогда, когда треугольники А, (t )А (t )А (t,

S U « v о Ü

И A^V^V^V и A;(t3)A-(t2)A»(t2) вписаны.

Теорема 4.1. Пусть точки A.(t ) и A„(t„) нелодашизы j

г-------------.3 0 2 о

находятся на расстоянии а, и точка А (t ! двшсется по прямой, перпендикуляр к которо!

с?,!, ряс.

образует с прямой А (tQ)A (t ) угол а. Тогдг траектория S(t) движения точки Штейнера фрагмент S1(t)A2(tQ) дуга А, (t0)A3(t0) окружности радиуса 3./W и S (t^Ao(t0) дугс A1(to)A2(tQ) того ке радиуса.°Точки S^y i S (+-) имеют соответственно координаты:

№

f äff" sin (ЭО-ь«) ^ 2 sin (30-«)

а sin (30+в) |. 2 sin (30-в) )'

fa<? sin (30-g) а sin (30-g) )

sin (30+a)

2 БХП (30+a) )

Теорема 4.2. Пусть траектория движения точки есть

прямая проходящая мезду неподвижными точками А ('Ьо) и АЭ(Ъ0). Тогда траектория точки

Штейнерз составлена из двух дуг Э (ЮО , О 52(1;) окружностей радауса а/ 43" и отрезка 0 0, траектории точки При этом *очки

5 и) и Ё^Ъ) имеют соответственно координаты

■и. рис. 3.

Теорема 4.3. Пусть траектории двиггения точек н

А (t ) паралеллыш и гчкяутся в противсполсж-. нем направлении с одной скорость«. Пусть точка -Aji tg) неподвижная л находится на ■ расстояния а ст А (t ) и (а +а_) от л (t ).

1 1 u 1 л «3 Q

Тогда траектория S(t) _точки йтэйнчра составлена из отрезка Л^ {(V ) л дуги л, U„)A' (t ) округлости радиуса а/ТГ.

1-й 2 1

Теорема 4.4. Пусть траектории движения точек". А^-t^) и ^ (t ) параллельны и спи движутся а протано-голозпо» гавревлешю, я гечко- А,Д ik-шд-- 15 -

вижна и находится мегвду Аä(to) и Aa(t ). Тогд траектория S(t) точки Штейнера есть неподвижная точка, совпадающая с A2(tQ).

Теорема 4.5. Пусть траектории движения точек As(t ) и A3(t ) параллельны и эти точки движутся в одном направлении со скоростями vt> v . Точка A2(t0) неподвижна и находится на расстоянии а, от А^) и а2 от A3(t0).

а) если v < v , то траектория S(t) точки Штейкера составлена из дуги " Aa(t0)Ai'(t ) окрумюсти радиуса n/W , а затем совпадает с траекторией движения точки А (Р ).

б) е-пи v =v , то траектория S(t) есть прямая параллельная А (t ), Л (t ).

Теорема 4.'. Пусть траектории движения точек А (t ) и А (t ) параллельни и обе точки движутся в одном направлении со скоростями v , v . Пусть точка А (tfl) неподвижна и находится на расстоянии а„ ог A„(t ) и (а+а„) от А (t ).

3 2 0 12 10

Тогда

а) если v С v , то траектория S(t) точки Шгейнера совладает о траекторией движения точки A2(tQ) пока ^ MWWV а а 120°, затем является дугой A^(ti)AJ(tj) онру-кпоога радиуса а/43", а затем совпадает с траекторией даигешя точки А (t ); б) если v - v , то траектория , S(t) есть

линия, стремящаяся к некоторой прямой, положение которой заьяспт от а и а,,.

В пятен пврягря^о изучается специфическая задача о центрах з плднарноЛ реализации графа, т.е. необходимо найти некоторое .шокество точек та;;, чтобы трассы еоед;шЯЕ;цие их с вор ичами графа но пересекали рзбер графа (дорог) и имели мшимали'.у» зушорнуя длину.

Для реиешш зс, ,ачи в Планерной реализации предлагается алгоритм градиентного типа

1. Для иазадоЛ внутренней грани I находим центр (X1) по формулам

Л1 = 2 л /\1 |; = Е У/К!;

и вес I) , рзвпи,1 длило трасс, соадклякднх центр (X1,-1) со всеми верхшами своей граня. Здесь 7 - множество верная г -¿пи 1.

2. Строил задачу покрытия в форда (трапв-зерввош) с ьосша граней Б .

3. Находим минимальное покрнтие Р:

гШп Е в121,

X, = 0/1,

где - ыатрхгца ннцидендиЛ (виутрепшю граЕИ-портяп;).

4. Центры (X1 ,У1), отвечайте граням I £ I' берем в качестве искомых центров.

Для этапа 3 алгоритма но повестей алгоритм. Л сотому его ¡.к ига замигать приЗ&пктгагм г?«и~!*.ктг.с\-.

Основные результаты диссертации опубликованы в работах:

1. Курума С.К. Динамическая задача Штейлера для тре; точек // .Актуальные проблеш информатики: Математическое, программное и информационное обеспечение. Минск, Ь'елгосуниверситет, 1983.

2. Куруыа С.К. Задача выбора центров планэтпюго графа // Актуальные проблемы информатики: Математическое, программное I 1шфор.шционноо обеспечение. Минск, Велгосуниверситет, 1990.

3- Курума С.К. Субмодулярность критерия в задаче с

медианах // /лтуальные проблеш информатики: Математическое, прогрш-вяюе и ' информационное обеспечение. Млнлк, Велгосуниверситет, 1992-

•ПСД&НИШО и иочааь ¿0.10,92. Ьумигп '¿шогрсн-скал I Уел.л^ч.г. 1,и

Т р,;. 100 15?.

*>о{г;а1' 60;.84,1/16.

нг.'ч^х^ с» 'ii'.'} ;;.

V'. л!:1,:,; 1'. ..Л) .и ЩЛ» Да РЬ. 220072, ¡Гчюк,