В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 15
Текст из файла (страница 15)
Àëãîðèòì îñòàíàâëèâàåòñÿ, êîãäàâñå ðåáðà ïîêðûòû.Ëåãêî ïîêàçàòü, ÷òî æàäíûé àëãîðèòì äëÿ ÌÂÏ èìååò ïîëèíîìèàëüíóþ ñëîæíîñòü.Òåîðåìà 5.2. Äëÿ æàäíîãî àëãîðèòìà äëÿ çàäà÷è ÌÂÏ äëÿëþáîãî íàòóðàëüíîãînñóùåñòâóåò ãðàôGnòàêîé, ÷òî ïðè âõîäåGnâûïîëíÿåòñÿ íåðàâåíñòâî:Fàëã > Fîïò (ln n − ln 2 − 1),ãäå Fàëã ÷èñëî âåðøèí â ïîêðûòèè, êîòîðîå ñòðîèò àëãîðèòì.Äîêàçàòåëüñòâî.Âêëþ÷èì â ãðàô Gn ñíà÷àëà âåðøèíûu1 , u2 , . . . , un , ìåæäó êîòîðûìè íå áóäåò ðåáåð. Äàëåå âûäåëèì èç66âåðøèí u1 , u2 , . .
. , un [ n2 ] íåïåðåñåêàþùèõñÿ ïàð (îäíà âåðøèíà ìîæåò íåó÷àñòâîâàòü â ïàðàõ) è êàæäóþ ïàðó ñîåäèíèì ñ íîâîé âåðøèíîé, ïðèýòîì ïîëó÷èì íîâûå âåðøèíû v1 , v2 , . . . , v[ n2 ] ñòåïåíè 2. Çàòåì âûäåëèìèç âåðøèí u1 , u2 , . . . , un [ n3 ] íåïåðåñåêàþùèõñÿ òðîåê è êàæäóþ òðîéêóñîåäèíèì ñ íîâîé âåðøèíîé (ñòåïåíè 3). Äàëåå àíàëîãè÷íî âûäåëèìíåïåðåñåêàþùèåñÿ ÷åòâåðêè, ïÿòåðêè âåðøèí è ò.ä. Íà ïîñëåäíåì ýòàïåâûäåëèì èç u1 , u2 , . . . , un ãðóïïó èç n − 1 âåðøèí è ñîåäèíèì åå ñíîâîé âåðøèíîé (ñòåïåíè n − 1). Çàìåòèì, ÷òî ïîñëå äîáàâëåíèÿ íîâûõâåðøèí ñòåïåíè k âåðøèíû u1 , u2 , . . .
, un èìåþò ñòåïåíü íå áîëåå k − 1,â ÷àñòíîñòè, â çàêëþ÷èòåëüíîì ãðàôå Gn îíè èìåþò ñòåïåíü íå áîëåån − 2. Ïîýòîìó æàäíûé àëãîðèòì, ïðèìåíåííûé ê Gn , ñíà÷àëà âûáåðåòäîáàâëåííóþ âåðøèíó ñòåïåíè n−1, çàòåì (ïîñëå óäàëåíèÿ ýòîé âåðøèíûè ïîêðûâàåìûõ åþ ðåáåð) âûáåðåò âñå äîáàâëåííûå âåðøèíû ñòåïåíèn − 2, çàòåì âñå äîáàâëåííûå âåðøèíû ñòåïåíè n − 3 è ò.ä. Íà ïîñëåäíåìýòàïå îí âûáåðåò âñå äîáàâëåííûå âåðøèíû ñòåïåíè 2. Òàêèì îáðàçîìFàëãn=++ ... +>23n−1 nnn−1 +− 1 + ... +−1 =>23n−11 11=n+ + ... +− (n − 2) >2 3n−1Zn1>ndx − n = n(ln n − ln 2) − n.xhnihni2Ñ äðóãîé ñòîðîíû ìíîæåñòâî {u1 , u2 , .
. . , un } ÿâëÿåòñÿ âåðøèííûì ïîêðûòèåì â Gn . Ïîýòîìó Fîïò 6 n èFàëã > n(ln n − ln 2 − 1) > Fîïò (ln n − ln 2 − 1).Ïóñòü äàíà çàäà÷à îïòèìèçàöèè ñ ôóíêöèîíàëîìF . Àëãîðèòì äëÿ ýòîé çàäà÷è íàçûâàåòñÿ ε- ïðèáëèæåííûì, åñëè âñåãäàÎïðåäåëåíèå.F − F àëãîïò < ε,Fîïòãäå Fàëã è Fîïò çíà÷åíèå ôóíêöèîíàëà, âûäàâàåìîå àëãîðèòìîì, è îïòèìàëüíîå çíà÷åíèå.Åñëè äàíà çàäà÷à ìèíèìèçàöèè è Fîïò > 0, òî óêàçàííîå íåðàâåíñòâî ýêâèâàëåíòíî íåðàâåíñòâó:Fàëã 6 (1 + ε)Fîïò .Ñëåäñòâèå.ε-ïðèáëèæåííûìÆàäíûéàëãîðèòìäëÿíè ïðè êàêîì ôèêñèðîâàííîì67ÌÂÏε.íåÿâëÿåòñÿÑëåäóþùàÿ òåîðåìà ïîêàçûâàåò, ÷òî òåîðåòè÷åñêèíàÿ"ñòðàòåãèÿ äëÿ çàäà÷è ÌÂÏ íå ÿâëÿåòñÿ õîðîøåé."æàä-Òåîðåìà 5.3.
Äëÿ çàäà÷è ÌÂÏ ñóùåñòâóåò 1-ïðèáëèæåííûéàëãîðèòì ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ.Ðàññìîòðèì ñëåäóþùèé àëãîðèòì. Ïóñòü äàíãðàô G = (V, E). Áóäåì ôîðìèðîâàòü âåðøèíîå ïîêðûòèå A. Âîçüìåìëþáîå ðåáðî e1 = (v1 , v2 ) è âêëþ÷èì v1 è v2 â A. Âûáðîñèì èç ãðàôà Gâåðøèíû v1 è v2 è âñå ðåáðà, êîòîðûå èìè ïîêðûâàþòñÿ.
 ïîëó÷åííîìãðàôå G1 îïÿòü âîçüìåì ëþáîå ðåáðî e2 = (v3 , v4 ), äîáàâèì v3 è v4 â Aè óäàëèì èç G1 âåðøèíû v3 è v4 è âñå ïîêðûâàåìûå èìè ðåáðà. Ïðîöåññ çàêîí÷èì, êîãäà áóäóò óäàëåíû âñå ðåáðà. Ëåãêî ïîíÿòü, ÷òî ýòîòàëãîðèòì ìîæíî ðåàëèçîâàòü ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ. Òàêæå ïîïîñòðîåíèþ î÷åâèäíî, ÷òî ïîëó÷åííîå ìíîæåñòâî âåðøèí A ïîêðûâàåòâñå ðåáðà. Ïóñòü â ïðîöåññå àëãîðèòìà âûáèðàëèñü ðåáðà e1 , e2 , .
. . , ek .Òîãäà |A| = 2k . Ñ äðóãîé ñòîðîíû ðåáðà e1 , e2 , . . . , ek íå èìåþò îáùèõâåðøèí è, ñëåäîâàòåëüíî, ëþáîå âåðøèííîå ïîêðûòèå äîëæíî ñîäåðæàòüíå ìåíåå k âåðøèí (÷òîáû ïîêðûòü e1 , e2 , . . . , ek ). Òàêèì îáðàçîì Fîïò > kè Fàëã = |A| 6 2Fîïò . Òåîðåìà äîêàçàíà.Âîçíèêàåò âîïðîñ, à íåëüçÿ ëè äëÿ çàäà÷è ÌÂÏ ïîñòðîèòü íå ïðèáëèæåííûé, à òî÷íûé àëãîðèòì ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ. Âûøåáûëà äîêàçàíà N P -ïîëíîòà çàäà÷è î âåðøèííîì ïîêðûòèè (ÂÏ), ãäå ïîçàäàííîìó ãðàôó G è ÷èñëó k òðåáóåòñÿ âûÿñíèòü, åñòü ëè â ãðàôå Gâåðøèííîå ïîêðûòèå ìîùíîñòè íå áîëåå k .Äîêàçàòåëüñòâî.Òåîðåìà 5.4.
Åñëè äëÿ çàäà÷è ÌÂÏ ñóùåñòâóåò àëãîðèòì ñïîëèíîìèàëüíîé ñëîæíîñòüþ, òî è äëÿ çàäà÷è ÂÏ ñóùåñòâóåò àëãîðèòì ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ.Ïóñòü àëãîðèòì H ðåøàåò çàäà÷ó ÌÂÏ çà ïîëèíîìèàëüíîå âðåìÿ è ïóñòü â çàäà÷å ÂÏ çàäàíû ãðàô G è ÷èñëî k .Ïðèìåíÿåì ê ãðàôó G àëãîðèòì H è ïîëó÷àåì mìèíèìàëüíóþ ìîùíîñòü âåðøèííîãî ïîêðûòèÿ â G. Åñëè m 6 k , òî îòâåò â çàäà÷å ÂÏ äà,èíà÷å îòâåò íåò. Ïîëó÷àåì ïîëèíîìèàëüíûé àëãîðèòì äëÿ çàäà÷è ÂÏ.Çàìå÷àíèå.
Åñëè äëÿ çàäà÷è ÂÏ ñóùåñòâóåò àëãîðèòì H ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ è â ãðàôå G n âåðøèí, òî, ïðèìåíÿÿ àëãîðèòìH ê ïàðàì (G, 0), (G, 1), . . . , (G, n − 1), ìîæíî çà ïîëèíîìèàëüíîå âðåìÿîïðåäåëèòü ìîùíîñòü ìèíèìàëüíîãî âåðøèííîãî ïîêðûòèÿ, îäíàêî íåÿñíî, êàê íàéòè ñàìî ìèíèìàëüíîå âåðøèííîå ïîêðûòèå.Îïðåäåëåíèå. Çàäà÷ó îïòèìèçàöèè áóäåì íàçûâàòü N P -òðóäíîé,åñëè èç ñóùåñòâîâàíèÿ àëãîðèòìà ïîëèíîìèàëüíîé ñëîæíîñòè äëÿ íååñëåäóåò ñóùåñòâîâàíèå àëãîðèòìà ïîëèíîìèàëüíîé ñëîæíîñòè äëÿ íåêîÄîêàçàòåëüñòâî.68òîðîé N P -ïîëíîé çàäà÷è (è,ñëåäîâàòåëüíî, äëÿ âñåõ çàäà÷ èç N P ).Ñëåäñòâèå.
Çàäà÷à ÌÂÏ ÿâëÿåòñÿÑëåäñòâèå. ÅñëèP 6= N P ,N P -òðóäíîé.òî äëÿ çàäà÷è ÌÂÏ íå ñóùåñòâóåòàëãîðèòìà ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ.5.3. Çàäà÷à êîììèâîÿæåðàÂûøå ìû ïîëó÷èëè óñëîâíûé ðåçóëüòàò î òðóäíîñòè íàõîæäåíèÿòî÷íîãî ðåøåíèÿ çàäà÷è ÌÂÏ. Çäåñü ìû ïîêàæåì, ÷òî òàêèå óñëîâíûåîòðèöàòåëüíûå ðåçóëüòàòû ìîæíî ïîëó÷àòü è äëÿ íàõîæäåíèÿ ïðèáëèæåííûõ ðåøåíèé.Íàïîìíèì, ÷òî öèêë â ãðàôå íàçûâàåòñÿ ãàìèëüòîíîâûì, åñëè îíïðîõîäèò ÷åðåç êàæäóþ âåðøèíó ðîâíî 1 ðàç. Âûøå áûëî ïîêàçàíî,÷òî çàäà÷à î ñóùåñòâîâàíèè â ãðàôå ãàìèëüòîíîâà öèêëà (ÃÖ) ÿâëÿåòñÿN P -ïîëíîé.Çàäà÷à êîììèâîÿæåðà (ÇÊ).ïîëíûé ãðàô Kn , â êîòîðîì êàæäîìó ðåáðó e = (vi , vj )ñîïîñòàâëåí âåñ d(e) = d(vi , vj ) > 0.
Ïðè ýòîì áóäåì ñ÷èòàòü, ÷òî âñåd(e) öåëûå ÷èñëà è äëèíà âõîäà âêëþ÷àåò â ñåáÿ ñóììàðíóþ äëèíóäâîè÷íîãî ïðåäñòàâëåíèÿ âñåõ d(e).Òðåáóåòñÿ: íàéòè ãàìèëüòîíîâ öèêë â Kn ñ ìèíèìàëüíîé ñóììîéâåñîâ ðåáåð.Âõîä:Òåîðåìà 5.5. ÇÊ ÿâëÿåòñÿN P -òðóäíîé.Äîêàçàòåëüñòâî. Ïóñòü ñóùåñòâóåò àëãîðèòì H äëÿ ÇÊ ñî ñëîæíîñòüþ, ïîëèíîìèàëüíî çàâèñÿùåé îò äëèíû âõîäà. Ïóñòü äàí ãðàôG = (V, E) ñ n âåðøèíàìè è ñïðàøèâàåòñÿ, åñòü ëè â G ãàìèëüòîíîâöèêë. Ïóñòü V = {v1 , v2 , . . .
, vn }. Ïîñòðîèì ïîëíûé ãðàô Kn íà ìíîæåñòâå âåðøèí V è çàäàäèì âåñà ñëåäóþùèì îáðàçîì:(1, åñëè (vi , vj ) ∈ E,d(vi , vj ) =2, åñëè (vi , vj ) 6∈ E.Ïðèìåíèì àëãîðèòì H äëÿ ÇÊ ê ãðàôó Kn ñ ýòèìè âåñàìè. Åñëè ïîëó÷èìäëÿ ÇÊ, ÷òî Fmin = n, òî â G ñóùåñòâóåò ãàìèëüòîíîâ öèêë, èíà÷å â Gíå ñóùåñòâóåò ãàìèëüòîíîâà öèêëà. Òàêèì îáðàçîì, ïîëó÷àåì àëãîðèòìäëÿ çàäà÷è î ãàìèëüòîíîâîì öèêëå (ÃÖ). Ïîñêîëüêó â G ìåíüøå, ÷åìn2 ðåáåð, òî ñóììàðíàÿ äëèíà äâîè÷íîé çàïèñè âñåõ âåñîâ íå ïðåâîñõîäèò cn2 , ãäå c íåêîòîðàÿ êîíñòàíòà, òî åñòü äëèíà âõîäà äëÿ H íåïðåâîñõîäèò ïîëèíîìà îò n.
Òàê êàê H ïîëèíîìèàëüíûé (îò äëèíûâõîäà) àëãîðèòì, òî ïîñòðîåííûé íàìè àëãîðèòì äëÿ ÃÖ èìååò ïîëèíîìèàëüíóþ îò n ñëîæíîñòü. Òàêèì îáðàçîì èç ñóùåñòâîâàíèÿ àëãîðèòìà ñ69ïîëèíîìèàëüíîé ñëîæíîñòüþ äëÿ ÇÊ âûòåêàåò ñóùåñòâîâàíèå àãîðèòìàñ ïîëèíîìèàëüíîé ñëîæíîòüþ äëÿ ÃÖ. Ïîñêîëüêó çàäà÷à ÃÖ ÿâëÿåòñÿN P -ïîëíîé, òî ïîëó÷àåì, ÷òî çàäà÷à ÇÊ ÿâëÿåòñÿ N P -òðóäíîé.Òåîðåìà 5.6.
Åñëèøîãî ïîñòîÿííîãî ÷èñëàP 6= N P , òî íè äëÿ êàêîãî ñêîëü óãîäíî áîëüε íå ñóùåñòâóåò ε-ïðèáëèæåííîãî àëãîðèòìàäëÿ ÇÊ ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ.Äîïóñòèì, ÷òî ñóùåñòâóåò ε è ñóùåñòâóåòε-ïðèáëèæåííûé àëãîðèòì H ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ äëÿ ÇÊ.Ïîñòðîèì òîãäà àëãîðèòì ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ äëÿ ÃÖ. Ïóñòüäàí ãðàô G = (V, E) ñ n âåðøèíàìè.
Ïîñòðîèì ïîëíûé ãðàô Kn =(V, E 0 ) è äëÿ âñåõ e ∈ E 0 ïîëîæèìÄîêàçàòåëüñòâî.(1,d(e) =b3 + εnc,åñëè e ∈ E,åñëè e 6∈ E.Ïðèìåíèì ê Kn c âåñàìè d àëãîðèòì H . Ïóñòü àëãîðèòì H íàõîäèòãàìèëüòîíîâ öèêë ñ ñóììàðíîé äëèíîé FH .Ëåììà 5.1. Åñëè â ãðàôåGFH 6n(1+ε). Åñëè â ãðàôå G íåò ãàìèëüòîíîâà öèêëà, òî FH > n(1+ε)+1.Äîêàçàòåëüñòâî. Åñëè â G åñòü ãàìèëüòîíîâ öèêë, òî â ÇÊ äëÿKn c âåñàìè d áóäåò Fîïò = n. Òàê êàê H ÿâëÿåòñÿ ε-ïðèáëèæåííûìàëãîðèòìîì äëÿ ÇÊ, òî FH 6 Fîïò (1 + ε) = n(1 + ε). Åñëè â G íåòãàìèëüòîíîâà öèêëà, òî ëþáîé ãàìèëüòîíîâ öèêë ñîäåðæèò õîòÿ áû îäíîðåáðî ñ âåñîì [3 + εn] è n − 1 ðåáåð ñ âåñîì íå ìåíåå 1. Òàêèì îáðàçîì,ñóììàðíûé âåñ ëþáîãî ãàìèëüòîíîâà öèêëà íå ìåíüøå ÷åì n−1+2+εn =n(1 + ε) + 1.Ëåììà 5.1 ïîêàçûâàåò, ÷òî ïî ðåçóëüòàòó ðàáîòû àëãîðèòìà Hìîæíî îïðåäåëèòü, åñòü ëè â G ãàìèëüòîíîâ öèêë.
Òàêèì îáðàçîì, ìûïîëó÷àåì àëãîðèòì H1 äëÿ çàäà÷è ÃÖ. Îöåíèì âðåìÿ åãî ðàáîòû. Äëèíàäâîè÷íîãî ïðåäñòàâëåíèÿ êàæäîãî âåñà d(e) íå ïðåâîñõîäèò c log2 n, ãäåcíåêîòîðàÿ êîíñòàíòà, è êîëè÷åñòâî âåñîâ ìåíüøå, ÷åì n2 . Ïîýòîìóäëèíà âõîäà äëÿ àëãîðèòìà H íå ïðåâîñõîäèò ïîëèíîìà îò n. Ïîñêîëüêóâðåìÿ ðàáîòû H çàâèñèò ïîëèíîìèàëüíî îò äëèíû âõîäà, òî îáùåå âðåìÿðàáîòû àëãîðèòìà H1 íå ïðåâîñõîäèò ïîëèíîìà îò n.  ðåçóëüòàòå ìûïîëó÷àåì, ÷òî åñëè ñóùåñòâóåò ε-ïðèáëèæåííûé àëãîðèòì H ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ äëÿ ÇÊ, òî ñóùåñòâóåò àëãîðèòì ñ ïîëèíîìèàëüíîéñëîæíîñòüþ äëÿ çàäà÷è ÃÖ.
Íî çàäà÷à ÃÖ N P -ïîëíà. Òîãäà ïîëó÷àåì,÷òî P = N P . Òåîðåìà 5.6 äîêàçàíà.Âî ìíîãèõ ïðàêòè÷åñêèõ çàäà÷àõ âåñà óäîâëåòâîðÿþò åñòåñòâåííîåñòü ãàìèëüòîíîâ öèêë, òî70ìó îãðàíè÷åíèþ, íàçûâàåìîìó íåðàâåíñòâîì òðåóãîëüíèêà:d(vi , vj ) 6 d(vi , vk ) + d(vk , vj )äëÿ âñåõ ðàçëè÷íûõ i, j, k . Áóäåì ãîâîðèòü, ÷òî äàíà çàäà÷à êîììèâîÿæåðà ñ íåðàâåíñòâîì òðåóãîëüíèêà (ÇÊÍÒ), åñëè íà âõîä ïîñòóïàþòòîëüêî âåñà, óäîâëåòâîðÿþùèå íåðàâåñòâó òðåóãîëüíèêà.Òåîðåìà 5.7. ÇÊÍÒ ÿâëÿåòñÿN P -òðóäíîé.Äëÿ äîêàçàòåëüñòâà ýòîé òåîðåìû ïîëíîñòüþ ïðîõîäèò äîêàçàòåëüñòâî òåîðåìû 5.5.
Äîñòàòî÷íî òîëüêî îòìåòèòü, ÷òî íàáîð âåñîâ, êîòîðûéñòðîèòñÿ â ýòîì äîêàçàòåëüñòâå, óäîâëåòâîðÿåò íåðàâåíñòâó òðåóãîëüíèêà.Òåîðåìà 5.8. Äëÿ ÇÊÍÒ ñóùåñòâóåò 1-ïðèáëèæåííûé àëãîðèòìñ ïîëèíîìèàëüíîé ñëîæíîñòüþ.Ìû äîëæíû ïîñòðîèòü àëãîðèòì H äëÿ ÇÊÍÒòàêîé, ÷òî âñåãäà FH 6 2Fîïò . Ïðèìåíèì ê çàäàííîìó ãðàôó Kn ñ âåñàìèd àëãîðèòì ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ äëÿ ïîñòðîåíèÿ êðàò÷àéøåãîîñòîâíîãî äåðåâà (ñì.
ï. 4.8). Ïóñòü îí ñòðîèò êðàò÷àéøåå îñòîâíîåäåðåâî D ñ ñóììàðíûì âåñîì ðåáåð d(D). Ïóñòü C ëþáîé ãàìèëüòîíîâöèêë. Åñëè âûáðîñèòü ëþáîå ðåáðî èç C , òî ïîëó÷èì äåðåâî T . Ïðè ýòîìÄîêàçàòåëüñòâî.d(D) 6 d(T ) 6 d(C).Ïîýòîìó d(D) 6 Fîïò . Ðàññìîòðèì äåðåâî D è çàìåíèì êàæäîå ðåáðîe = (vi , vj ) â D äâóìÿ ðåáðàìè e0 = (vi , vj ) è e00 = (vi , vj ). Òîãäà ïîëó÷èììóëüòèãðàô K (ãðàô ñ êðàòíûìè ðåáðàìè), â êîòîðîì ñòåïåíü êàæäîéâåðøèíû ÷åòíà. Òàê êàê D îñòîâíîå äåðåâî, òî ìóëüòèãðàô K ñâÿçíûé.Âûøå äîêàçàíî (ñì. òåîðåìó 4.19), ÷òî â ëþáîì ñâÿçíîì ìóëüòèãðàôå,â êîòîðîì ñòåïåíè âñåõ âåðøèí ÷åòíû, ñóùåñòâóåò ýéëåðîâ öèêë.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
