Реоптимизация задачи о покрытии множествами

Реоптимизация задачи о покрытии множествами

При додаванні або звільненні елемента з множини задачу про покриття множинами реоптимізовано з відношенням (2 - 1/(ln m + 1)), де m— число елементів множини. Подібний результат має місце при додаванні або вилученні довільного числа 1 < p < m елшементів з множини. If an element is inserted int...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Кибернетика и системный анализ
Дата:2010
Автор: Михайлюк, В.А.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Теми:
Кибернетика
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/45644
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Реоптимизация задачи о покрытии множествами / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 6. — С. 27–31. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-45644
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
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Реоптимизация задачи о покрытии множествами
spellingShingle Реоптимизация задачи о покрытии множествами
Михайлюк, В.А.
Кибернетика
title_short Реоптимизация задачи о покрытии множествами
title_full Реоптимизация задачи о покрытии множествами
title_fullStr Реоптимизация задачи о покрытии множествами
title_full_unstemmed Реоптимизация задачи о покрытии множествами
title_sort реоптимизация задачи о покрытии множествами
author Михайлюк, В.А.
author_facet Михайлюк, В.А.
topic Кибернетика
topic_facet Кибернетика
publishDate 2010
language Russian
container_title Кибернетика и системный анализ
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Реоптимізація задачі про покриття множинами
Reoptimization of set covering problems
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.
issn 0023-1274
url https://nasplib.isofts.kiev.ua/handle/123456789/45644
citation_txt Реоптимизация задачи о покрытии множествами / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 6. — С. 27–31. — Бібліогр.: 8 назв. — рос.
work_keys_str_mv AT mihailûkva reoptimizaciâzadačiopokrytiimnožestvami
AT mihailûkva reoptimízacíâzadačípropokrittâmnožinami
AT mihailûkva reoptimizationofsetcoveringproblems
first_indexed 2025-11-27T02:49:18Z
last_indexed 2025-11-27T02:49:18Z
_version_ 1850792545965047808
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

Схожі ресурси