Реоптимизация задачи о покрытии множествами
При додаванні або звільненні елемента з множини задачу про покриття множинами реоптимізовано з відношенням (2 - 1/(ln m + 1)), де m— число елементів множини. Подібний результат має місце при додаванні або вилученні довільного числа 1 < p < m елшементів з множини. If an element is inserted int...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45644 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Реоптимизация задачи о покрытии множествами / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 6. — С. 27–31. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859576173054394368 |
|---|---|
| author | Михайлюк, В.А. |
| author_facet | Михайлюк, В.А. |
| citation_txt | Реоптимизация задачи о покрытии множествами / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 6. — С. 27–31. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | При додаванні або звільненні елемента з множини задачу про покриття множинами реоптимізовано з відношенням (2 - 1/(ln m + 1)), де m— число елементів множини. Подібний результат має місце при додаванні або вилученні довільного числа 1 < p < m елшементів з множини.
If an element is inserted into or deleted from a set, the set covering problem can be reoptimizated with the ratio (2 - 1/(ln m + 1)), where m is the number of elements of the set. A similar result holds if an arbitrary number 1< p < m of elements of the set is inserted or deleted.
|
| first_indexed | 2025-11-27T02:49:18Z |
| format | Article |
| fulltext |
ÓÄÊ 519.854
Â.À. ÌÈÕÀÉËÞÊ
ÐÅÎÏÒÈÌÈÇÀÖÈß ÇÀÄÀ×È Î ÏÎÊÐÛÒÈÈ ÌÍÎÆÅÑÒÂÀÌÈ
Êëþ÷åâûå ñëîâà: ðåîïòèìèçàöèÿ, r-ïðèáëèæåííûé àëãîðèòì.
 íàñòîÿùåå âðåìÿ ïðè ðåøåíèè NP-òðóäíûõ çàäà÷ âîçíèêëà íîâàÿ âû÷èñëèòåëü-
íàÿ ïàðàäèãìà — ðåîïòèìèçàöèÿ [1–7]. Íàèáîëåå èçâåñòíûé ïîäõîä ê ðåøåíèþ òà-
êèõ çàäà÷ ñîñòîèò â ðàçðàáîòêå è èñïîëüçîâàíèè ïðèáëèæåííûõ àëãîðèòìîâ, êîòî-
ðûå çà ïîëèíîìèàëüíîå âðåìÿ äàþò ðåøåíèå, áëèçêîå ê îïòèìàëüíîìó. Êà÷åñòâî
ïðèáëèæåííîãî ðåøåíèÿ (îáû÷íî èçìåðÿåìîãî êàê îòíîøåíèå çíà÷åíèé ïðèáëèæåí-
íîãî è îïòèìàëüíîãî ðåøåíèé) äîëæíî áûòü ãàðàíòèðîâàíî. Íàïðàâëåíèå èññëåäî-
âàíèé, ñâÿçàííîå ñ ðàçðàáîòêîé ëó÷øèõ ïðèáëèæåííûõ àëãîðèòìîâ, è êëàññèôèêà-
öèÿ ïðîáëåì, îñíîâàííàÿ íà êà÷åñòâå ïðèáëèæåíèÿ, êîòîðîå äîñòèãàåòñÿ çà ïîëè-
íîìèàëüíîå âðåìÿ, çàíèìàþò âàæíîå ìåñòî â òåîðåòè÷åñêèõ èññëåäîâàíèÿõ èíôîð-
ìàòèêè çà ïîñëåäíèå äâà äåñÿòèëåòèÿ.
Ïîíÿòèå ðåîïòèìèçàöèè ñîñòîèò â ñëåäóþùåì. Ïóñòü Ï — íåêîòîðàÿ NP-òðóä-
íàÿ (âîçìîæíî, NP-ïîëíàÿ) ïðîáëåìà, I — íà÷àëüíûé ýêçåìïëÿð ïðîáëåìû Ï, îïòè-
ìàëüíîå ðåøåíèå êîòîðîãî èçâåñòíî. Ïðåäëàãàåòñÿ íîâûé ýêçåìïëÿð I � çàäà÷è Ï,
ïîëó÷åííûé íåêîòîðûìè «íåçíà÷èòåëüíûìè» èçìåíåíèÿìè ýêçåìïëÿðà I. Êàê ìîæ-
íî ýôôåêòèâíî èñïîëüçîâàòü çíàíèÿ îá îïòèìàëüíîì ðåøåíèè I äëÿ âû÷èñëåíèÿ
òî÷íîãî èëè ïðèáëèæåííîãî ðåøåíèÿ ýêçåìïëÿðà I � ?
Öåëü ðåîïòèìèçàöèè ïðè ïðèìåíåíèè ïðèáëèæåííûõ ìåòîäîâ — èñïîëüçîâà-
íèå çíàíèé î ðåøåíèè íà÷àëüíîãî ýêçåìïëÿðà I äëÿ: ëèáî äîñòèæåíèÿ ëó÷øåãî êà-
÷åñòâà ïðèáëèæåíèÿ (àïïðîêñèìàöèîííîãî îòíîøåíèÿ) I � ; ëèáî ñîçäàíèÿ áîëåå ýô-
ôåêòèâíîãî (áûñòðîãî ïî âðåìåíè) àëãîðèòìà îïðåäåëåíèÿ îïòèìàëüíîãî èëè áëèç-
êîãî ê íåìó ðåøåíèÿ I � ; ëèáî âûïîëíåíèÿ ïåðâîãî è âòîðîãî óñëîâèé.
Èçâåñòíû ñëåäóþùèå ðåçóëüòàòû ïî ðåîïòèìèçàöèè äèñêðåòíûõ çàäà÷ îïòè-
ìèçàöèè. Ïðè âñòàâêå ýëåìåíòàðíîé äèçúþíêöèè ðåîïòèìèçàöèÿ Max Weighted Sat
(âçâåøåííàÿ çàäà÷à î âûïîëíèìîñòè íà ìàêñèìóì) àïïðîêñèìèðóåìà ñ îòíîøåíèåì
0,81, õîòÿ Max Weighted Sat àïïðîêñèìèðóåìà ñ îòíîøåíèåì 0,77 [7]. Ïðè âñòàâêå
âåðøèíû â ãðàô ðåîïòèìèçàöèÿ Min Vertex Cover (ìèíèìàëüíîå âåðøèííîå ïîêðû-
òèå ãðàôà) àïïðîêñèìèðóåìà ñ îòíîøåíèåì 1,5, Min Vertex Cover — ñ îòíîøåíè-
åì 2 [7]. Ïðè âñòàâêå âåðøèíû (òåðìèíàëüíîé èëè íåò) ðåîïòèìèçàöèÿ Min Steiner
Tree (ìèíèìàëüíîå äåðåâî Øòåéíåðà) àïïðîêñèìèðóåìà ñ îòíîøåíèåì 1,5, Min
Steiner Tree — ñ îòíîøåíèåì 1 3 2 1 55� �ln( ) / , [4].
Ñëåäóåò îòìåòèòü öèêë ðàáîò ïî ðåîïòèìèçàöèè çàäà÷è î êîììèâîÿæåðå
(TSP — Travelling Salesman Problem) [1–3, 5]. Íàïðèìåð, çàäà÷à Minimum Metric
TSP (Min TSP — çàäà÷à î êîììèâîÿæåðå íà ìèíèìóì ñ ìåòðè÷åñêèìè ðàññòîÿíèÿ-
ìè) àïïðîêñèìèðóåìà ñ îòíîøåíèåì 1,5, åå ðåîïòèìèçàöèÿ ïðè âñòàâêå íîâîãî
óçëà — ñ îòíîøåíèåì 1,34, ðåîïòèìèçàöèÿ ýòîé çàäà÷è ïðè èçìåíåíèè ðàññòîÿíèé —
ñ îòíîøåíèåì 1, 4 [7]. Äëÿ îáùåé çàäà÷è î êîììèâîÿæåðå (Min TSP) íåèçâåñòíû îöåí-
êè àïïðîêñèìàöèè êàê äëÿ íåå ñàìîé, òàê è äëÿ ðàçëè÷íûõ âåðñèé ðåîïòèìèçàöèè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹6 27
© Â.À. Ìèõàéëþê, 2010
ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß Î ÏÐÈÁËÈÆÅÍÍÛÕ ÀËÃÎÐÈÒÌÀÕ
È ÀÏÏÐÎÊÑÈÌÀÖÈÎÍÍÛÕ ÊËÀÑÑÀÕ ÇÀÄÀ× ÄÈÑÊÐÅÒÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Ïðèâåäåì íåêîòîðûå íåîáõîäèìûå ïîíÿòèÿ äëÿ äàëüíåéøåãî èçëîæåíèÿ [7].
Îïðåäåëåíèå 1 [7]. NP-îïòèìèçàöèîííàÿ (NPO) ïðîáëåìà Ï îïðåäåëÿåòñÿ êàê
÷åòâåðêà ( , , , )E mSol opt òàêàÿ, ÷òî:
• E — ìíîæåñòâî ýêçåìïëÿðîâ Ï, ðàñïîçíàâàåìîå çà ïîëèíîìèàëüíîå âðåìÿ;
• äëÿ äàííîãî I E� Sol( )I — ìíîæåñòâî äîïóñòèìûõ ðåøåíèé I; äëÿ êàæäîãî
S I�Sol( ) | |S (ðàçìåð S) ïîëèíîìèàëåí ïî | |I (ðàçìåð I); äëÿ ëþáîãî äàííîãî I è
ëþáîãî S (ïîëèíîìèàëüíîãî ïî | |I ) çà ïîëèíîìèàëüíîå âðåìÿ ìîæíî îïðåäåëèòü
S I�Sol( ) ;
• äëÿ äàííûõ I E� è S I m I S�Sol( ) ( , ) — çíà÷åíèå (÷èñëîâîå) S ; m ïîëèíî-
ìèàëüíî âû÷èñëèìà è íàçûâàåòñÿ öåëåâîé ôóíêöèåé;
• opt { }� min, max — òèï îïòèìèçàöèîííîé ïðîáëåìû.
Äëÿ äàííîé NPO-ïðîáëåìû � � { Sol opt}E m, , , îïòèìàëüíîå ðåøåíèå ýêçåìïëÿ-
ðà I ñ Ï îáîçíà÷èì S I* ( ) , åãî âåëè÷èíó — m I S I I( , ( )) ( )* � opt .
Îïðåäåëåíèå 2 [7]. Äëÿ äàííîé NPO-ïðîáëåìû � � ( , , , )E mSol opt ïðèáëèæåí-
íûé (àïïðîêñèìàöèîííûé) àëãîðèòì A — ýòî àëãîðèòì, êîòîðûé äëÿ äàííîãî ýê-
çåìïëÿðà I ñ Ï âûäàåò äîïóñòèìîå ðåøåíèå S I�Sol ( ) .
Åñëè A âûïîëíÿåòñÿ çà ïîëèíîìèàëüíîå âðåìÿ îò | |I , òî A íàçûâàåòñÿ ïîëèíî-
ìèàëüíûì ïðèáëèæåííûì àëãîðèòìîì äëÿ Ï.
Êà÷åñòâî ïðèáëèæåííîãî àëãîðèòìà îöåíèâàåòñÿ êàê îòíîøåíèå �A I( ) (àï-
ïðîêñèìàöèîííîå îòíîøåíèå) ìåæäó çíà÷åíèåì ïðèáëèæåííîãî ðåøåíèÿ
m I A I( , ( )) è çíà÷åíèåì îïòèìàëüíîãî ðåøåíèÿ opt( )I . Òàêèì îáðàçîì, äëÿ ìèíèìè-
çàöèîííûõ ïðîáëåì àïïðîêñèìàöèîííîå îòíîøåíèå íàõîäèòñÿ â ïðåäåëå [ , )1 , äëÿ
ìàêñèìèçàöèîííûõ — â [ , ]0 1 .
Îòíîñèòåëüíî êà÷åñòâà ïðèáëèæåííûõ àëãîðèòìîâ NPO-ïðîáëåìû êëàññèôè-
öèðóþò ñëåäóþùèì îáðàçîì.
Îïðåäåëåíèå 3 [7]. NPO-ïðîáëåìà Ï ïðèíàäëåæèò ê êëàññó APX , åñëè ñóùåñ-
òâóåò ïîëèíîìèàëüíî ïðèáëèæåííûé àëãîðèòì A è ðàöèîíàëüíîå ÷èñëî r òàêîå,
÷òî äëÿ äàííîãî I ñ � �A I r( )
(ñîîòâåòñòâåííî �A I r( ) � ) , åñëè Ï — ìèíèìèçà-
öèîííàÿ (ñîîòâåòñòâåííî ìàêñèìèçàöèîííàÿ) ïðîáëåìà.  ýòîì ñëó÷àå A íàçûâàåò-
ñÿ r-ïðèáëèæåííûì (àïïðîêñèìàöèîííûì) àëãîðèòìîì (ïðîáëåìà Ï — r-àïïðîêñè-
ìèðóåìà àëãîðèòìîì A).
Ïðèìåðàìè êîìáèíàòîðíûõ îïòèìèçàöèîííûõ ïðîáëåì, ïðèíàäëåæàùèõ
ê êëàññó APX , ÿâëÿþòñÿ Max Weighted Sat, Min Vertex Cover, Min TSP. Äëÿ îòäåëü-
íûõ ïðîáëåì èç APX ìîæíî ââåñòè áîëåå ñèëüíóþ ôîðìó àïïðîêñèìàöèîííîñòè.
Äëÿ òàêèõ ïðîáëåì äëÿ ëþáîãî ðàöèîíàëüíîãî r � 1(èëè r � ( , )0 1 äëÿ ìàêñèìè-
çàöèîííûõ ïðîáëåì) ñóùåñòâóåò àëãîðèòì Ar è ïîäõîäÿùèé ïîëèíîì p òàêîé,
÷òî Ar — r-àïïðîêñèìàöèîííûé (ïðèáëèæåííûé) àëãîðèòì ñî âðåìåíåì, èçìåðÿ-
åìûì êàê p îò | |I . Ñåìåéñòâî àëãîðèòìîâ Ar (ïàðàìåòðèçîâàííîå ñ ïîìîùüþ r)
íàçûâàåòñÿ ïîëèíîìèàëüíîé ïðèáëèæåííîé ñõåìîé (PTAS — Polynomial Time
Approximation Scheme).
Îïðåäåëåíèå 4 [7]. NPO-ïðîáëåìà Ï ïðèíàäëåæèò ê êëàññó PTAS , åñëè äëÿ ëþ-
áîãî ðàöèîíàëüíîãî r � 1 (ñîîòâåòñòâåííî r � ( , )0 1 ) è ëþáîãî ýêçåìïëÿðà I ñ Ï ñó-
ùåñòâóåò òàêàÿ ïîëèíîìèàëüíàÿ ïðèáëèæåííàÿ ñõåìà Ar , ÷òî �Ar
I r( )
(ñîîòâå-
òñòâåííî �
Ar
I r( ) � ) äëÿ Ï — ìèíèìèçàöèîííîé (ìàêñèìèçàöèîííîé) ïðîáëåìû.
Çàìåòèì, ÷òî â îïðåäåëåíèè PTAS âðåìÿ àëãîðèòìà Ar ïîëèíîìèàëüíî îòíîñè-
òåëüíî ðàçìåðà âõîäà, îäíàêî îíî ìîæåò áûòü ýêñïîíåíöèàëüíî îòíîñèòåëüíî r �1.
Ëó÷øàÿ ñèòóàöèÿ âîçíèêàåò, êîãäà âðåìÿ âûïîëíåíèÿ ïîëèíîìèàëüíî êàê ïî ðàçìå-
ðó âõîäà, òàê è ïî r �1(èëè 1� r äëÿ ìàêñèìèçàöèîííûõ ïðîáëåì).  ýòîì ñëó÷àå àë-
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
ãîðèòì íàçûâàåòñÿ ïîëíîñòüþ ïîëèíîìèàëüíîé ïðèáëèæåííîé ñõåìîé (FPTAS —
Fully Polynomial Time Approximation Scheme).
Îïðåäåëåíèå 5 [7]. NPO-ïðîáëåìà ïðèíàäëåæèò ê êëàññó FPTAS , åñëè îíà äî-
ïóñêàåò ïîëíîñòüþ ïîëèíîìèàëüíóþ ïðèáëèæåííóþ ñõåìó.
Åñëè P NP
, òî èìååò ìåñòî âêëþ÷åíèå FPTAS PTAS APX NPO� � � .
ÐÅÎÏÒÈÌÈÇÀÖÈß ÇÀÄÀ×È Î ÏÎÊÐÛÒÈÈ ÌÍÎÆÅÑÒÂÀÌÈ
ÏÐÈ ÈÇÌÅÍÅÍÈÈ ÌÀÒÐÈÖÛ ÎÃÐÀÍÈ×ÅÍÈÉ
Çàäà÷ó î ïîêðûòèè ìíîæåñòâàìè (çàäà÷à Ï( , )A c ) ðàññìîòðèì â ñëåäóþùåé ïî-
ñòàíîâêå:
min ( ) ( )f x c x x Q Ai i
i
n
� �
�
�
�
��
�
�
�
���
�
1
,
Q A x B a x i mn
ij j
j
n
( ) , , ,� � � �
�
�
�
��
�
�
�
���
� 1 1
1
� ,
ãäå B A a i m j nn n
ij� � � �{ } { }0 1 1 1, , , , , , , , ,� � A m n� ( , ) — áóëåâà ìàòðèöà ( ),m n
c i ni � �0 1, , , .�
Áóäåì ïîëüçîâàòüñÿ ñëåäóþùèìè ðåçóëüòàòàìè.
Èçâåñòíî [8], ÷òî æàäíûé àëãîðèòì ðåøàåò çàäà÷ó �( , )A c ñ îöåíêîé òî÷íîñòè
1
1
1 t
m
t
c A
�
�
�
( )
ln , ãäå c A( ) — ìàêñèìàëüíîå ÷èñëî åäèíèö â ñòîëáöå ìàòðèöû A, ò.å.
æàäíûé àëãîðèòì — (ln )m� 1 -ïðèáëèæåííûé (àïïðîêñèìàöèîííûé) àëãîðèòì äëÿ
ðåøåíèÿ �( , )A c .
Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ äëÿ èçìåíåííûõ ýêçåìïëÿðîâ çàäà÷è �( , )A c :
�( , )A cj
� (ñîîòâåòñòâåííî �( , )A cj
� ) — çàäà÷à �( , )A c ñ çàìåíîé â ñòîëáöå j ìàòðè-
öû A ïðîèçâîëüíîãî 0 íà 1 (1 íà 0) ; �( ( ), )A p cj
� (ñîîòâåòñòâåííî �( ( ), )A p cj
� ) —
çàäà÷à �( , )A c ñ çàìåíîé â ñòîëáöå j ìàòðèöû A ïðîèçâîëüíîãî ÷èñëà p p m( )1
�
0 íà 1 (1 íà 0 ) ; REOPT ( )� — ñîîòâåòñòâóþùèé ðåîïòèìèçàöèîííûé àëãîðèòì, èñ-
õîäÿùèé èç îïòèìàëüíîãî ðåøåíèÿ çàäà÷è �( , )A c .
Äîïóñòèìîå ðåøåíèå S j jk� { }1 , ,� çàäà÷è �( , )A c èíòåðïðåòèðóåì êàê ñîâî-
êóïíîñòü ñòîëáöîâ { }j jk1 , ,� (ïîäìíîæåñòâ ìíîæåñòâà { }1, , )� m , êîòîðûå ñîñòàâ-
ëÿþò ïîêðûòèå ìàòðèöû A (ò.å. S j jk� { }
1
, ,� ñîîòâåòñòâóåò äîïóñòèìûé âåêòîð
x x x Q An� �( , , ) ( )
1
� òàêîé, ÷òî x x xj j jk1 2
1� � � �� ; îñòàëüíûå êîìïîíåíòû
ðàâíû 0). Ïîä âåñîì c S( ) ðåøåíèÿ S áóäåì ïîíèìàòü c S c cj jk
( ) � � �
1
� .
Òåîðåìà 1. Ñóùåñòâóåò REOPT A cj( ( , ))� � , ÿâëÿþùèéñÿ 2
1
1
�
�
�
�
�
�
�
�
ln m
-ïðèáëè-
æåííûì (àïïðîêñèìàöèîííûì) àëãîðèòìîì.
Äîêàçàòåëüñòâî. Ïðèìåíèì òåõíèêó äîêàçàòåëüñòâà ðåîïòèìèçàöèè Min
Vertex Cover (çàäà÷è î ìèíèìàëüíîì âåðøèííîì ïîêðûòèè) ïðè âñòàâêå íîâîé âåð-
øèíû èç [7]. Ïîñòðîèì REOPT A cj( ( , ))� � .
Ïóñòü S * — îïòèìàëüíîå ðåøåíèå çàäà÷è �( , )A c , S I �
* — îïòèìàëüíîå ðåøå-
íèå �( , )A cj
� , S j* �{ } — äîïóñòèìîå ðåøåíèå �( , )A cj
� .
Åñëè S I �
* ñîäåðæèò j, òî S j* �{ } — ðåøåíèå.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹6 29
Ïðåäïîëîæèì, ÷òî S I �
* íå ñîäåðæèò j, òîãäà S j* �{ } — äîïóñòèìîå ðåøåíèå
�( , )A cj
� è, ïîñêîëüêó c S c S I( ) ( )* *
� , èìååì
ñ S j c S cI j( { }) ( ')
* *�
� . (1)
Ïîñòðîèì äîïóñòèìîå ðåøåíèå S1 çàäà÷è �( , )A cj
� :
— ïðèìåíèì �-ïðèáëèæåííûé (àïïðîêñèìàöèîííûé) àëãîðèòì äëÿ çàäà÷è
�( , )A cj
� ñ èñêëþ÷åííûì ñòîëáöîì (ìíîæåñòâîì) j (ñîîòâåòñòâóþùåå x j � 0 â �( , )A c );
— ê ïîëó÷åííîìó ðåøåíèþ äîáàâèì ñòîëáåö (ìíîæåñòâî) j.
Òàêèì îáðàçîì, èìååì
c S c S c c c S cI j j I j( ) ( ( ) ) ( ) ( )* *
1 1
� � � � �� �� � � (2)
(êàê è âûøå, S I �
* íå ñîäåðæèò j). Ñðåäè ðåøåíèé S j* �{ } è S1 âûáåðåì (S ) íàè-
ëó÷øåå (ñ íàèìåíüøèì çíà÷åíèåì âåñà). Äîìíîæèâ (1) íà � �1 è ïðèáàâèâ ê (2),
ïîëó÷èì
( ) ( ) ( ) ( ) ( ) ( ) ( )* * *
� � � �� � �
� � � �� �1 1 2 11c S j c S c S c S cI I{ } ( )*S I � .
Ïîñêîëüêó ( ) ( ) ( ) ( )min ( ), ( )* *
� � �� � � � � � � �1 1 11 1c S j c S c S j c S{ } { { } } c S( ) , èìååì
� �c S c S I( ) ( ) ( )*
� �2 1 .
Ïîëó÷åíî ïðèáëèæåííîå ðåøåíèå S çàäà÷è �( , )A cj
� , äëÿ êîòîðîãî
c S c S c SI I( ) ( ) ( )* *
�
� �
�
�
��
�
�
��� �
2 1
2
1�
� �
.
Ïîëîæèâ � � �ln m 1 (ò.å. ïðèìåíèâ ïðè ôîðìèðîâàíèè S1 æàäíûé àëãîðèòì),
â ðåçóëüòàòå ïîëó÷èì äîêàçàòåëüñòâî òåîðåìû.
Òåîðåìà 2. Äëÿ 1� �p m ñóùåñòâóåò REOPT A p cj( ( ( ), ))� � , ÿâëÿþùèéñÿ
2
1
1
�
�
�
�
�
�
�
�
ln m
-ïðèáëèæåííûì (àïïðîêñèìàöèîííûì) àëãîðèòìîì.
Äîêàçàòåëüñòâî ïîëíîñòüþ àíàëîãè÷íî äîêàçàòåëüñòâó òåîðåìû 1.
Òåîðåìà 3. Ñóùåñòâóåò REOPT A cj( ( , ))� � , ÿâëÿþùèéñÿ 2
1
1
�
�
�
�
�
�
�
�
ln m
-ïðèáëè-
æåííûì (àïïðîêñèìàöèîííûì) àëãîðèòìîì.
Äîêàçàòåëüñòâî ïðîâåäåì ïî àíàëîãèè ñ ïðåäûäóùèì (ñ íåêîòîðûìè ìîäèôè-
êàöèÿìè). Ïîñòðîèì ñîîòâåòñòâóþùèé REOPT A cj( ( , ))� � .
Ïóñòü S * — îïòèìàëüíîå ðåøåíèå çàäà÷è �( , )A c , S I �
* — îïòèìàëüíîå ðåøå-
íèå çàäà÷è �( , )A cj
� .
Åñëè S * íå ñîäåðæèò j, òî S SI � �* * . Åñëè S * ñîäåðæèò j, òî S * ìîæåò íå áûòü
äîïóñòèìûì ðåøåíèåì �( , )A cj
� . Ïîñòðîèì â ýòîì ñëó÷àå ïîäõîäÿùåå ïðèáëèæå-
íèå ðåøåíèÿ çàäà÷è �( , )A cj
� .
Äëÿ ôèêñèðîâàííîãî j ïîëîæèì i c ai ij0 1� �arg { }min : (ò.å. i0 òàêîå, 1
i n,
÷òî ci0
ìèíèìàëüíî è aij � 1, 1
i n). Òîãäà â ëþáîì ñëó÷àå S i* � { }0 — äîïóñòè-
ìîå ðåøåíèå �( , )A cj
� . Ïîñêîëüêó c S c S I( ) ( )* *
� , èìååì
c S i c S cI i( { }) ( )* *�
��0 0
. (3)
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Ïîñòðîèì äîïóñòèìîå ðåøåíèå S1 çàäà÷è �( , )A cj
� :
— ïðèìåíèì �-ïðèáëèæåííûé (àïïðîêñèìàöèîííûé) àëãîðèòì äëÿ çàäà÷è �( , )A cj
�
ñ èñêëþ÷åííûì ñòîëáöîì (ìíîæåñòâîì) i0 (ñîîòâåòñòâóþùåå xi0
0� â �( , )A c );
— ê ïîëó÷åííîìó ðåøåíèþ äîáàâèì ñòîëáåö (ìíîæåñòâî) i0 .
Òàêèì îáðàçîì, èìååì
c S c S c c c S cI i i I i( ) ( ( ) ) ( ) ( )* *
1 0 0 0
1
� � � � �� �� � � . (4)
Ñðåäè ðåøåíèé S i* � { }0 è S1 âûáåðåì (S ) íàèëó÷øåå (ñ íàèìåíüøèì çíà÷åíè-
åì âåñà). Äîìíîæèâ (3) íà � �1 è ïðèáàâèâ ê (4), ïîëó÷èì
( ) ( ) ( ) ( ) ( ) ( ) ( )* * *
� � � �� � �
� � � �� �1 1 2 10 1c S i c S c S c SI I{ } c S I( )*
� .
Ïîñêîëüêó
( ) ( ) ( ) ( )min ( ), ( )* *
� �� � � � � � �1 1 10 1 0 1c S i c S c S i c S{ } { { } }� �c S( ) ,
èìååì � �c S c S I( ) ( ) ( )*
� �2 1 .
Ïîëó÷åíî ïðèáëèæåííîå ðåøåíèå S çàäà÷è �( , )A cj
� , äëÿ êîòîðîãî
c S c S c SI I( ) ( ) ( )* *
�
� �
�
�
��
�
�
��� �
2 1
2
1�
� �
.
Ïîëîæèâ � � �ln m 1 (ò.å. ïðèìåíèâ ïðè ôîðìèðîâàíèè S
1
æàäíûé àëãîðèòì),
ïîëó÷èì äîêàçàòåëüñòâî òåîðåìû.
Òåîðåìà 4. Äëÿ 1� �p m ñóùåñòâóåò REOPT A p cj( ( ( ), ))� � , ÿâëÿþùèéñÿ
2
1
1
�
�
�
�
�
�
�
�
ln m
-ïðèáëèæåííûì (àïïðîêñèìàöèîííûì) àëãîðèòìîì.
Äîêàçàòåëüñòâî àíàëîãè÷íî äîêàçàòåëüñòâó òåîðåìû 3.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A u s i e l l o G . , E s c o f f i e r B . , M o n n o t J . , a n d P a s c h o s V . T h . Reoptimization of minimum
and maximum traveling salesman’s tours // Algorithmic theory. SWAT 2006; Lect. Notes Comput. Sci. —
Berlin: Springer, 2006. — 4059. — P. 196–207.
2. O n t h e approximability of TSP on local modifications of optimal solved instances / H.J. Bockenhauer,
L. Forlizzi, J. Hromkovic, et al. // Algorithmic Oper. Res. — 2007. — 2(2). — P. 83–93.
3. B o c k e n h a u e r H . J . , H r o m k o v i c J . , M o m k e T . , a n d W i d m a y e r P . On the hardness of
reoptimization // Proc. of the 34th Intern. Conf. on Current Trends in Theory and Practice of Computer Sci-
ence (SOF — SEM 2008); Lect. Notes Comput. Sci. — Berlin: Springer, 2008. — 4910. — P. 50–65.
4. E s c o f f i e r B . , M i l a n i c M . , a n d P a s c h o s V . T h . Simple and fast reoptimizations for the
Steiner tree problem // Algorithmic Oper. Res. — 2009. — 4(2). — P. 86–94.
5. A r c h e t t i C . , B e r t a z z i L . , a n d S p e r a n z a M . G . Reoptimizing the travelling salesman problem
// Networks. — 2003. — 42(3). — P. 154–159.
6. A r c h e t t i C . , B e r t a z z i L . , a n d S p e r a n z a M . G . Reoptimizing the 0-1 knapsack problem. —
Manuscript, 2008.
7. A u s i e l l o G . , B o n i f a c i V . , a n d E s c o f f i e r B . Complexity and approximation in reoptimiza-
tion // Computability in Context: Computation and Logic in the Real World. — Imperial College Press,
members of the 2007 Computability Europe conference CiE 2007: Logic and Computation in the Real
World (June, 2007). — P. 24–33.
8. C h v a t a l V . A . A greedy heuristic for the set covering problem // Math. Oper. Res. — 1979. — 4, N 3.
— P. 233–235.
Ïîñòóïèëà 10.12.2009
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹6 31
|
| id | nasplib_isofts_kiev_ua-123456789-45644 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-27T02:49:18Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.А. 2013-06-17T06:16:06Z 2013-06-17T06:16:06Z 2010 Реоптимизация задачи о покрытии множествами / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 6. — С. 27–31. — Бібліогр.: 8 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45644 519.854 При додаванні або звільненні елемента з множини задачу про покриття множинами реоптимізовано з відношенням (2 - 1/(ln m + 1)), де m— число елементів множини. Подібний результат має місце при додаванні або вилученні довільного числа 1 < p < m елшементів з множини. If an element is inserted into or deleted from a set, the set covering problem can be reoptimizated with the ratio (2 - 1/(ln m + 1)), where m is the number of elements of the set. A similar result holds if an arbitrary number 1< p < m of elements of the set is inserted or deleted. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Реоптимизация задачи о покрытии множествами Реоптимізація задачі про покриття множинами Reoptimization of set covering problems Article published earlier |
| spellingShingle | Реоптимизация задачи о покрытии множествами Михайлюк, В.А. Кибернетика |
| title | Реоптимизация задачи о покрытии множествами |
| title_alt | Реоптимізація задачі про покриття множинами Reoptimization of set covering problems |
| title_full | Реоптимизация задачи о покрытии множествами |
| title_fullStr | Реоптимизация задачи о покрытии множествами |
| title_full_unstemmed | Реоптимизация задачи о покрытии множествами |
| title_short | Реоптимизация задачи о покрытии множествами |
| title_sort | реоптимизация задачи о покрытии множествами |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45644 |
| work_keys_str_mv | AT mihailûkva reoptimizaciâzadačiopokrytiimnožestvami AT mihailûkva reoptimízacíâzadačípropokrittâmnožinami AT mihailûkva reoptimizationofsetcoveringproblems |