Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений
Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимац...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2015 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/101323 |
| 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: | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений / С.В. Листровой, С.В. Моцный // Электронное моделирование. — 2015. — Т. 37, № 6. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101323 |
|---|---|
| record_format |
dspace |
| spelling |
Листровой, С.В. Моцный, С.В. 2016-06-02T14:40:32Z 2016-06-02T14:40:32Z 2015 Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений / С.В. Листровой, С.В. Моцный // Электронное моделирование. — 2015. — Т. 37, № 6. — С. 3-17. — Бібліогр.: 12 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101323 519.854 Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимации. Приведены результаты экспериментального анализа, свидетельствующие о преимуществе описанного алгоритма по сравнению с существующими. Запропоновано алгоритм роз’язку задачі про найменше покриття довільного графа за допомогою систем квадратичних рівнянь, які дозволяють досягати високого ступіню розпаралелювання операцій. Для розв’язку цієї задачі на практиці використовують наближені алгоритми з різними коефіцієнтами апроксимації. Наведено результати експериментального аналізу, які свідчать про перевагу описаного алгоритму в порівнянні з існуючими. This paper presents an algorithm for solving the minimum vertex cover problem for the arbitrary graphs using systems of quadratic equations that provide high level of the operations parallelization. Approximation algorithms with different approximation coefficients can be used in practice to solve such problems. Experimental analysis shows the advantages of the described methodology in comparison with existing implementations. The algorithm effectiveness can be significantly enhanced by the use of distributed systems with many cores. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений The minimum vertex cover problem solving algorithm for an arbitrary graph with using the systems of quadratic equations 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 |
2015 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| title_alt |
The minimum vertex cover problem solving algorithm for an arbitrary graph with using the systems of quadratic equations |
| description |
Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимации. Приведены результаты экспериментального анализа, свидетельствующие о преимуществе описанного алгоритма по сравнению с существующими.
Запропоновано алгоритм роз’язку задачі про найменше покриття довільного графа за допомогою систем квадратичних рівнянь, які дозволяють досягати високого ступіню розпаралелювання операцій. Для розв’язку цієї задачі на практиці використовують наближені алгоритми з різними коефіцієнтами апроксимації. Наведено результати експериментального аналізу, які свідчать про перевагу описаного алгоритму в порівнянні з існуючими.
This paper presents an algorithm for solving the minimum vertex cover problem for the arbitrary graphs using systems of quadratic equations that provide high level of the operations parallelization. Approximation algorithms with different approximation coefficients can be used in practice to solve such problems. Experimental analysis shows the advantages of the described methodology in comparison with existing implementations. The algorithm effectiveness can be significantly enhanced by the use of distributed systems with many cores.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101323 |
| citation_txt |
Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений / С.В. Листровой, С.В. Моцный // Электронное моделирование. — 2015. — Т. 37, № 6. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
| work_keys_str_mv |
AT listrovoisv algoritmrešeniâzadačionaimenʹšemveršinnompokrytiiproizvolʹnogografaspomoŝʹûsistemkvadratičnyhuravnenii AT mocnyisv algoritmrešeniâzadačionaimenʹšemveršinnompokrytiiproizvolʹnogografaspomoŝʹûsistemkvadratičnyhuravnenii AT listrovoisv theminimumvertexcoverproblemsolvingalgorithmforanarbitrarygraphwithusingthesystemsofquadraticequations AT mocnyisv theminimumvertexcoverproblemsolvingalgorithmforanarbitrarygraphwithusingthesystemsofquadraticequations |
| first_indexed |
2025-11-25T23:07:30Z |
| last_indexed |
2025-11-25T23:07:30Z |
| _version_ |
1850580783818866688 |
| fulltext |
ÓÄÊ 519.854
Ñ.Â. Ëèñòðîâîé, ä-ð òåõí. íàóê, Ñ.Â. Ìîöíûé, àñïèðàíò
Óêðàèíñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò æåëåçíîäîðîæíîãî òðàíñïîðòà
(Óêðàèíà, 61050, Õàðüêîâ, ïë. Ôåéåðáàõà, 7,
òåë. +380509355042, +380987290907,
e-mail: om1@yandex.ru, stanislav.motsnyi@gmail.com)
Àëãîðèòì ðåøåíèÿ çàäà÷è î íàèìåíüøåì
âåðøèííîì ïîêðûòèè ïðîèçâîëüíîãî ãðàôà
ñ ïîìîùüþ ñèñòåì êâàäðàòè÷íûõ óðàâíåíèé
Ïðåäëîæåí àëãîðèòì ðåøåíèÿ çàäà÷è î íàèìåíüøåì ïîêðûòèè ïðîèçâîëüíîãî ãðàôà ñ
ïîìîùüþ ñèñòåì êâàäðàòè÷íûõ óðàâíåíèé, êîòîðûå ïîçâîëÿþò äîñòèãàòü âûñîêîé ñòåïå-
íè ðàñïàðàëëåëèâàíèÿ îïåðàöèé. Äëÿ ðåøåíèÿ ýòîé çàäà÷è íà ïðàêòèêå èñïîëüçóþòñÿ
ïðèáëèæåííûå àëãîðèòìû ñ ðàçëè÷íûìè êîýôôèöèåíòàìè àïïðîêñèìàöèè. Ïðèâåäåíû
ðåçóëüòàòû ýêñïåðèìåíòàëüíîãî àíàëèçà, ñâèäåòåëüñòâóþùèå î ïðåèìóùåñòâå îïèñàí-
íîãî àëãîðèòìà ïî ñðàâíåíèþ ñ ñóùåñòâóþùèìè.
Çàïðîïîíîâàíî àëãîðèòì ðîç’ÿçêó çàäà÷³ ïðî íàéìåíøå ïîêðèòòÿ äîâ³ëüíîãî ãðàôà çà äî-
ïîìîãîþ ñèñòåì êâàäðàòè÷íèõ ð³âíÿíü, ÿê³ äîçâîëÿþòü äîñÿãàòè âèñîêîãî ñòóï³íþ ðîçïà-
ðàëåëþâàííÿ îïåðàö³é. Äëÿ ðîçâ’ÿçêó ö³º¿ çàäà÷³ íà ïðàêòèö³ âèêîðèñòîâóþòü íàáëèæåí³
àëãîðèòìè ç ð³çíèìè êîåô³ö³ºíòàìè àïðîêñèìàö³¿. Íàâåäåíî ðåçóëüòàòè åêñïåðèìåíòàëüíîãî
àíàë³çó, ÿê³ ñâ³ä÷àòü ïðî ïåðåâàãó îïèñàíîãî àëãîðèòìó â ïîð³âíÿíí³ ç ³ñíóþ÷èìè.
Ê ë þ ÷ å â û å ñ ë î â à: âåðøèííîå ïîêðûòèå, ñòåïåíü àïïðîêñèìàöèè, ñèñòåìû êâàäðà-
òè÷íûõ óðàâíåíèé, ÷àñòîòà ïîÿâëåíèÿ ñëàãàåìûõ.
Ïðîáëåìà ïîèñêà íàèìåíüøåãî ïîêðûòèÿ â ïðîèçâîëüíîì ãðàôå áûëà îä-
íîé èç ïåðâûõ çàäà÷, âûäåëåííûõ â êàòåãîðèþ NP-ïîëíûõ [1]. Áûëî ñäåëà-
íî ìíîæåñòâî ïîïûòîê ðàçðàáîòàòü ìåòîäû, êîòîðûå ïîçâîëèëè áû íàéòè
òî÷íîå ðåøåíèå çà ïîëèíîìèàëüíîå âðåìÿ. Îäíàêî äî ñèõ ïîð èçâåñòíû
ëèøü àëãîðèòìû [2], äàþùèå ïðèáëèæåííûé ðåçóëüòàò, ò.å. âîñïðîèçâî-
äÿùèå òàêîå âåðøèííîå ïîêðûòèå, â êîòîðîì ÷èñëî âåðøèí íå áîëåå ÷åì â
k ðàç ïðåâîñõîäèò ìèíèìàëüíî âîçìîæíîå (k — òî÷íîñòü ïðèáëèæåííîãî
àëãîðèòìà).
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 6 3
�����������
���
��
��
�����
�������
���
��������
��
� Ñ.Â. Ëèñòðîâîé, Ñ.Â. Ìîöíûé, 2015
 ïîñëåäíèå äåñÿòèëåòèÿ äàííîé ïðîáëåìå óäåëÿåòñÿ îñîáîå âíèìà-
íèå, òàê êàê çàäà÷ó î íàèìåíüøåì ïîêðûòèè ïðèõîäèòñÿ ÷àñòî ðåøàòü â
òåîðèè è íà ïðàêòèêå.  ÷àñòíîñòè, àëãîðèòìû ðåøåíèÿ ýòîé çàäà÷è øè-
ðîêî èñïîëüçóþòñÿ ïðè ìîíèòîðèíãå òåëåêîììóíèêàöèîííûõ ñåòåé [3],
äàâàÿ âîçìîæíîñòü ýôôåêòèâíî îáíàðóæèâàòü ìåäëåííûå è (èëè) íåèñ-
ïðàâíûå ó÷àñòêè, ïðè âûïîëíåíèè ïðîöåäóðû âûðàâíèâàíèÿ áèîëîãè÷åñ-
êèõ ïîñëåäîâàòåëüíîñòåé (áåëêîâ, ÐÍÊ, ÄÍÊ è äð.) [4], êîòîðàÿ ïîçâîëÿåò
àíàëèçèðîâàòü ñõîäíûå ó÷àñòêè â ýòèõ ïîñëåäîâàòåëüíîñòÿõ, èõ ñòðóê-
òóðíûå è ýâîëþöèîííûå âçàèìîñâÿçè, à òàêæå ïðè èññëåäîâàíèè ìíîãèõ
äðóãèõ ïðîáëåì âû÷èñëèòåëüíîé áèîëîãèè [5].
Äàííàÿ ïðîáëåìà àêòóàëüíà òàêæå ïðè ïëàíèðîâàíèè è ðàñïðåäåëåíèè
ðåñóðñîâ â ãåòåðîãåííûõ âûñîêîíàãðóæåííûõ ñèñòåìàõ, ãäå áîëüøîå
âëèÿíèå íà ïðîèçâîäèòåëüíîñòü îêàçûâàåò èìåííî âûáîð ýôôåêòèâíîãî
àëãîðèòìà íàõîæäåíèÿ íàèìåíüøåãî ïîêðûòèÿ, êîòîðûé îáåñïå÷èâàë áû
óñòîé÷èâîñòü ñèñòåìû ïðè âûñîêîé èíòåíñèâíîñòè ïîñòóïëåíèÿ çàäàíèé
è âûáîðêó íåîáõîäèìûõ ðåñóðñîâ ñ ìèíèìàëüíûìè çàòðàòàìè.
Íåñìîòðÿ íà òî ÷òî òî÷íûå àëãîðèòìû ðåøåíèÿ äàííîé çàäà÷è íåöå-
ëåñîîáðàçíî èñïîëüçîâàòü íà ïðàêòèêå ââèäó èõ ÷ðåçâû÷àéíî âûñîêîé
âðåìåííîé ñëîæíîñòè, â áîëüøèíñòâå ñëó÷àåâ äîñòàòî÷íî óðîâíÿ àïïðîê-
ñèìàöèè áîëåå áûñòðûõ ïðèáëèæåííûõ ìåòîäîâ.
Àíàëèç ïîñëåäíèõ èññëåäîâàíèé. Â ïîñëåäíèå ãîäû ïðîáëåìà íà-
õîæäåíèÿ îïòèìàëüíîãî àëãîðèòìà ðåøåíèÿ çàäà÷è î íàèìåíüøåì ïîêðûòèè
ðàññìàòðèâàëàñü ñ ó÷åòîì ôèêñèðîâàííîé ïàðàìåòðè÷åñêîé ñëîæíîñòè [6]. Â
îñíîâå ïàðàìåòðè÷åñêîãî ìîäåëèðîâàíèÿ ëåæèò èäåÿ ðàçäåëåíèÿ ïðîáëåìû
íà äâå ñîñòàâëÿþùèå. Ñ îäíîé ñòîðîíû, èìååòñÿ ñîâîêóïíîñòü ìíîæåñòâà
âõîäíûõ äàííûõ, à ñ äðóãîé, — ìíîæåñòâî ðàçëè÷íûõ ïàðàìåòðîâ, òàê èëè
èíà÷å âëèÿþùèõ íà îáùóþ âû÷èñëèòåëüíóþ ñëîæíîñòü èññëåäóåìîãî àëãî-
ðèòìà. Ýòî ïîçâîëÿåò ñôîðìèðîâàòü áîëåå ãèáêóþ êëàññèôèêàöèþ NP-
ñëîæíûõ ïðîáëåì ïî ñðàâíåíèþ ñ êëàññè÷åñêèì ïîäõîäîì, êîãäà ñëîæ-
íîñòü àëãîðèòìà çàâèñèò òîëüêî îò âõîäíîãî ïîòîêà.
Ìíîãèå çàäà÷è âû÷èñëèòåëüíîé òåîðèé ñëîæíîñòè ìîãóò áûòü ïðåä-
ñòàâëåíû â ñëåäóþùåì âèäå. Ïóñòü èìååòñÿ ýêçåìïëÿð x è íåîòðèöàòåëü-
íîå öåëîå ÷èñëî k. Îáëàäàåò ëè x òàêèìè ñâîéñòâàìè, êîòîðûå çàâèñÿò îò k?
Äëÿ çàäà÷è î âåðøèííîì ïîêðûòèè ïàðàìåòðîì k ìîæåò áûòü ÷èñëî âåð-
øèí, êîòîðîå íåîáõîäèìî íàéòè. Î÷åâèäíî, ÷òî ïàðàìåòð k âåñüìà âàæåí
ïðè îöåíêå ñëîæíîñòè ðåøåíèÿ çàäà÷è. Åñëè ïðåäïîëîæèòü, ÷òî P � NP, òî
ñóùåñòâóåò áîëüøîå ÷èñëî ïðîáëåì, äëÿ ðåøåíèÿ êîòîðûõ òðåáóåòñÿ ýêñ-
ïîíåíöèàëüíîå âû÷èñëèòåëüíîå âðåìÿ.
Ïðè èñïîëüçîâàíèè ïàðàìåòðè÷åñêîãî ïîäõîäà ýòè ïðîáëåìû ìîæíî
ðåøèòü çà ïîëèíîìèàëüíîå âðåìÿ ïðè óñëîâèè, ÷òî âõîäíîé ïàðàìåòð k
Ñ.Â. Ëèñòðîâîé, Ñ.Â. Ìîöíûé
4 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 6
èìååò ôèêñèðîâàííîå çíà÷åíèå. Èíûìè ñëîâàìè, åñëè èìååòñÿ íå-
êîòîðàÿ ôóíêöèÿ f k( ), âëèÿþùàÿ íà ïàðàìåòðè÷åñêóþ ñëîæíîñòü àëãî-
ðèòìà, è k ðàâíÿåòñÿ îòíîñèòåëüíî íåáîëüøîìó öåëî÷èñëåííîìó çíà÷å-
íèþ, òî âû÷èñëèòåëüíàÿ ñëîæíîñòü ðàâíà O f k nO( ( ) )( )� 1 , ãäå n — ÷èñëî
âõîäíûõ äàííûõ.
Çàäà÷è, â êîòîðûõ èñïîëüçóåòñÿ ôèêñèðîâàííûé ïàðàìåòð k, íàçû-
âàþòñÿ ïàðàìåòðèçèðîâàííûìè è îòíîñÿòñÿ ê êëàññó ñëîæíîñòè FPT
(Fixed-parameter tractability — âûïîëíèìîñòü ïðè ôèêñèðîâàííîì ïàðà-
ìåòðå). Çàäà÷à î âåðøèííîì ïîêðûòèè òàêæå îòíîñèòñÿ ê äàííîìó êëàññó.
Óæå äàâíî ïðîâîäÿòñÿ èññëåäîâàíèÿ, ñâÿçàííûå ñ ïîèñêîì íàèáîëåå áûñò-
ðîãî ïàðàìåòðèçèðîâàííîãî àëãîðèòìà. Â íàñòîÿùåå âðåìÿ îäèí èç ñàìûõ
áûñòðûõ àëãîðèòìîâ ðåøàåò äàííóþ çàäà÷ó çà O kn k( , )�1 2738 øàãîâ [7].
Ïðè ðåøåíèè îïòèìèçàöèîííûõ çàäà÷ íà ïðàêòèêå ÷àñòî èñïîëüçóþò
ïðèáëèæåííûå àëãîðèòìû, âàæíåéøåé õàðàêòåðèñòèêîé êîòîðûõ ÿâëÿåò-
ñÿ êîýôôèöèåíò àïïðîêñèìàöèè.
Äîêàçàíî, ÷òî â ñëó÷àå p-àïïðîêñèìèðîâàííîãî àëãîðèòìà [2] îòíîøå-
íèå f x( ) (çíà÷åíèå—ñòîèìîñòü) äëÿ NP- òðóäíîé çàäà÷è x óäîâëåòâîðÿåò
ñëåäóþùèì îãðàíè÷åíèÿì:
OPT f x pOPT p� � �( ) , 1,
pOPT f x OPT p� � �( ) , 1,
(1)
ãäå OPT — òî÷íîå ðåøåíèå ïîñòàâëåííîé çàäà÷è x; f x( ) — îòíîøåíèå
çíà÷åíèå—ñòîèìîñòü â ðåøåíèè çàäà÷è x, îïðåäåëÿþùåå ñòåïåíü àïïðîê-
ñèìàöèè.
Äëÿ îöåíêè êà÷åñòâà ðàáîòû àïïðîêñèìèðîâàííîãî àëãîðèòìà ÷àñòî
èñïîëüçóåòñÿ ïîíÿòèå îòíîñèòåëüíîé ïîãðåøíîñòè. Ïóñòü s — ïðèáëè-
æåííîå ðåøåíèå, s* — ñîîòâåòñòâóþùåå îïòèìàëüíîå ðåøåíèå, c è ñ* —
âðåìåííûå çàòðàòû ðàáîòû àëãîðèòìà. Òîãäà îòíîñèòåëüíàÿ ïîãðåøíîñòü
îïðåäåëÿåòñÿ òàê:
�� ( )
( ) ( )
( )
*
*
s
c s c s
c s
. (2)
Îäèí èç íàèáîëåå îïòèìàëüíûõ àëãîðèòìîâ ïðåäëîæåí â ðàáîòå [8],
ãäå êîýôôèöèåíò àïïðîêñèìàöèè óäàëîñü óìåíüøèòü â ñîîòâåòñòâèè ñ (1)
äî 2
�
�
�
�
�
�
�
�
�
��
�
logn
. Â îñíîâå äàííîãî àëãîðèòìà ëåæèò ñáàëàíñèðîâàííîå
ðàçáèåíèå ãðàôà ïî çàäàííûì ïðàâèëàì, à òàêæå èñïîëüçîâàíèå ìåòîäîâ
ïîëóîïðåäåëåííîãî ïðîãðàììèðîâàíèÿ. Îäíàêî íà ïðàêòèêå ïðè âûáîðå
Àëãîðèòì ðåøåíèÿ çàäà÷è î íàèìåíüøåì âåðøèííîì ïîêðûòèè ïðîèçâîëüíîãî ãðàôà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 6 5
ïðèáëèæåííîãî àëãîðèòìà äëÿ äîñòèæåíèÿ íàèáîëåå îïòèìàëüíûõ ïîêà-
çàòåëåé ïîãðåøíîñòè (2) íåîáõîäèìî ó÷èòûâàòü êîíêðåòíóþ ìîäåëü èñïîëü-
çóåìîãî ãðàôà. Íàïðèìåð, äëÿ ãðàôîâ ñ íèçêîé ïëîòíîñòüþ ðàñïðåäåëåíèÿ
âåðøèí ïðåäëîæåí ìåòîä [9], îñíîâàííûé íà ýâðèñòè÷åñêîì âàðèàíòå
ïîèñêà ñ ðåêîìáèíàöèåé ðåøåíèé-êàíäèäàòîâ. Ýòîò àëãîðèòì îòíîñèòñÿ ê
ðàçðÿäó ãåíåòè÷åñêèõ, îòëè÷èòåëüíîé îñîáåííîñòüþ êîòîðûõ ÿâëÿåòñÿ èñïîëü-
çîâàíèå ìåõàíèçìîâ, àíàëîãè÷íûõ åñòåñòâåííîìó îòáîðó â ïðèðîäå.
 ðàáîòå [10] îïèñàí ïðèáëèæåííûé àëãîðèòì, îñíîâàííûé íà êàíî-
íè÷åñêîì ñòàòèñòè÷åñêîì àíàëèçå Ìîíòå-Êàðëî, ñ ïîìîùüþ êîòîðîãî
ìîæíî ïðîâîäèòü âûáîðêó âåðøèí äëÿ çàíåñåíèÿ â ïîêðûòèå ñ ïðîãíî-
çèðîâàííîé âåðîÿòíîñòüþ.  îòëè÷èå îò äðóãèõ ýòîò àëãîðèòì ïîçâîëÿåò
áàëàíñèðîâàòü ìåæäó íåîáõîäèìîé òî÷íîñòüþ è ñëîæíîñòüþ âû÷èñëè-
òåëüíûõ îïåðàöèé.
Ê íåäîñòàòêàì ïîïóëÿðíûõ ìåòîäîâ ðåøåíèÿ çàäà÷è î íàèìåíüøåì
ïîêðûòèè ìîæíî îòíåñòè íåðåøåííóþ ïðîáëåìó ðàñïàðàëëåëèâàíèÿ îïå-
ðàöèé äëÿ ïîâûøåíèÿ ýôôåêòèâíîñòè âûïîëíåíèÿ â ðàñïðåäåëåííûõ ñðå-
äàõ, à òàêæå ñëèøêîì âûñîêèå ôèêñèðîâàííûå êîýôôèöèåíòû, ñíèæàþ-
ùèå ïðîèçâîäèòåëüíîñòü äàæå ïðè íåáîëüøèõ âõîäíûõ çíà÷åíèÿõ.
Ïðè ðàçðàáîòêå îïòèìàëüíîãî àëãîðèòìà ðåøåíèÿ çàäà÷è î íàèìåíü-
øåì ïîêðûòèè â ïðîèçâîëüíûõ ãðàôàõ äëÿ ïðèìåíåíèÿ â ðàñïðåäåëåííûõ
ñðåäàõ è óñëîâèÿõ âûñîêîé íàãðóçêè ñ óëó÷øåííûìè ïî ñðàâíåíèþ ñ ñó-
ùåñòâóþùèìè ìåòîäîëîãèÿìè õàðàêòåðèñòèêàìè îñîáîå âíèìàíèå óäå-
ëåíî óëó÷øåíèþ ïîêàçàòåëÿ àïïðîêñèìàöèè ïîëó÷àåìûõ ðåøåíèé. Ðå-
çóëüòàòû ýêñïåðèìåíòàëüíîãî àíàëèçà ïîçâîëèëè îöåíèòü âîçìîæíîñòü
èñïîëüçîâàíèÿ ïðåäëàãàåìîé ìåòîäèêè äëÿ ðåøåíèÿ äðóãèõ çàäà÷ ïîäîá-
íîãî êëàññà ñëîæíîñòè.
Ïîñòàíîâêà è ðåøåíèå çàäà÷è. Äëÿ îáùåé ôîðìàëèçàöèè çàäà÷è î
íàèìåíüøåì ïîêðûòèè èñïîëüçóåì ïîíÿòèå ïðîèçâîëüíîãî íåîðèåíòè-
ðîâàííîãî ãðàôà, ïîä êîòîðûì ïîäðàçóìåâàåòñÿ ïàðà G (V, E), ãäå V — ìíî-
æåñòâî âåðøèí, E — ìíîæåñòâî ðåáåð äàííîãî ãðàôà. Ðåáðîì â íåîðèåíòè-
ðîâàííîì ãðàôå íàçûâàþò íåóïîðÿäî÷åííóþ ïàðó âåðøèí ( , )u v E� . Âåð-
øèííûì ïîêðûòèåì äàííîãî ãðàôà ÿâëÿåòñÿ òàêîå ïîäìíîæåñòâî âåðøèí
� �V V , ÷òî êàæäîå ðåáðî ( , )u v G� óäîâëåòâîðÿåò ñëåäóþùåìó êðèòåðèþ:
u V v V� �� � � (ò.å. ìíîæåñòâó �V ïðèíàäëåæèò õîòÿ áû îäíà èç âåðøèí u èëè
v).  çàäà÷å î íàèìåíüøåì ïîêðûòèè òðåáóåòñÿ íàéòè ìèíèìàëüíî âîçìîæ-
íûé ðàçìåð âåðøèííîãî ïîêðûòèÿ â èññëåäóåìîì ãðàôå.
Ïðåäëàãàåìûé àëãîðèòì ðåøåíèÿ ïîñòàâëåííîé çàäà÷è ñîñòîèò èç
äâóõ ïðîöåäóð: A è B. Ïðîöåäóðà A ñîñòîèò èç 11 áàçîâûõ øàãîâ. Ïðè
âûïîëíåíèè ýòèõ øàãîâ ïåðèîäè÷åñêè âîçíèêàåò íåîáõîäèìîñòü â âûçîâå
âñïîìîãàòåëüíîé ïðîöåäóðû B, êîòîðàÿ, â ñâîþ î÷åðåäü, ïîçâîëÿåò ïðî-
Ñ.Â. Ëèñòðîâîé, Ñ.Â. Ìîöíûé
6 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 6
âåñòè ïðîâåðêó íà íàëè÷èå â ãðàôå âèñÿ÷èõ âåðøèí. Ïîä âèñÿ÷åé ïîäðàçó-
ìåâàåòñÿ âåðøèíà, êîòîðàÿ ÿâëÿåòñÿ êîíöîì ðîâíî îäíîãî ðåáðà.
Ìèíèìàëüíîå âåðøèííîå ïîêðûòèå çàâèñèò îò ëîêàëüíîé ñòðóêòóðû
âûáðàííîãî ãðàôà. Îáùàÿ òîïîëîãèÿ è ïëîòíîñòü ðàñïðåäåëåíèÿ ïîçâî-
ëÿåò ïðîâîäèòü ïðîãíîçèðîâàííóþ âûáîðêó ïàð âåðøèí ñ íàèáîëåå îïòè-
ìàëüíîé îáùåé ñòåïåíüþ. Íà îñíîâàíèè ýòîé âûáîðêè ñîñòàâëÿåòñÿ ñèñ-
òåìà êâàäðàòè÷íûõ óðàâíåíèé, ïðè ðåøåíèè êîòîðîé, â çàâèñèìîñòè îò
êîíêðåòíîãî øàãà àëãîðèòìà, âîçâðàùàåòñÿ ëèáî ÷àñòè÷íûé R z
�, ëèáî ïîë-
íûé R z
ï ðåçóëüòàò.
Ïîëó÷åííûé ðåçóëüòàò ÿâëÿåòñÿ íàèìåíüøèì ïîêðûòèåì çàäàííîãî
ãðàôà. Ïåðåìåííàÿ z â äàííîì ñëó÷àå õàðàêòåðèçóåò âàðèàíò ïðîãíîçèðî-
âàíèÿ, ò.å. âûáîð ñëàãàåìîãî èç îäíîé èç òðåõ âîçìîæíûõ ïàð ïåðåìåííûõ,
ðàññìàòðèâàåìûõ íà øàãå 3.
Ïðîöåäóðà A. Øàãè ïîèñêà ìèíèìàëüíîãî âåðøèííîãî ïîêðûòèÿ â
ïðîèçâîëüíîì ãðàôå ñëåäóþùèå:
Ø à ã 1. Ïî çàäàííîìó ãðàôó ôîðìèðóåì èñõîäíîå êâàäðàòè÷íîå óðàâ-
íåíèå:
f x xz i j( ) 0 , (3)
ãäå x xi j — ïàðû ïåðåìåííûõ, ñîîòâåòñòâóþùèå âåðøèíàì ãðàôà. Îäíà èç
ïåðåìåííûõ äëÿ îáðàçîâàíèÿ ïîêðûòèÿ äîëæíà áûòü ðàâíà íóëþ.
Ø à ã 2. Îáðàáàòûâàåì óðàâíåíèå (3) ñ ïîìîùüþ âñïîìîãàòåëüíîé
ïðîöåäóðû B. Åñëè ïðîöåäóðà B âîçâðàùàåò âòîðîé âîçìîæíûé âàðèàíò
ðåçóëüòàòà (âñå âîçìîæíûå ðåçóëüòàòû ïåðå÷èñëåíû â îïèñàíèè ïðîöå-
äóðû B), òî ìèíèìàëüíîå ïîêðûòèå íàéäåíî. Îíî ÿâëÿåòñÿ ïîëíûì ðåøå-
íèåì R z
ï , è ïðîöåäóðà A çàêàí÷èâàåò ðàáîòó. Åñëè ïîëó÷åí ïåðâûé èëè
òðåòèé âîçìîæíûé ðåçóëüòàò ðàáîòû ïðîöåäóðû B, òî ïåðåõîäèì ê ñëå-
äóþùåìó øàãó.
Ø à ã 3.  çàâèñèìîñòè îò òîãî, êàêîé ðåçóëüòàò ïîëó÷åí íà ïðåäû-
äóùåì øàãå, â óðàâíåíèè (3) èëè ïðîèçâîäíîì îò íåãî óðàâíåíèè
f x xz i j
| ( ) 0, èìåþùåì ÷àñòè÷íîå ðåøåíèå R z
�, íàõîäèì ñëàãàåìîå
S x xp l m
* ñ ìàêñèìàëüíîé ñóììàðíîé ÷àñòîòîé ïîÿâëåíèÿ ïåðåìåííûõ â
òåêóùåì óðàâíåíèè (h h hs l m � ) è ôîðìèðóåì òðè ïðîãíîçèðóåìûå ïàðû
ïåðåìåííûõ: x l 0, xm 0; x l 1, xm 0; x l 1, xm 1. Çàòåì ïåðåõîäèì ê
ñëåäóþùåìó øàãó.
Ø à ã 4. Ïåðåìåííîé z ïðèñâàèâàåì çíà÷åíèå 1 è ïîäñòàâëÿåì ïåðâóþ
ïàðó ïåðåìåííûõ x l 0, xm 0 â òåêóùåå óðàâíåíèå. Ïîëó÷àåì íîâîå òå-
êóùåå óðàâíåíèå f x xi j1 0( ) , à ïåðåìåííûå x l è xm âíîñèì â ÷àñòè÷íîå
ðåøåíèå R z
�. Ïðèìåíÿåì ê òåêóùåìó óðàâíåíèþ ïðîöåäóðó B. Åñëè â
ðåçóëüòàòå ðàáîòû ïðîöåäóðû B ïîëó÷åí âòîðîé âàðèàíò, òî ïîêðûòèå
Àëãîðèòì ðåøåíèÿ çàäà÷è î íàèìåíüøåì âåðøèííîì ïîêðûòèè ïðîèçâîëüíîãî ãðàôà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 6 7
íàéäåíî, îíî îïðåäåëÿåòñÿ ïîëíûì ðåøåíèåì R z
ï . Çàïîìèíàåì åãî è ïå-
ðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 5.  çàâèñèìîñòè îò òîãî, êàêîé ðåçóëüòàò ïîëó÷åí íà ïðåäûäó-
ùåì øàãå â ðåçóëüòàòå ðàáîòû ïðîöåäóðû B, óðàâíåíèå f x xi j1 0( ) (èëè
f x xi j1
0| ( ) ) âìåñòå ñ õàðàêòåðèçóþùèì åãî òåêóùèì ÷àñòè÷íûì ðåøå-
íèåì çàíîñèì âî ìíîæåñòâî Ì, êóäà çàíîñèì òàêæå âñå ïîëíûå ðåøåíèÿ R z
ï ,
ïîëó÷åííûå íà ïðåäûäóùèõ øàãàõ. Ïåðåõîäèì ê ñëåäóþùåìó øàãó.
Ø à ã 6. Ïåðåìåííîé z ïðèñâàèâàåì çíà÷åíèå 2 è ïîäñòàâëÿåì âòîðóþ
ïàðó ïåðåìåííûõ x l 1, xm 0 â òåêóùåå óðàâíåíèå. Ïîëó÷àåì íîâîå òå-
êóùåå óðàâíåíèå f x xi j2 0( ) . Ñëàãàåìûå (x xt j ) óðàâíåíèÿ (3), ñîäåð-
æàùèå ïî îäíîé ïåðåìåííîé{ }x t , ïðèðàâíèâàåì íóëþ. Â ðåçóëüòàòå ïîëó-
÷àåì íîâîå òåêóùåå óðàâíåíèå f x xi j2
0| ( ) . Ïåðåìåííûå { }x j , ñîñåäíèå ñ
{ }x t , è ïåðåìåííóþ xm çàíîñèì â ÷àñòè÷íîå ðåøåíèå R z
�. Ïðèìåíÿåì ê
òåêóùåìó óðàâíåíèþ ïðîöåäóðó B. Åñëè ïðè ýòîì ïîëó÷àåì âòîðîé âà-
ðèàíò ðåçóëüòàòà ðàáîòû ïðîöåäóðû B, òî ïîêðûòèå íàéäåíî, îíî îïðå-
äåëÿåòñÿ ïîëíûì ðåøåíèåì R z
ï . Çàïîìèíàåì åãî è ïåðåõîäèì ê âûïîë-
íåíèþ ñëåäóþùåãî øàãà.
Ø à ã 7. Óðàâíåíèå f x xi j2
0| ( ) (èëè f x xi j2
0|| ( ) , â çàâèñèìîñòè îò
òîãî, êàêîé ðåçóëüòàò ïîëó÷åí íà ïðåäûäóùåì øàãå ïðîöåäóðû B) âìåñòå ñ
õàðàêòåðèçóþùèì åãî òåêóùèì ÷àñòè÷íûì ðåøåíèåì çàíîñèì âî ìíî-
æåñòâî Ì, êóäà çàíîñèì òàêæå âñå ïîëíûå ðåøåíèÿ R z
ï , ïîëó÷åííûå íà
ïðåäûäóùèõ øàãàõ, è ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 8. Ïåðåìåííîé z ïðèñâàèâàåì çíà÷åíèå 3 è ïîäñòàâëÿåì òðåòüþ
ïàðó ïåðåìåííûõ x l 0, xm 1 â òåêóùåå óðàâíåíèå. Ïîëó÷àåì íîâîå òå-
êóùåå óðàâíåíèå f x xi j3 0( ) . Ïîëàãàåì ñëàãàåìûå (x xt j ) â äàííîì óðàâ-
íåíèè, ñîäåðæàùèå ïî îäíîé ïåðåìåííîé { }x t , ðàâíûìè íóëþ. Ïîëó÷àåì
íîâîå òåêóùåå óðàâíåíèå f x xi j3
0| ( ) , à ïåðåìåííûå{ }x j , ñîñåäíèå ñ{ }x t , è
ïåðåìåííóþ xl çàíîñèì â ÷àñòè÷íîå ðåøåíèå R z
�. Ïðèìåíÿåì ê òåêóùåìó
óðàâíåíèþ ïðîöåäóðó B. Åñëè ïîëó÷àåì âòîðîé âàðèàíò ðåçóëüòàòà ðàáîòû
ïðîöåäóðû B, òî ïîêðûòèå íàéäåíî. Îíî îïðåäåëÿåòñÿ ïîëíûì ðåøåíèåì
R z
ï , êîòîðîå çàïîìèíàåì è ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 9. Óðàâíåíèå f x xi j3
0| ( ) (èëè f x xi j3
0|| ( ) , â çàâèñèìîñòè îò
òîãî, êàêîé ðåçóëüòàò áûë ïîëó÷åí íà ïðåäûäóùåì øàãå â ðåçóëüòàòå
ðàáîòû ïðîöåäóðû B) âìåñòå ñ õàðàêòåðèçóþùèì åãî òåêóùèì ÷àñòè÷íûì
ðåøåíèåì çàíîñèì âî ìíîæåñòâî Ì, è òóäà æå çàíîñèì âñå ïîëíûå ðå-
øåíèÿ R z
ï , ïîëó÷åííûå íà ïðåäûäóùèõ øàãàõ. Ïåðåõîäèì ê âûïîëíåíèþ
ñëåäóþùåãî øàãà.
Ø à ã 10. Ïðîâåðÿåì, âñå ëè óðàâíåíèÿ â Ì ïðåâðàùåíû â òîæäåñòâà
âèäà 0 = 0. Åñëè äà, òî ñðåäè âñåõ ïîëíûõ ðåøåíèé {R z
ï} âûáèðàåì ìèíè-
ìàëüíîå, êîòîðîå è áóäåò îïðåäåëÿòü ìèíèìàëüíîå âåðøèííîå ïîêðûòèå
Ñ.Â. Ëèñòðîâîé, Ñ.Â. Ìîöíûé
8 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 6
ãðàôà. Íà ýòîì ïðîöåäóðà çàêàí÷èâàåò ðàáîòó, èíà÷å — âûïîëíÿåì ñëå-
äóþùèé øàã.
Ø à ã 11. Èç òåêóùèõ óðàâíåíèé f x xi j1 0( ) , f x xi j2 0( ) , f x xi j3 0( ) ,
êîòîðûå åùå íå îáðàòèëèñü â òîæäåñòâî âèäà 0 = 0, âûáèðàåì óðàâíåíèå
f x xi i j
* ( ) 0 ñ íàèáîëüøèì ÷èñëîì ñëàãàåìûõ. Ìåíÿåì èñïîëüçóåìîå óðàâ-
íåíèå (3) íà óðàâíåíèå f x xi i j
* ( ) 0 è ïåðåõîäèì ê âûïîëíåíèþ øàãà 2.
Âñÿ ïîñëåäîâàòåëüíîñòü øàãîâ ïîâòîðÿåòñÿ äî òåõ ïîð, ïîêà ìèíèìàëüíîå
âåðøèííîå ïîêðûòèå íå áóäåò íàéäåíî.
Ñëåäóåò çàìåòèòü, ÷òî åñëè íè îäíî èç òðåõ óðàâíåíèé íå îáðàùàåòñÿ â
òîæäåñòâî âèäà 0 = 0, òî âûáèðàåòñÿ óðàâíåíèå ñ ìàêñèìàëüíûì ÷èñëîì
ñëàãàåìûõ íåçàâèñèìî îò òîãî, âõîäÿò â íåãî äâà îñòàâøèõñÿ óðàâíåíèÿ
èëè íåò, âî ìíîæåñòâå Ì ïðè ýòîì ñîõðàíÿåòñÿ òîëüêî âûáðàííîå óðàâ-
íåíèå è ÷àñòè÷íîå ðåøåíèå, îòíîñÿùååñÿ ê îñòàâøåìóñÿ óðàâíåíèþ.
Ââåäåì âñïîìîãàòåëüíóþ ïðîöåäóðó B, êîòîðàÿ ïåðèîäè÷åñêè ïîâòî-
ðÿåòñÿ âíóòðè ïðîöåäóðû A. Ïðîöåäóðà B ïîçâîëÿåò âûïîëíÿòü ïðîâåðêó
íàëè÷èÿ â óðàâíåíèè ñëàãàåìûõ ñ ïåðåìåííûìè, âñòðå÷àþùèìèñÿ îäèí
ðàç. Ïîäîáíûå ïåðåìåííûå àññîöèèðîâàíû ñ âèñÿ÷èìè âåðøèíàìè ãðàôà.
Ñëåäîâàòåëüíî, îíè óäàëÿþòñÿ èç òåêóùåãî ðåøåíèÿ, à ñìåæíûå ñ íèìè
âåðøèíû çàíîñÿòñÿ â ïîêðûòèå, â ðåçóëüòàòå ÷åãî óäàåòñÿ èçáåæàòü èçáû-
òî÷íîñòè ïîëó÷àåìûõ ðåøåíèé è óëó÷øèòü ïîêàçàòåëü àïïðîêñèìàöèè
àëãîðèòìà.
Ïðîöåäóðà Â. Ïîèñê âèñÿ÷èõ âåðøèí.
Ø à ã 1. Ïðîâåðÿåì, åñòü ëè â óðàâíåíèè (3) ñëàãàåìûå x xq j �
� f x xi j*
( ) ñ ïåðåìåííûìè { }xq , âñòðå÷àþùèìèñÿ îäèí ðàç. Åñëè äà, òî
âñåì ïåðåìåííûì { }x j , ñîñåäíèì ñ { }xq , ïðèñâàèâàåì çíà÷åíèå, ðàâíîå
íóëþ, è âêëþ÷àåì èõ â ÷àñòè÷íîå ðåøåíèå Ri
�. Ïðè ýòîì óðàâíåíèå (3)
ïðåîáðàçóåòñÿ â óðàâíåíèå f x xz i j
| ( ) 0 ñ ìåíüøèì ÷èñëîì ñëàãàåìûõ.
Ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà, èíà÷å óðàâíåíèå (3) îñòàåòñÿ
íåèçìåííûì è ïðîöåäóðà çàêàí÷èâàåò ðàáîòó.
Ø à ã 2. Ïðîâåðÿåì, îáðàòèëîñü ëè óðàâíåíèå f x xz i j
| ( ) 0â òîæäåñòâî
âèäà 0 = 0. Åñëè äà, òî ÷àñòè÷íîå ðåøåíèå R z
� ñòàíîâèòñÿ ïîëíûì R z
ï , ïîñ-
êîëüêó ïåðåìåííûå, âîøåäøèå â Ri
ï , îïðåäåëÿþò âåðøèííîå ïîêðûòèå â
èñõîäíîì ãðàôå, è ïðîöåäóðà çàêàí÷èâàåò ðàáîòó. Åñëè íåò, òî ìåíÿåì óðàâ-
íåíèå (3) íà óðàâíåíèå f x xz i j
| ( ) 0 è ïåðåõîäèì ê âûïîëíåíèþ øàãà 1.
 ðåçóëüòàòå ïðèìåíåíèÿ ïðîöåäóðû B ê óðàâíåíèþ (3) ìîæíî ïîëó-
÷èòü òðè ñëåäóþùèõ âàðèàíòà:
1) óðàâíåíèå f x xz i j( ) 0 íå èçìåíÿåòñÿ;
2) óðàâíåíèå îáðàùàåòñÿ â òîæäåñòâî âèäà 0 = 0, è ïîëó÷àåì ïîëíîå
ðåøåíèå R z
ï;
Àëãîðèòì ðåøåíèÿ çàäà÷è î íàèìåíüøåì âåðøèííîì ïîêðûòèè ïðîèçâîëüíîãî ãðàôà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 6 9
3) ïîëó÷àåì íîâîå óðàâíåíèå f x xz i j
| ( ) 0 ñ ìåíüøèì ÷èñëîì ñëàãàå-
ìûõ è íåêîòîðîå ÷àñòè÷íîå ðåøåíèå R z
�.
Ðàññìîòðèì ïðèìåð èñïîëüçîâàíèÿ ïðåäëàãàåìîãî àëãîðèòìà. Ñîñòà-
âèì ïåðå÷åíü ñâÿçåé ìåæäó âåðøèíàìè èññëåäóåìîãî ãðàôà:
1: 3 6 7 8 12; 2: 5 6 9 11 12; 3: 1 4 5 7 8 9 10 11; 4: 3 6 8 9 10;
5: 2 3 7 8 11 12; 6: 1 2 4 7 8 9; 7: 1 3 5 6 8; 8: 1 3 4 5 6 7 9;
9: 2 3 4 6 8 10 12; 10: 3 4 9 11; 11: 2 3 5 10; 12: 1 2 5 9.
Ñîñòàâëÿåì èñõîäíîå óðàâíåíèå ãðàôà:
x x x x x x x x x x x x x x x x x x1 3 1 6 1 7 1 8 1 12 2 5 2 6 2 9 2 11� � � � � � � � �
� � �x x x x x x2 12 3 4 3 5� � � � � � �x x x x x x x x x x x x3 7 3 8 3 9 3 10 3 11 4 6
� � � � � � � � � �x x x x x x x x x x x x x x x x x x x4 8 4 9 4 10 5 7 5 8 5 11 5 12 6 7 6 8 6 9x �
� � � � � x x x x x x x x x x7 8 8 9 9 10 9 12 10 11 0. (4)
Ñïèñîê âåðøèííûõ ïîêðûòèé è íåçàâèñèìûõ ìíîæåñòâ äàííîãî ãðàôà
ïðåäñòàâëåí â ñëåäóþùåé òàáëèöå:
Ñ.Â. Ëèñòðîâîé, Ñ.Â. Ìîöíûé
10 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 6
Âåðøèííîå ïîêðûòèå Íåçàâèñèìîå ìíîæåñòâî
1 2 3 5 6 8 9 10 (8) 4 7 11 12 (4)
1 2 3 4 5 6 7 9 10 (9) 8 11 12 (3)
1 2 3 4 5 6 7 9 11 (9) 8 10 12 (3)
1 2 3 4 5 6 8 9 11 (9) 7 10 12 (3)
1 2 3 4 5 6 8 10 12 (9) 7 9 11 (3)
1 2 3 4 5 7 8 9 10 (9) 6 11 12 (3)
1 2 3 4 5 7 8 9 11 (9) 6 10 12 (3)
1 2 3 4 7 8 9 11 12 (9) 5 6 10 (3)
1 2 4 5 7 8 9 10 11 (9) 3 6 12 (3)
1 3 4 5 6 7 9 11 12 (9) 2 8 10 (3)
1 3 4 5 6 8 9 11 12 (9) 2 7 10 (3)
1 3 5 6 8 9 10 11 12 (9) 2 4 7 (3)
2 3 4 5 6 7 8 10 12 (9) 1 9 11 (3)
2 3 4 6 7 8 9 11 12 (9) 1 5 10 (3)
2 3 4 6 7 8 10 11 12 (9) 1 5 9 (3)
2 3 5 6 7 8 9 10 12 (9) 1 4 11 (3)
2 3 6 7 8 9 10 11 12 (9) 1 4 5 (3)
3 4 5 6 7 8 9 11 12 (9) 1 2 10 (3)
3 5 6 7 8 9 10 11 12 (9) 1 2 4 (3)
1 4 5 6 7 8 9 10 11 12 (10) 2 3 (2)
Îïðåäåëÿåì ÷àñòîòû hi
x ïîÿâëåíèÿ ïåðåìåííûõ X i â ñëàãàåìûõ óðàâ-
íåíèÿ (4) è íà îñíîâàíèè ïîëó÷åííûõ çíà÷åíèé ñîñòàâëÿåì òàáëèöó:
X i 1 2 3 4 5 6 7 8 9 10 11 12
hi
x
5 5 8 5 6 6 5 7 7 4 4 4
Âûáèðàåì ñëàãàåìîå ñ ìàêñèìàëüíîé ñóììàðíîé ÷àñòîòîé ïîÿâëåíèÿ
ïåðåìåííûõ â óðàâíåíèè (4). Òàêèì ÿâëÿåòñÿ ñëàãàåìîå õ3õ8 ñ ñóììàðíîé
÷àñòîòîé ïîÿâëåíèÿ 8 + 7 = 15. Íà îñíîâå ýòîãî ñëàãàåìîãî ôîðìèðóåì ñèñ-
òåìó èç òðåõ óðàâíåíèé, ó÷èòûâàÿ ïîî÷åðåäíî âûïîëíåíèå ñëåäóþùèõ
ïðîãíîçèðóåìûõ ðàâåíñòâ: õ3 = 0, õ8 = 0; õ3 = 0, õ8 = 1; õ3 = 1, õ8 = 0.
Ïåðâîå óðàâíåíèå ïîëó÷àåì, ó÷èòûâàÿ â (4) âûïîëíåíèå ïåðâîãî ðà-
âåíñòâà (õ3 = 0, õ8 = 0):
x x x x x x x x x x x x1 6 1 7 1 12 2 5 2 6 2 9� � � � � �
� � � � � � � � �x x x x x x x x x x x x x x x x2 11 2 12 4 6 4 9 4 10 5 7 5 11 5 12
� � � � � x x x x x x x x x x6 7 6 9 9 10 9 12 10 11 0. (5)
 ÷àñòè÷íîå ðåøåíèå ïåðâîãî óðàâíåíèÿ âêëþ÷àåì ïåðåìåííûå õ3, õ8.
Âòîðîå óðàâíåíèå (ïðè õ3 = 0, õ8 = 1) ïîëó÷àåì íà îñíîâàíèè òîãî, ÷òî ïåðå-
ìåííûå â (4) õ1 = 0, õ4 = 0, õ5 = 0, õ6 = 0, õ7 = 0, õ9 = 0, òàê êàê õ8 = 1. Ñëåäîâà-
òåëüíî, óðàâíåíèå (4) ïðèìåò âèä
x x x x x x2 11 2 12 10 11 0� � . (6)
Ïðè ýòîì â ÷àñòè÷íîå ðåøåíèå âêëþ÷àåì ïåðåìåííûå õ3 è ïåðåìåííûå õ1,
õ4, õ5, õ6, õ7, õ9. Òðåòüå óðàâíåíèå (ïðè õ3 = 1, õ8 = 0) ïîëó÷àåì àíàëîãè÷íî:
èç ðàâåíñòâà õ3 = 1 ñëåäóþò ðàâåíñòâà õ1 = 0, õ4 = 0, õ5 = 0, õ6 = 0, õ7 = 0, õ9 = 0,
õ10 = 0 è óðàâíåíèå (4) ïðèíèìàåò âèä
x x x x2 6 2 12 0� . (7)
 ÷àñòè÷íîå ðåøåíèå âêëþ÷àåì ïåðåìåííûå õ8 è õ1, õ4, õ5, õ6, õ7, õ9, õ10.
Ïîñêîëüêó ñëàãàåìûå óðàâíåíèé (6) è (7) âõîäÿò â óðàâíåíèå (5), óðàâ-
íåíèÿ (6) è (7) ìîãóò áûòü èñêëþ÷åíû èç äàëüíåéøåãî àíàëèçà.
Äàëåå îïðåäåëÿåì ÷àñòîòû ïîÿâëåíèÿ ïåðåìåííûõ äëÿ óðàâíåíèÿ (5) è
çàíîñèì èõ â ñëåäóþùóþ òàáëèöó:
X i 1 2 4 5 6 7 9 10 11 12
hi
x
3 5 3 4 5 3 4 3 3 4
Âûáèðàåì ñëàãàåìîå ñ ìàêñèìàëüíîé ñóììàðíîé ÷àñòîòîé ïîÿâëåíèÿ â (5).
Òàêèì ñëàãàåìûì ÿâëÿåòñÿ õ2õ6 ñ ñóììàðíîé ÷àñòîòîé 5 + 5 = 10. Íà îñíîâå
Àëãîðèòì ðåøåíèÿ çàäà÷è î íàèìåíüøåì âåðøèííîì ïîêðûòèè ïðîèçâîëüíîãî ãðàôà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 6 11
óðàâíåíèÿ (5) ôîðìèðóåì íîâóþ ñèñòåìó èç òðåõ óðàâíåíèé, ó÷èòûâàÿ
ïîî÷åðåäíî âûïîëíåíèå ñëåäóþùèõ ðàâåíñòâ: õ2 = 0, õ6 = 0; õ2 = 0, õ6 = 1;
õ2 = 1, õ6 = 0.
Ïåðâîå óðàâíåíèå ïîëó÷àåì èç (5) ñ ó÷åòîì ðàâåíñòâà õ2 = 0, õ6 = 0.
Ïîñëå îáíóëåíèÿ ñîîòâåòñòâóþùèõ ïåðåìåííûõ óðàâíåíèå (5) ïðèíèìàåò
ñëåäóþùèé âèä:
x x x x x x x x x x1 7 1 12 4 9 4 10 5 7� � � � �
� � � � � x x x x x x x x x x5 11 5 12 9 10 9 12 10 11 0. (8)
Ïðè ýòîì â ÷àñòè÷íîå ðåøåíèå âêëþ÷àåì õ2, õ6 è ïåðåìåííûå õ3, õ8,
âêëþ÷åííûå íà ïðåäûäóùåì øàãå. Âòîðîå óðàâíåíèå ïîëó÷àåì, ó÷èòûâàÿ,
÷òî â (5) õ2 = 0, õ6 = 1. Èç ðàâåíñòâà õ6 = 1 ñëåäóþò ðàâåíñòâà õ1 = 0, õ4 = 0,
õ7 = 0, õ7 = 0, õ9 = 0. Òàêèì îáðàçîì, óðàâíåíèå (5) ïðèíèìàåò âèä
x x x x x x x x5 7 5 11 5 12 10 11 0� � � . (9)
Òåïåðü â ÷àñòè÷íîå ðåøåíèå âêëþ÷àåì ïåðåìåííûå õ2 è õ1, õ4, õ7, õ9 .
Òðåòüå óðàâíåíèå (ïðè õ2 = 1, õ6 = 0) ïîëó÷àåì àíàëîãè÷íî: èç ðàâåíñòâà õ2 =
= 1 ñëåäóþò ðàâåíñòâà õ5 = 0, õ9 = 0, õ11 = 0, õ12 = 0. Óðàâíåíèå (5) ïðåîáðà-
çóåòñÿ ê âèäó
x x x x x x x x x x1 7 1 12 2 5 4 10 5 7 0� � � � . (10)
Ïðè ýòîì â ÷àñòè÷íîå ðåøåíèå âêëþ÷àåì ïåðåìåííûå õ6 è ïåðåìåííûå õ5,
õ9, õ11, õ12. Ñëàãàåìûå óðàâíåíèé (9) è (10) âõîäÿò â (8), ïîýòîìó óðàâíåíèÿ
(9) è (10) ìîãóò áûòü èñêëþ÷åíû èç äàëüíåéøåãî àíàëèçà.
Äàëåå îïðåäåëÿåì ÷àñòîòó ïîÿâëåíèÿ ïåðåìåííûõ â óðàâíåíèè (8) è
íà îñíîâàíèè ïîëó÷åííûõ ðåçóëüòàòîâ ôîðìèðóåì ñëåäóþùóþ òàáëèöó:
X i 1 4 5 7 9 10 11 12
hi
x
2 2 3 2 3 3 2 3
Âûáèðàåì ñëàãàåìîå ñ ìàêñèìàëüíîé ñóììàðíîé ÷àñòîòîé ïîÿâëåíèÿ
ïåðåìåííûõ â óðàâíåíèè (8). Òàêèì ÿâëÿåòñÿ ñëàãàåìîå õ9 õ10 ñ ñóììàðíîé
÷àñòîòîé ïîÿâëåíèÿ 3 + 3 = 6. Íà îñíîâå ýòîãî ñëàãàåìîãî ôîðìèðóåì ñèñ-
òåìó èç òðåõ óðàâíåíèé, ïîëàãàÿ ïîî÷åðåäíî âûïîëíåíèå ñëåäóþùèõ ðà-
âåíñòâ: õ9 = 0, õ10 = 0; õ9 = 0, õ10 = 1; õ9 = 1, õ10 = 0.
Ïåðâîå óðàâíåíèå ôîðìèðóåì íà îñíîâå (8), ïðèíèìàÿ âî âíèìàíèå,
÷òî õ9 = 0, õ10 = 0. Ïîëüçóÿñü ñòàíäàðòíûìè ôîðìóëàìè áóëåâîé àëãåáðû,
ïîëó÷àåì íîâîå ïðîãíîçèðîâàííîå óðàâíåíèå:
x x x x x x x x x x1 7 1 12 5 7 5 11 5 12 0� � � � . (11)
Ñ.Â. Ëèñòðîâîé, Ñ.Â. Ìîöíûé
12 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 6
Âòîðîå óðàâíåíèå ñîñòàâëÿåì íà îñíîâå âòîðîé ïàðû ïåðåìåííûõ: õ9 = 0,
õ10 = 1. Èç ðàâåíñòâà õ10 = 1 ñëåäóåò, ÷òî â (8) õ4 = 0, õ9 = 0, õ11= 0. Òîãäà
óðàâíåíèå ïðèìåò âèä
x x x x x x x x1 7 1 12 5 7 5 12 0� � � . (12)
Òðåòüå óðàâíåíèå (ïðè õ9 = 1, õ10 = 0) ïîëó÷àåì àíàëîãè÷íî: èç ðà-
âåíñòâà õ9 = 1 ñëåäóþò ðàâåíñòâà õ4 = 0, õ9 = 0, õ12 = 0, è óðàâíåíèå (8) ïðè-
íèìàåò âèä
x x x x x x1 7 5 7 5 11 0� � . (13)
Ñëàãàåìûå óðàâíåíèé (12) è (13) âõîäÿò â óðàâíåíèå (11), ïîýòîìó óðàâ-
íåíèÿ (12), (13) ìîãóò áûòü èñêëþ÷åíû èç äàëüíåéøåãî àíàëèçà.
Äàëåå, äëÿ óðàâíåíèÿ (11) ñ ÷àñòè÷íûì ðåøåíèåì õ3, õ8, õ2, õ6, õ9, õ10
îïðåäåëÿåì ÷àñòîòó ïîÿâëåíèÿ ïåðåìåííûõ è íà îñíîâàíèè ïîëó÷åííûõ
ðåçóëüòàòîâ ôîðìèðóåì ñëåäóþùóþ òàáëèöó:
X i 1 5 7 11 12
hi
x
2 3 2 1 2
Ïîñêîëüêó õ11 âñòðå÷àåòñÿ îäèí ðàç, ïåðåìåííóþ õ5 = 0 âêëþ÷àåì â ÷àñ-
òè÷íîå ðåøåíèå, â ðåçóëüòàòå ÷åãî óðàâíåíèå (11) ïðåîáðàçóåòñÿ ê âèäó
x x x x1 7 1 12 0� . (14)
Îïðåäåëÿåì ÷àñòîòû ïîÿâëåíèÿ ïåðåìåííûõ â óðàâíåíèè (14) ñ ÷àñò-
íûì ðåøåíèåì õ3, õ8, õ2, õ6, õ9, õ10, õ5 è çàíîñèì èõ â òàáëèöó:
X i 1 7 12
hi
x
2 1 1
Ïðè ýòîì ïîÿâèëîñü íåñêîëüêî âèñÿ÷èõ âåðøèí (èìåþùèõ ñòåïåíü 1), èç
êîòîðûõ ïðîèçâîëüíî âûáèðàåì ëþáóþ äëÿ îáðàáîòêè. Â ïîêðûòèå äîëæ-
íà áûòü äîáàâëåíà âåðøèíà, ñìåæíàÿ ñ âûáðàííîé. Ïîñêîëüêó õ7 õ12 âñòðå-
÷àåòñÿ îäèí ðàç, ïåðåìåííàÿ õ1 = 0 äîëæíà áûòü âêëþ÷åíà â ÷àñòè÷íîå ðå-
øåíèå. Òîãäà óðàâíåíèå (14) ïðèíèìàåò âèä 0 = 0, ò.å. ïîëó÷åíî òîæäåñòâî.
Òàêèì îáðàçîì, íàáîð ïåðåìåííûõ õ3, õ8, õ2, õ6, õ9, õ10, õ5, õ1 îïðåäåëÿåò
ìèíèìàëüíîå âåðøèííîå ïîêðûòèå çàäàííîãî ãðàôà. Ýòî æå ïîêðûòèå
ñîäåðæèòñÿ â ïåðâîé ñòðîêå ïåðâîé òàáëèöû. Ñëåäîâàòåëüíî, ðåøåíèå,
íàéäåííîå ñ ïîìîùüþ ïðåäëàãàåìîãî àëãîðèòìà, ÿâëÿåòñÿ òî÷íûì.
Ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé. Äëÿ ïðîâåäåíèÿ ýêñïå-
ðèìåíòàëüíûõ èññëåäîâàíèé è äàëüíåéøåãî ñðàâíèòåëüíîãî àíàëèçà ðàçðà-
Àëãîðèòì ðåøåíèÿ çàäà÷è î íàèìåíüøåì âåðøèííîì ïîêðûòèè ïðîèçâîëüíîãî ãðàôà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 6 13
áîòàíî ïðîãðàììíîå îáåñïå÷åíèå íà ÿçûêå ïðîãðàììèðîâàíèÿ C++, êîòîðîå
ïîçâîëÿåò ãåíåðèðîâàòü ãðàôû ñîãëàñíî ðàâíîìåðíîìó çàêîíó ðàñïðåäåëåíèÿ
ñ ó÷åòîì çàäàâàåìûõ õàðàêòåðèñòèê (ïëîòíîñòü è ÷èñëî âåðøèí).
Ïðåäëàãàåìûé ìåòîä ðåøåíèÿ çàäà÷è î íàèìåíüøåì ïîêðûòèè (ìåòîä
óðàâíåíèé) ñðàâíèì ñ ÷àñòîòíûì ìåòîäîì [11, 12], êîòîðûé èìååò âðåìåí-
íóþ ñëîæíîñòü O (mn2) (ãäå m — ÷èñëî ðåáåð ãðàôà, n — ÷èñëî âåðøèí) è
ÿâëÿåòñÿ îäíèì èç íàèáîëåå òî÷íûõ ìåòîäîâ ðåøåíèÿ äàííîé çàäà÷è. Íà
ðèñóíêàõ à, á ïðåäñòàâëåíû çàâèñèìîñòè ÷àñòîòû ïîÿâëåíèÿ íåòî÷íûõ ðå-
øåíèé àëãîðèòìîâ îò ÷èñëà âåðøèí è ïëîòíîñòè ãðàôà. Ïðè ïðîâåäåíèè
ýêñïåðèìåíòîâ ðàçìåðíîñòü ãðàôà ìåíÿëàñü îò 10 äî 35 âåðøèí, ïëîòíîñòü —
îò 10 äî 70 %.
Ðåçóëüòàòû ýêñïåðèìåíòàëüíîãî àíàëèçà ñâèäåòåëüñòâóþò î òîì, ÷òî
ïðåäëàãàåìûé ìåòîä óðàâíåíèé áîëåå ýôôåêòèâåí êàê íà íà÷àëüíûõ ñòàäèÿõ
òåñòèðîâàíèÿ, òàê è ïðè çíà÷èòåëüíîì óâåëè÷åíèè âåðøèííûõ õàðàêòåðèñòèê
ãðàôà, è ïîçâîëÿåò ïîëó÷àòü áîëåå òî÷íûå ðåøåíèÿ ïî ñðàâíåíèþ ñ ÷àñ-
òîòíûì ìåòîäîì. Òàê, ïðè èñïîëüçîâàíèè ÷àñòîòíîãî ìåòîäà ïîãðåøíîñòü
ðåøåíèÿ íå ïðåâûøàåò 4 %, à ïðè èñïîëüçîâàíèè ìåòîäà óðàâíåíèé ìàêñè-
ìàëüíîå çàôèêñèðîâàííîå çíà÷åíèå ñîñòàâèëî 1,74 %, ò.å. äàííûé ïîêàçà-
òåëü óäàëîñü óëó÷øèòü ïðàêòè÷åñêè â äâà ðàçà. Èç ðèñóíêîâ â è ã âèäíî,
÷òî ïðè óëó÷øåííûõ ïîêàçàòåëÿõ àïïðîêñèìàöèè ïðåäëàãàåìûé ìåòîä
óðàâíåíèé çíà÷èòåëüíî ìåíüøå çàâèñèò îò ñëîæíîñòè òîïîëîãèè âûáðàí-
íîãî ãðàôà.
Ñ.Â. Ëèñòðîâîé, Ñ.Â. Ìîöíûé
14 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 6
0
à
â
á
ã
0,2
0,4
0,6
10 15 20 25 30 35
×èñëî âåðøèí
×
è
ñë
î
î
ï
åð
àö
è
é
×
àñ
òî
òà
ï
î
ÿ
â
ë
åí
è
ÿ
î
ø
è
á
î
ê
0
0,1
0,2
0,3
0,4
10 30 50 70
0
10 000
20 000
30 000
40 000
10 15 20 25 30 35
0
5 000
10 000
15 000
20 000
25 000
30 000
10 30 50 70
Ïëîòíîñòü ãðàôà, %
Ãðàôèêè çàâèñèìîñòåé ÷àñòîòû ïîÿâëåíèÿ îøèáîê (à, á) è ÷èñëà îïåðàöèé (â, ã) îò ÷èñëà
âåðøèí (à, â) è ïëîòíîñòè ãðàôà (á, ã): �— ÷àñòîòíûé ìåòîä;�— ìåòîä óðàâíåíèé
Îáû÷íî ïðè óâåëè÷åíèè ïîêàçàòåëÿ òî÷íîñòè ïðèáëèæåííîãî àëãî-
ðèòìà ñóùåñòâåííî âîçðàñòàåò åãî âðåìåííàÿ ñëîæíîñòü. Êàê ïîêàçàëè ðå-
çóëüòàòû òåñòèðîâàíèÿ, âðåìåííàÿ ñëîæíîñòü àëãîðèòìà ñ èñïîëüçîâàíèåì
ñèñòåì êâàäðàòè÷íûõ óðàâíåíèé â ñðåäíåì íå ïðåâûøàåò âåëè÷èíû mn2. Ïðè
ýòîì åãî ýôôåêòèâíîñòü çíà÷èòåëüíî óëó÷øàåòñÿ ïðè èñïîëüçîâàíèè áîëü-
øîãî ÷èñëà âû÷èñëèòåëüíûõ ÿäåð. Âûñîêàÿ ñòåïåíü ðàñïàðàëëåëèâàíèÿ
èíñòðóêöèé äîñòèãàåòñÿ â ðåçóëüòàòå èñïîëüçîâàíèÿ âîçìîæíîñòè îäíî-
âðåìåííîãî ðåøåíèÿ êàæäîãî èç ïðîãíîçèðóåìûõ âàðèàíòîâ ñ îäíîé èç
òðåõ âåðîÿòíûõ ïàð ïåðåìåííûõ ïî õîäó âûïîëíåíèÿ àëãîðèòìà. Åñòåñò-
âåííî, ñóùåñòâóåò íåîáõîäèìîñòü â ñèíõðîíèçàöèè ïðîöåäóð, âîçâðàùàå-
ìûå ðåçóëüòàòû êîòîðûõ òðåáóåòñÿ ïîëó÷àòü â îïðåäåëåííûé ìîìåíò âðå-
ìåíè. Ïðè ðåàëèçàöèè äàííîãî àëãîðèòìà â ðàñïðåäåëåííîé ñðåäå âðåìÿ åãî
âûïîëíåíèÿ ñîêðàùàåòñÿ â 2,3 ðàçà ïî ñðàâíåíèþ ñ ÷àñòîòíûì ìåòîäîì.
Âûâîäû
 ðåçóëüòàòå ïðîâåäåíîãî ñðàâíèòåëüíîãî àíàëèçà óñòàíîâëåíî, ÷òî ïðåä-
ëîæåííûé ìåòîä ðåøåíèÿ çàäà÷è î íàèìåíüøåì ïîêðûòèè ïðîèçâîëüíîãî
ãðàôà ñ ïîìîùüþ ñèñòåì êâàäðàòè÷íûõ óðàâíåíèé áîëåå ýôôåêòèâåí ïî
ñðàâíåíèþ ñ ÷àñòîòíûì ìåòîäîì, êîòîðûé â íàñòîÿùåå âðåìÿ ÿâëÿåòñÿ îä-
íèì èç íàèáîëåå òî÷íûõ. Êàê ñâèäåòåëüñòâóþò ðåçóëüòàòû àíàëèçà, ïðè
ðåøåíèè çàäà÷ â ìàñøòàáàõ ðåàëüíîãî âðåìåíè ïðåäëàãàåìûé ìåòîä ïðå-
âîñõîäèò ñóùåñòâóþùèå êàê ïî ïîêàçàòåëÿì ïîãðåøíîñòè, òàê è ïî âðåìå-
íè âûïîëíåíèÿ. Ïðè ýòîì âîçìîæíîñòü ãèáêîãî ðàñïàðàëëåëèâàíèÿ âû-
ïîëíÿåìûõ ïðîöåäóð ïîçâîëÿåò íàèáîëåå îïòèìàëüíî èñïîëüçîâàòü ðåñóðñû
ñîâðåìåííûõ âû÷èñëèòåëüíûõ ñèñòåì. Ýôôåêòèâíîñòü àëãîðèòìà çíà÷è-
òåëüíî ïîâûøàåòñÿ ïðè èñïîëüçîâàíèè ðàñïðåäåëåííûõ ñèñòåì ñ áîëüøèì
êîëè÷åñòâîì âû÷èñëèòåëüíûõ ÿäåð.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Êðèñòîôèäåñ Í. Òåîðèÿ ãðàôîâ. Àëãîðèòìè÷åñêèé ïîäõîä. — Ì. : Ìèð, 1978. — 309 ñ.
2. Vijay V. Vazirani. Approximation Algorithms. 2nd Ed. — Berlin: Springer-Verlag, 2003. —
P. 306—334.
3. Zhang Y., Qi G., Fleisher R. et al. Approximating the minimum weight weak vertex cover //
Elsevier: Theoretical Computer Science. —1992. — Vol. 7, Iss. 4. — P. 404—416.
4. Roth-Korostensky C. Algorithms for building multiple sequence alignments and evolution-
ary trees// Doctoral thesis. — ETH Z��urich, Institute of Scientific Computing, Switzerland,
2000. — 161 p.
5. Stege U. Resolving conflicts in problems from computational biology// Doctoral thesis. —
ETH Z�rich, Institute of Scientific Computing, Switzerland, 2000. — 158 p.
6. Jianer C., Iyad K.A., Ge X. Improved Parameterized Upper Bounds for Vertex Cover//
Elsevier: Theoretical Computer Science. — 2010. — Vol. 411. — P. 3736—3756.
7. Jianer C., Iyad K.A., Ge X. Simplicity is beauty: Improved upper bounds for vertex cover//
Technical Report 05-008, Texas A&M University, Utrecht, Netherlands, April 2005.
Àëãîðèòì ðåøåíèÿ çàäà÷è î íàèìåíüøåì âåðøèííîì ïîêðûòèè ïðîèçâîëüíîãî ãðàôà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 6 15
8. Karakostas G. A better approximation ratio for the vertex cover problem// ACM Transac-
tions on Algorithms (TALG). — 2009. — Vol. 5, Iss. 4. — P. 1—8.
9. Cheng W., Yuren Z., Weiping T. Hybrid genetic algorithm for vertex cover problem// Com-
puter Engineering and Applications. — 2007. — Vol. 43, No. 14. — P. 27—29.
10. Miehalewiez Z., Fogel D.B. How to Solve It: Modern Heuristics. — Berlin, Heidelberg:
Springer-Verlag, 2004. — 554 p.
11. Ëèñòðîâîé Ñ.Â., Ìèíóõèí Ñ.Â. Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì âåðøèííîì
ïîêðûòèè â ïðîèçâîëüíîì ãðàôå è çàäà÷è î íàèìåíüøåì ïîêðûòèè// Ýëåêòðîí. ìîäå-
ëèðîâàíèå. — 2012. — 34, ¹ 1. — Ñ. 29—45.
12. Listrovoy S.V., Minukhin S.V. Investigation of the Scheduler for Heterogeneous Distributed
Computing Systems based on Minimal Cover Method// Intern. Journal of Computer Appli-
cations. — 2012. — Vol. 51, No.19. — P. 35—44.
S.V. Listrovoy, S.V. Motsnyi
THE MINIMUM VERTEX COVER PROBLEM
SOLVING ALGORITHM FOR AN ARBITRARY GRAPH
WITH USING THE SYSTEMS OF QUADRATIC EQUATIONS
This paper presents an algorithm for solving the minimum vertex cover problem for the arbitrary
graphs using systems of quadratic equations that provide high level of the operations paralleli-
zation. Approximation algorithms with different approximation coefficients can be used in prac-
tice to solve such problems. Experimental analysis shows the advantages of the described meth-
odology in comparison with existing implementations. The algorithm effectiveness can be signif-
icantly enhanced by the use of distributed systems with many cores.
K e y w o r d s : vertex cover, approximation coefficient, quadratic equations, frequency of terms
occurrences.
REFERENCES
1. Christofides, N. (1978), Teoriya grafov. Algoritmicheskiy podkhod [Graph Theory. An Al-
gorithmic Approach], Mir, Moscow, Russia.
2. Vijay Vazirani, V. (2003), Approximation Algorithms, 2nd ed., Springer-Verlag, Berlin,
Germany, pp. 306-334.
3. Zhang, Y. and et al. (1992), “Approximating the minimum weight weak vertex cover”,
Elsevier, Theoretical Computer Science, Vol. 7, no. 4, pp. 404-416.
4. Roth-Korostensky, C. (2000), “Algorithms for building multiple sequence alignments and
evolutionary trees”, PhD thesis, ETH Z�rich Institute of Scientific Computing, Z�rich,
Switzerland.
5. Stege, U. (2000), “Resolving conflicts in problems from computational biology”, PhD the-
sis, ETH Z�rich Institute of Scientific Computing, Z�rich, Switzerland.
6. Jianer, C., Iyad, K.A. and Ge, X. (2010), “Improved Parameterized Upper Bounds for Vertex
Cover”, Elsevier, Theoretical Computer Science, Vol. 411, Iss. 40-42, pp. 3736-3756.
7. Jianer, C., Iyad, K.A. and Ge, X. (2005), “Simplicity is beauty: Improved upper bounds for
vertex cover”, Technical Report 05-008, Texas A&M University, Utrecht, the Netherlands.
8. Karakostas, G. (2009), “A better approximation ratio for the vertex cover problem”, ACM
Transactions on Algorithms (TALG), Vol. 5, Iss. 4, pp. 1-8.
9. Cheng, W., Yuren, Z. and Weiping, T. (2007), “Hybrid genetic algorithm for vertex cover
problem”, Computer Engineering and Applications, Vol. 43, no. 14, pp. 27-29.
Ñ.Â. Ëèñòðîâîé, Ñ.Â. Ìîöíûé
16 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 6
10. Miehalewiez, Z. and Fogel, D.B. (2004), How to solve it: Modern heuristics, 2nd ed.,
Springer-Verlag, Heidelberg, Berlin, Germany.
11. Listrovoy, S.V. and Minukhin, S.V. (2012), “Method for solving the minimum vertex cover
problem in arbitrary graphs and the problem of minimal coverage”, Elektronnoe mode-
lirovanie, Vol. 34, no. 1, pp. 29-45.
12. Listrovoy, S.V. and Minukhin, S.V. (2012), “Investigation of the scheduler for heteroge-
neous distributed computing systems based on minimal cover method”, International Jour-
nal of Computer Applications, Vol. 51, no. 19, ðp. 35-44.
Ïîñòóïèëà 06.05.15;
ïîñëå äîðàáîòêè 05.10.15
ËÈÑÒÐÎÂÎÉ Ñåðãåé Âëàäèìèðîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû ñïåöèà-
ëèçèðîâàííûõ êîìïüþòåðíûõ ñèñòåì Óêðàèíñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà æåëåçíî-
äîðîæíîãî òðàíñïîðòà.  1972 ã. îêîí÷èë Õàðüêîâñêîå âûñøåå âîåííîå êîìàíäíî-èíæåíåðíîå
ó÷èëèùå. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — çàäà÷è äèñêðåòíîé îïòèìèçàöèè è òåîðèè ãðàôîâ
è èõ ïðèëîæåíèå ê àíàëèçó âû÷èñëèòåëüíûõ ñèñòåì è ñåòåé.
ÌÎÖÍÛÉ Ñòàíèñëàâ Âëàäèìèðîâè÷, àñïèðàíò êàôåäðû ñïåöèàëèçèðîâàííûõ êîìïüþòåðíûõ
ñèñòåì Óêðàèíñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà æåëåçíîäîðîæíîãî òðàíñïîðòà. Â 2012 ã.
îêîí÷èë Óêðàèíñêóþ ãîñóäàðñòâåííóþ àêàäåìèþ æåëåçíîäîðîæíîãî òðàíñïîðòà (ã. Õàðü-
êîâ). Îáëàñòü íàó÷íûõ èññëåäîâàíèé — èíôîðìàöèîííàÿ áåçîïàñíîñòü â òåëåêîììóíèêàöèîí-
íûõ ñèñòåìàõ è ñåòÿõ, îïòèìèçàöèÿ ïðîöåññîâ â ðàñïðåäåëåííûõ ñèñòåìàõ.
Àëãîðèòì ðåøåíèÿ çàäà÷è î íàèìåíüøåì âåðøèííîì ïîêðûòèè ïðîèçâîëüíîãî ãðàôà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 6 17
|