Поиск заданного количества решений системы размытых ограничений
Исследована минимаксная модификация задачи распознавания совместимости системы ограничений, когда для каждого решения определена не бинарная допустимость, а ее количественная характеристика. Описанный в статье алгоритм находит за полиномиальное время требуемое количество наилучших решений системы ра...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2018 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/144833 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Поиск заданного количества решений системы размытых ограничений / М.И. Шлезингер, Б. Флах, Е.В. Водолазский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 67–83. — Бібліогр.: 22 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-144833 |
|---|---|
| record_format |
dspace |
| spelling |
Шлезингер, М.И. Флах, Б. Водолазский, Е.В. 2019-01-05T15:26:01Z 2019-01-05T15:26:01Z 2018 Поиск заданного количества решений системы размытых ограничений / М.И. Шлезингер, Б. Флах, Е.В. Водолазский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 67–83. — Бібліогр.: 22 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/144833 519.157 Исследована минимаксная модификация задачи распознавания совместимости системы ограничений, когда для каждого решения определена не бинарная допустимость, а ее количественная характеристика. Описанный в статье алгоритм находит за полиномиальное время требуемое количество наилучших решений системы размытых ограничений, если эти ограничения инвариантны относительно некоторого мажоритарного оператора. Существенно, что для реализации алгоритма не требуется знания этого оператора, более того, не требуется гарантировать его существование. Для любой системы размытых ограничений алгоритм либо находит заданное количество наиболее допустимых решений, либо выдает отказ от решения задачи. Последнее возможно, только если для решаемой системы ограничений такой оператор отсутствует. Досліджено мінімаксну модифікацію задачі розпізнавання несуперечності системи обмежень, коли для кожного розв’язку визначено не бінарну допустимість, а її кількісну характеристику. Описаний в статті алгоритм знаходить за поліноміальний час задану кількість найкращих розв’язків системи розмитих обмежень, якщо ці обмеження інваріантні відносно деякого мажоритарного оператора. Важливо, що для реалізації алгоритму не потрібно знання цього оператора, більш того, не потрібно гарантувати його існування. Для довільної системи розмитих обмежень алгоритм або знаходить задану кількість найбільш допустимих розв’язків, або дає відмову від розв’язку задачи. Останнє можливо, тільки якщо для розв’язаної системи обмежень такого оператора не існує. A minimax modification of a fuzzy constraint satisfaction problem is considered, where constraints determine not whether a given solution is feasible but the numerical value of satisfiability. The algorithm is proposed that finds a given number of solutions with the highest value of satisfiability in polynomial time for a subclass of problems with constraints invariant to some majority operator. It is essential that knowing the operator itself is not required. Moreover, it is not necessary to guarantee its existence. For any system of fuzzy constraints, the algorithm either finds a given number of best solutions or declines the problem. The latter is only possible when no such operator exists. Работа выполнена в рамках проекта № 7/2/267-39/17 «Создание интеллектуальных технологий на основе методов и средств образного мышления» (Отделение информатики НАН Украины) и при поддержке гранта № 16-05872S «Probabilistic graphical models and deep learning» (Грантовая агентура Чешской Республики). ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Поиск заданного количества решений системы размытых ограничений Пошук заданої кількості розв’язків системи розмитих обмежень Finding a given number of solutions to a system of fuzzy constraints 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 |
2018 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Пошук заданої кількості розв’язків системи розмитих обмежень Finding a given number of solutions to a system of fuzzy constraints |
| description |
Исследована минимаксная модификация задачи распознавания совместимости системы ограничений, когда для каждого решения определена не бинарная допустимость, а ее количественная характеристика. Описанный в статье алгоритм находит за полиномиальное время требуемое количество наилучших решений системы размытых ограничений, если эти ограничения инвариантны относительно некоторого мажоритарного оператора. Существенно, что для реализации алгоритма не требуется знания этого оператора, более того, не требуется гарантировать его существование. Для любой системы размытых ограничений алгоритм либо находит заданное количество наиболее допустимых решений, либо выдает отказ от решения задачи. Последнее возможно, только если для решаемой системы ограничений такой оператор отсутствует.
Досліджено мінімаксну модифікацію задачі розпізнавання несуперечності системи обмежень, коли для кожного розв’язку визначено не бінарну допустимість, а її кількісну характеристику. Описаний в статті алгоритм знаходить за поліноміальний час задану кількість найкращих розв’язків системи розмитих обмежень, якщо ці обмеження інваріантні відносно деякого мажоритарного оператора. Важливо, що для реалізації алгоритму не потрібно знання цього оператора, більш того, не потрібно гарантувати його існування. Для довільної системи розмитих обмежень алгоритм або знаходить задану кількість найбільш допустимих розв’язків, або дає відмову від розв’язку задачи. Останнє можливо, тільки якщо для розв’язаної системи обмежень такого оператора не існує.
A minimax modification of a fuzzy constraint satisfaction problem is considered, where constraints determine not whether a given solution is feasible but the numerical value of satisfiability. The algorithm is proposed that finds a given number of solutions with the highest value of satisfiability in polynomial time for a subclass of problems with constraints invariant to some majority operator. It is essential that knowing the operator itself is not required. Moreover, it is not necessary to guarantee its existence. For any system of fuzzy constraints, the algorithm either finds a given number of best solutions or declines the problem. The latter is only possible when no such operator exists.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/144833 |
| citation_txt |
Поиск заданного количества решений системы размытых ограничений / М.И. Шлезингер, Б. Флах, Е.В. Водолазский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 67–83. — Бібліогр.: 22 назв. — рос. |
| work_keys_str_mv |
AT šlezingermi poiskzadannogokoličestvarešeniisistemyrazmytyhograničenii AT flahb poiskzadannogokoličestvarešeniisistemyrazmytyhograničenii AT vodolazskiiev poiskzadannogokoličestvarešeniisistemyrazmytyhograničenii AT šlezingermi pošukzadanoíkílʹkostírozvâzkívsistemirozmitihobmeženʹ AT flahb pošukzadanoíkílʹkostírozvâzkívsistemirozmitihobmeženʹ AT vodolazskiiev pošukzadanoíkílʹkostírozvâzkívsistemirozmitihobmeženʹ AT šlezingermi findingagivennumberofsolutionstoasystemoffuzzyconstraints AT flahb findingagivennumberofsolutionstoasystemoffuzzyconstraints AT vodolazskiiev findingagivennumberofsolutionstoasystemoffuzzyconstraints |
| first_indexed |
2025-11-24T16:08:15Z |
| last_indexed |
2025-11-24T16:08:15Z |
| _version_ |
1850850828312641536 |
| fulltext |
ÓÄÊ 519.157
Ì.È. ØËÅÇÈÍÃÅÐ, Á. ÔËÀÕ, Å.Â. ÂÎÄÎËÀÇÑÊÈÉ
ÏÎÈÑÊ ÇÀÄÀÍÍÎÃÎ ÊÎËÈ×ÅÑÒÂÀ ÐÅØÅÍÈÉ ÑÈÑÒÅÌÛ
ÐÀÇÌÛÒÛÕ ÎÃÐÀÍÈ×ÅÍÈÉ1
Àííîòàöèÿ. Èññëåäîâàíà ìèíèìàêñíàÿ ìîäèôèêàöèÿ çàäà÷è ðàñïîçíàâàíèÿ
ñîâìåñòèìîñòè ñèñòåìû îãðàíè÷åíèé, êîãäà äëÿ êàæäîãî ðåøåíèÿ îïðåäåëå-
íà íå áèíàðíàÿ äîïóñòèìîñòü, à åå êîëè÷åñòâåííàÿ õàðàêòåðèñòèêà. Îïèñàí-
íûé â ñòàòüå àëãîðèòì íàõîäèò çà ïîëèíîìèàëüíîå âðåìÿ òðåáóåìîå êîëè-
÷åñòâî íàèëó÷øèõ ðåøåíèé ñèñòåìû ðàçìûòûõ îãðàíè÷åíèé, åñëè ýòè îãðà-
íè÷åíèÿ èíâàðèàíòíû îòíîñèòåëüíî íåêîòîðîãî ìàæîðèòàðíîãî îïåðàòîðà.
Ñóùåñòâåííî, ÷òî äëÿ ðåàëèçàöèè àëãîðèòìà íå òðåáóåòñÿ çíàíèÿ ýòîãî îïå-
ðàòîðà, áîëåå òîãî, íå òðåáóåòñÿ ãàðàíòèðîâàòü åãî ñóùåñòâîâàíèå. Äëÿ ëþ-
áîé ñèñòåìû ðàçìûòûõ îãðàíè÷åíèé àëãîðèòì ëèáî íàõîäèò çàäàííîå êîëè-
÷åñòâî íàèáîëåå äîïóñòèìûõ ðåøåíèé, ëèáî âûäàåò îòêàç îò ðåøåíèÿ çàäà-
÷è. Ïîñëåäíåå âîçìîæíî, òîëüêî åñëè äëÿ ðåøàåìîé ñèñòåìû îãðàíè÷åíèé
òàêîé îïåðàòîð îòñóòñòâóåò.
Êëþ÷åâûå ñëîâà: äèñêðåòíàÿ îïòèìèçàöèÿ, ìèíèìàêñíûå çàäà÷è, ðàçìåòêè,
èíâàðèàíòû, ïîëèìîðôèçìû.
ÂÂÅÄÅÍÈÅ
Èññëåäóåìàÿ çàäà÷à îòíîñèòñÿ ê ïðîáëåìå äèñêðåòíîé îïòèìèçàöèè ôóíêöèé
è ðàñïîçíàâàíèÿ ñîâìåñòèìîñòè îãðàíè÷åíèé [1].  òåðìèíàõ äèñêðåòíîé îïòè-
ìèçàöèè ýòà çàäà÷à èìååò ñëåäóþùèé ôîðìàò. Ïóñòü K — êîíå÷íûé àëôàâèò
ñèìâîëîâ, W — óïîðÿäî÷åííîå ìíîæåñòâî, x x x x Kn
n� �( , , , )1 2 � — ïîñëåäî-
âàòåëüíîñòü ñèìâîëîâ äëèíû n� 0, �: K Wn � — ôóíêöèÿ n ïåðåìåííûõ. Äëÿ
çàäàííîãî öåëîãî ÷èñëà 0� �d K n| | çàäà÷à d-îïòèìèçàöèè ôóíêöèè � ñîñòîèò
â îòûñêàíèè ïîäìíîæåñòâà Sol K n� , | |Sol d� , òàêîãî ÷òî � �( ) ( )x y� äëÿ ëþ-
áûõ x Sol� , y Sol . Îïòèìèçàöèÿ ôóíêöèè â îáû÷íîì ñìûñëå ýòîãî ñëîâà ÿâ-
ëÿåòñÿ 1-îïòèìèçàöèåé.
Àíàëîãè÷íî d-îïòèìèçàöèè ìîæíî îïðåäåëèòü d-ñîâìåñòèìîñòü ñèñòåìû
îãðàíè÷åíèé êàê åñòåñòâåííîå îáîáùåíèå êëàññè÷åñêîé ïðîáëåìû ðàñïîçíàâà-
íèÿ ñîâìåñòèìîñòè [1]. Ïóñòü R Kj
n� , j m�1 2, , ,� , — ñèñòåìà îãðàíè÷åíèé íà
n-êè ñèìâîëîâ èç K. Ðàñïîçíàâàíèå d-ñîâìåñòèìîñòè ñîñòîèò â îòâåòå íà âîïðîñ,
ñóùåñòâóþò ëè òàêèå ïîïàðíî ðàçëè÷íûå n-êè x Ki
n� , i d�1 2, , ,� , ÷òî x Ri j�
äëÿ âñåõ i è j. Êëàññè÷åñêàÿ çàäà÷à ñîâìåñòèìîñòè îãðàíè÷åíèé, ò.å. ïðîâåðêà íå-
ðàâåíñòâà
j
n
jR
�
�
1
� , ÿâëÿåòñÿ çàäà÷åé 1-ñîâìåñòèìîñòè. Î÷åâèäíî, ðàñïîçíàâà-
íèå d-cîâìåñòèìîñòè ñâîäèòñÿ ê d-îïòèìèçàöèè ôóíêöèè �: ,K n � { }0 1 , ïðèíè-
ìàþùåé çíà÷åíèå �( )x � 0 ïðè x R j
j
n
�
�1
� è çíà÷åíèå �( )x �1â ïðîòèâíîì ñëó÷àå.
Ðàçìûòîå îãðàíè÷åíèå ïîíèìàåòñÿ êàê ôóíêöèÿ �: [ , ]K n � 0 1 , çíà÷åíèå
�( )x êîòîðîé óêàçûâàåò ñòåïåíü äîïóñòèìîñòè ðåøåíèÿ x îòíîñèòåëüíî îãðàíè-
÷åíèÿ �, à ñòåïåíü äîïóñòèìîñòè ðåøåíèÿ x â ñèñòåìå � j
nK: [ , ]� 0 1 ,
j m�1 2, , ,� , ðàçìûòûõ îãðàíè÷åíèé ïîíèìàåòñÿ êàê ÷èñëî min ( )
j
j x� [2, 3].
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 67
1
Ðàáîòà âûïîëíåíà â ðàìêàõ ïðîåêòà ¹ 7/2/267-39/17 «Ñîçäàíèå èíòåëëåêòóàëüíûõ òåõíîëîãèé íà
îñíîâå ìåòîäîâ è ñðåäñòâ îáðàçíîãî ìûøëåíèÿ» (Îòäåëåíèå èíôîðìàòèêè ÍÀÍ Óêðàèíû) è ïðè
ïîääåðæêå ãðàíòà ¹ 16-05872S «Probabilistic graphical models and deep learning» (Ãðàíòîâàÿ
àãåíòóðà ×åøñêîé Ðåñïóáëèêè).
© Ì.È. Øëåçèíãåð, Á. Ôëàõ, Å.Â. Âîäîëàçñêèé, 2018
Ðàñïîçíàâàíèå d-ñîâìåñòèìîñòè ñèñòåìû ðàçìûòûõ îãðàíè÷åíèé ïîíèìàåòñÿ
êàê îòûñêàíèå d íàèáîëåå äîïóñòèìûõ ðåøåíèé.
Íåîáõîäèìîñòü d-îïòèìèçàöèè, d �1, âîçíèêàåò â ïîâñåäíåâíûõ ðåàëüíûõ ñè-
òóàöèÿõ. Ýòî ïðîèñõîäèò, íàïðèìåð, êîãäà èñêîìûé îïòèìóì äîëæåí óäîâëåòâî-
ðÿòü àïðèîðè èçâåñòíîìó îãðàíè÷åíèþ, à îïòèìèçàöèÿ � ñ ó÷åòîì ýòîãî îãðàíè÷å-
íèÿ ñîïðÿæåíà ñ ñåðüåçíûìè âû÷èñëèòåëüíûìè òðóäíîñòÿìè. Èíàÿ ñèòóàöèÿ âîç-
íèêàåò, êîãäà èñêîìîå ðåøåíèå x� ïðåäíàçíà÷åíî äëÿ ïîñëåäóþùåé îáðàáîòêè
ñ ïîìîùüþ àëãîðèòìà ñ îãðàíè÷åííîé îáëàñòüþ îïðåäåëåíèÿ.  ýòîì ñëó÷àå òðóä-
íî àïðèîðè ôîðìàëèçîâàòü îãðàíè÷åíèå íà ðåøåíèå, à ìîæíî ëèøü àïîñòåðèîðè
êîíñòàòèðîâàòü, ÷òî òåêóùåå ïîëó÷åííîå ðåøåíèå x� íåïðèãîäíî, è çàïðîñèòü ðå-
øåíèå, îòëè÷àþùååñÿ îò x� , íî ñ êàê ìîæíî ìåíüøèì çíà÷åíèåì ôóíêöèè �. Íà-
êîíåö, ôîðìàëèçîâàòü îãðàíè÷åíèå íà ðåøåíèå â ïðèíöèïå íåâîçìîæíî, êîãäà îíî
àäðåñóåòñÿ ÷åëîâåêó, êîòîðûé ìîæåò îòâåðãíóòü ïðåäëîæåííîå ðåøåíèå x� â ñèëó
òîëüêî åìó èçâåñòíûõ ïðè÷èí. Âî âñåõ ýòèõ ñèòóàöèÿõ öåëåñîîáðàçíà d-îïòèìèçà-
öèÿ ñ ïîñëåäîâàòåëüíî âîçðàñòàþùèì d è îòûñêàíèå ïîñëåäîâàòåëüíîñòè óõóäøà-
þùèõñÿ ðåøåíèé, ïîêà íå áóäåò íàéäåíî îïòèìàëüíîå ðåøåíèå, óäîâëåòâîðÿþùåå
îáúåêòèâíûì, íî çàðàíåå íå èçâåñòíûì îãðàíè÷åíèÿì.
Îñíîâîïîëàãàþùàÿ èäåÿ d-îïòèìèçàöèè è ðàñïîçíàâàíèÿ d-ñîâìåñòèìîñòè
ïðèíàäëåæèò Ëîóëåðó (Eugene U. Lawler) [4] è ñîñòîèò â ñëåäóþùåì. Ôóíêöèþ
� : K Wl
�1 íàçîâåì ñå÷åíèåì ôóíêöèè � : K Wl � , åñëè ñóùåñòâóþò òàêèå
1� �i l è a K� , ÷òî �( , ,x xi1 1�
, x x x x a x xi n i i n�
��1 1 1 1, , ) ( , , , , , , )� � �� .
Äëÿ ôóíêöèè � : K Wn � îáîçíà÷èì �( )� ìèíèìàëüíîå ìíîæåñòâî ôóíêöèé, ñî-
äåðæàùåå � è âñå âîçìîæíûå ñå÷åíèÿ êàæäîé ôóíêöèè � ���( ). Åñëè äëÿ ôóíê-
öèè � ñóùåñòâóåò àëãîðèòì 1-îïòèìèçàöèè ëþáîé ïîäàííîé íà åãî âõîä ôóíê-
öèè � ���( ), òî îí íàçûâàåòñÿ êîíñåðâàòèâíûì àëãîðèòìîì îïòèìèçàöèè �.
Ëîóëåð ïîêàçàë, ÷òî d-îïòèìèçàöèÿ ôóíêöèè � ñâîäèòñÿ ê ( | | )d n K� � -êðàòíîìó
âûçîâó êîíñåðâàòèâíîãî àëãîðèòìà è 1-îïòèìèçàöèè îïðåäåëåííîé ñîâîêóïíîñ-
òè ôóíêöèé � ���( ), êîëè÷åñòâî êîòîðûõ ðàâíî d n K� � | | .
Íàðÿäó ñ îáùèì ìåòîäîì Ëîóëåðà, ïðèìåíèìîãî äëÿ d-îïòèìèçàöèè øèðî-
êîãî êëàññà ôóíêöèé, èçâåñòåí ðÿä ÷àñòíûõ, íî áîëåå áûñòðîäåéñòâóþùèõ àëãî-
ðèòìîâ d-îïòèìèçàöèè òåõ èëè èíûõ ïîäêëàññîâ ôóíêöèé [5–9]. Áóäåì ãîâîðèòü,
÷òî ïîäêëàññ ôóíêöèé äîïóñêàåò óñêîðåííóþ d-îïòèìèçàöèþ, åñëè âû÷èñëè-
òåëüíàÿ ñëîæíîñòü d-îïòèìèçàöèè íà ýòîì ïîäêëàññå íà ïîðÿäîê ìåíüøå ñëîæ-
íîñòè àëãîðèòìà Ëîóëåðà. Èçâåñòíûå ïîäêëàññû óñêîðåííî ðåøàåìûõ çàäà÷ ôîð-
ìóëèðóþòñÿ â òåðìèíàõ ðàñïîçíàâàíèÿ ñîâìåñòèìîñòè îãðàíè÷åíèé. Îñíîâíûå
èäåè ðåøåíèÿ ýòèõ ïîäêëàññîâ çàäà÷ îïèñàíû â ðàçä. 2. Òàì æå óêàçàíî ìåñòî
ïðåäëàãàåìîãî ìåòîäà ñðåäè èçâåñòíûõ.
 ðàçä. 3–6 ðàññìîòðåí óñêîðåííûé àëãîðèòì d-îïòèìèçàöèè ôóíêöèé, èí-
âàðèàíòíûõ îòíîñèòåëüíî ìàæîðèòàðíûõ îïåðàòîðîâ (èíâàðèàíòíîñòü ôóíêöèè
îòíîñèòåëüíî îïåðàòîðà îïðåäåëåíà â ðàçä. 2). Â ðàáîòå [10] îïèñàí êîíñåðâàòèâ-
íûé àëãîðèòì 1-îïòèìèçàöèè òàêèõ ôóíêöèé. Ñëåäîâàòåëüíî, ê ýòèì ôóíêöèÿì
ïðèìåíèìà d-îïòèìèçàöèÿ ïî ìåòîäó Ëîóëåðà, êîòîðàÿ âûïîëíÿåòñÿ çà âðåìÿ
O C n K d K n( ( , | | ) | | )� � � , ãäå C n K( , | | ) — âðåìÿ îäíîêðàòíîãî âûïîëíåíèÿ èìå-
þùåãîñÿ êîíñåðâàòèâíîãî àëãîðèòìà. Ïðåäëàãàåìûé àëãîðèòì âûïîëíÿåò
d-îïòèìèçàöèþ çà âðåìÿ O C n K d K n( ( , | | ) | | )� � � 2 .
1. ÔÎÐÌÓËÈÐÎÂÊÀ ÎÑÍÎÂÍÛÕ ÏÎÍßÒÈÉ
Îïðåäåëåíèå 1. Äëÿ êîíå÷íîãî ìíîæåñòâà I , óïîðÿäî÷åííîãî ìíîæåñòâà W,
ôóíêöèè �: I W� è öåëîãî ÷èñëà d , 0� �d I| |, âûðàæåíèå
I id
i I
�
�
� arg min ( )[ ] � îáîçíà÷àåò, ÷òî
I I� � , | |I d� � è � �( ) ( )i j� äëÿ ëþáûõ i I� � , j I � ; (1)
äëÿ d I� | | âûðàæåíèå I id
i I
*
[ ]min ( )�
�
arg � îáîçíà÷àåò, ÷òî I I� � . �
68 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
Ïîäîáíî îáîçíà÷åíèþ arg min ( ),
i I
i
�
� êîòîðîå íå îáÿçàòåëüíî îïðåäåëÿåò
åäèíñòâåííûé ýëåìåíò i I� � , îáîçíà÷åíèå arg min ( )[ ]d
i I
i
�
� íå îïðåäåëÿåò îäíîçíà÷-
íî åäèíñòâåííîå ïîäìíîæåñòâî I I� � . Âûðàæåíèå I id
i I
�
�
� arg min ( )[ ] � ñëåäóåò ïî-
íèìàòü êàê êðàòêóþ çàïèñü óòâåðæäåíèÿ, ÷òî ïîäìíîæåñòâî I � óäîâëåòâîðÿåò óñëî-
âèÿì (1), âîçìîæíî, íàðÿäó ñ êàêèìè-òî äðóãèìè ïîäìíîæåñòâàìè. Ïîäìíîæåñòâà
âèäà arg min[ ]d
i I�
èìåþò ñëåäóþùèå ñâîéñòâà.
Ëåììà 1. Ïóñòü I — êîíå÷íîå ìíîæåñòâî, � : I W� — ôóíêöèÿ,
I id
i I
�
�
� arg min ( )[ ] � . Òîãäà
max ( ) max ( )
i I i I
i i
� �
�
�'
� � äëÿ ëþáîãî I I I d' '� �, | | . (2)
Ïóñòü I I0 � , I i
d
i I
0
0
�
�
� arg min ( )
[ ]
� è � �( ) max ( )i j
j I
�
� �
0
äëÿ ëþáîãî i I �
0 . Òîãäà
I id
i I
0
�
�
� arg min ( )[ ] � . � (3)
Ñâîéñòâà, óêàçàííûå â ëåììå 1, ñëåäóþò íåïîñðåäñòâåííî èç îïðåäåëåíèÿ 1.
Áóäåì ñ÷èòàòü, ÷òî óïîðÿäî÷åííîå ìíîæåñòâî W ñîäåðæèò ýëåìåíò � òàêîé,
÷òî � � a äëÿ ëþáîãî a W� .
Îïðåäåëåíèå 2. Äëÿ öåëîãî ÷èñëà d , 0� �d I| | , âûðàæåíèå min ( )[ ]d
i I
i
�
� îá-
îçíà÷àåò ñîâîêóïíîñòü çíà÷åíèé �( )i , i id
i I
�
�
arg min ( )[ ] � , ïðåäñòàâëåííóþ ìîíî-
òîííî íåóáûâàþùåé ïîñëåäîâàòåëüíîñòüþ; äëÿ d I� | | âûðàæåíèå min ( )
[ ]d
i I
i
�
� îá-
îçíà÷àåò ïîñëåäîâàòåëüíîñòü äëèíû d , êîòîðàÿ íà÷èíàåòñÿ ïîñëåäîâàòåëüíîñòüþ
çíà÷åíèé �( ),i i I� , óïîðÿäî÷åííîé â íåóáûâàþùåì ïîðÿäêå, è çàêàí÷èâàåòñÿ
d I
| | ýëåìåíòàìè, ðàâíûìè � . �
 îòëè÷èå îò arg min ( )
[ ]d
i I
i
�
� ïîñëåäîâàòåëüíîñòü min ( )[ ]d
i I
i
�
� îïðåäåëåíà îä-
íîçíà÷íî äëÿ ëþáîé ôóíêöèè � : I W� .
 äàííîé ðàáîòå, êàê è â ðÿäå ðàáîò, óïîìÿíóòûõ âî ââåäåíèè, âîïðîñû
óñêîðåííîé d-îïòèìèçàöèè èññëåäîâàíû â ðàìêàõ ñëåäóþùåé îáùåé çàäà÷è ðàç-
ìåòêè [1]. Ïóñòü T è K — äâà êîíå÷íûõ ìíîæåñòâà, ýëåìåíòû êîòîðûõ íàçîâåì
îáúåêòàìè è ìåòêàìè. Ñòðóêòóðîé ìíîæåñòâà T íàçîâåì íåêîòîðîå ïîäìíîæåñ-
òâî � � 2T . Äëÿ ëþáîãî ïîäìíîæåñòâà S T� îáîçíà÷èì K S ìíîæåñòâî âñåõ âîç-
ìîæíûõ îòîáðàæåíèé âèäà S K� . Ïóñòü x T K: � — îòîáðàæåíèå, íàçûâàåìîå
ðàçìåòêîé. Îáîçíà÷èì xi çíà÷åíèå ðàçìåòêè x T K: � äëÿ îáúåêòà i T� , à xS —
åå ñóæåíèå íà ïîäìíîæåñòâî S T� .  ñëó÷àå, êîãäà íåîáõîäèìî îáðàòèòü âíèìà-
íèå íà òî, ÷òî S P R� � , P R� ��, ñóæåíèå x íà S áóäåì îáîçíà÷àòü íå â âèäå
xP R� , à â âèäå ïàðû ( , )x xP R .
Ïóñòü ( , , )W � � — êîììóòàòèâíîå ïîëóêîëüöî, è äëÿ êàæäîãî S �� îïðåäå-
ëåíà ôóíêöèÿ �S
SK W: � , ïðåäñòàâëåííàÿ òàáëèöåé Tab {( ) ( , ( )) |S x xS S S� �
x K S� }. Ïîñêîëüêó îïåðàöèè � è � êîììóòàòèâíû è àññîöèàòèâíû, äàëåå èñ-
ïîëüçóþòñÿ âûðàæåíèÿ�
�i I
ia è�
�i I
ia äëÿ «ñóììû» êîíå÷íîãî êîëè÷åñòâà ñëàãàå-
ìûõ è «ïðîèçâåäåíèÿ» êîíå÷íîãî êîëè÷åñòâà ñîìíîæèòåëåé.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 69
Îïðåäåëåíèå 3. Èñõîäíûå äàííûå ( , )� � -çàäà÷è ðàçìåòêè — ýòî ïÿòåðêà
�� � � � � �T K W SS, , ( , , ), , ( | )� �� , (4)
à åå ðåøåíèå — çíà÷åíèå
w x W
x K S
S S
T
�
� �
� �� �
�
� ( ) (5)
è ðàçìåòêà x K T� � , òàêàÿ ÷òî
� � �
�
�
� �
�� �
S
S S
x K S
S Sx x w
T� �
� �( ) ( ) , (6)
åñëè îíà ñóùåñòâóåò. �
×èñëî Ord ( ) max | |� �
�S
S
�
íàçîâåì ïîðÿäêîì ñòðóêòóðû � , ïîðÿäêîì çàäà÷è
� è ïîðÿäêîì ôóíêöèè �
�S
S Sx
�
� ( ). ×èñëî Vol Tab( ) | ( ) |� �
�
�
S
S
�
íàçîâåì îáúå-
ìîì èñõîäíûõ äàííûõ çàäà÷è. Êëàññè÷åñêàÿ çàäà÷à ðàñïîçíàâàíèÿ ñîâìåñòèìîñ-
òè îãðàíè÷åíèé [11] åñòü çàäà÷à (4)–(6), ñôîðìóëèðîâàííàÿ äëÿ ïîëóêîëüöà
� � ��{ }0 1, , , . Çàäà÷à ðàñïîçíàâàíèÿ ñîâìåñòèìîñòè ðàçìûòûõ îãðàíè÷åíèé [2, 3]
åñòü çàäà÷à (4)–(6), ñôîðìóëèðîâàííàÿ íà ïîëóêîëüöå � �W, min, max , ãäå W — íå-
êîòîðîå óïîðÿäî÷åííîå ìíîæåñòâî. Îïòèìèçàöèîííàÿ çàäà÷à ðàçìåòêè [12] —
ýòî çàäà÷à (4)–(6), ñôîðìóëèðîâàííàÿ íà ïîëóêîëüöå � ��W, min, , ãäå � — ëþáàÿ
îïåðàöèÿ, îáðàçóþùàÿ ñ îïåðàöèåé min ïîëóêîëüöî íà ìíîæåñòâå W.
Ïóñòü äëÿ êàæäîãî i T� îïðåäåëåí òðåõìåñòíûé îïåðàòîð p K K K Ki : � � � .
Ñîâîêóïíîñòü P p i Ti� �( | ) ýòèõ îïåðàòîðîâ áóäåì ïîíèìàòü êàê îïåðàòîð
K K K KS S S S� � � , îïðåäåëåííûé äëÿ êàæäîãî S T� . Â ðåçóëüòàòå ïðèìåíå-
íèÿ åãî ê òðîéêå ðàçìåòîê x y z K S, , � ïîëó÷àåòñÿ ðàçìåòêà P x y z K S( , , ) � �� ,
òàêàÿ ÷òî � i i i i ip x y z� ( , , ), i S� .
Îïðåäåëåíèå 4. Îïåðàòîð P p i Ti� �( | ) íàçîâåì ïîëèìîðôèçìîì ôóíêöèè
�S
SK W: � íà ïîëóêîëüöå ( , , )W min max , à ôóíêöèþ �S — èíâàðèàíòîì îïå-
ðàòîðà P, åñëè äëÿ ëþáîé òðîéêè ðàçìåòîê x y z K S, , � âûïîëíÿåòñÿ íåðàâåíñòâî
max ( ), ( ), ( ) ( ( , , )){ }� � � �S S S Sx y z P x y z� ; (7)
îïåðàòîð P íàçîâåì ïîëèìîðôèçìîì ( , )min max -çàäà÷è (4)–(6), à çàäà÷ó — èí-
âàðèàíòíîé îòíîñèòåëüíî P, åñëè êàæäàÿ ôóíêöèÿ �S
SK W: � , S �� , èíâà-
ðèàíòíà îòíîñèòåëüíî P. �
Îïðåäåëåíèå 4 ÿâëÿåòñÿ åñòåñòâåííûì ðàñøèðåíèåì íà ïîëóêîëüöî ( max)min,
èçâåñòíûõ ïîíÿòèé ïîëèìîðôèçìîâ è èíâàðèàíòîâ, îïðåäåëåííûõ íà ïîëóêîëüöå
( , , , ){ }0 1 � � [11], ãäå óñëîâèþ (7) ñîîòâåòñòâóåò óñëîâèå � � �S S Sx y z( ) ( ) ( )� � �
� �S P x y z( ( , , )). Îïðåäåëåíèå 4 îáîáùàåò êëàññè÷åñêèå ïîíÿòèÿ ïîëèìîðôèç-
ìîâ è èíâàðèàíòîâ åùå è â äðóãîì íàïðàâëåíèè. Â òåîðèè ( , )� � -çàäà÷ ïîëàãàþò,
÷òî îïåðàòîð P p i Ti� �( | ) îäíîðîäåí íà ìíîæåñòâå T â òîì ñìûñëå, ÷òî åãî êîì-
ïîíåíòû pi íå çàâèñÿò îò i T� . Â ñîîòâåòñòâèè ñ îïðåäåëåíèåì 4 îïåðàòîð
P p i Ti� �( | ) ìîæåò áûòü íåîäíîðîäíûì â òîì ñìûñëå, ÷òî êàæäîìó i T� ñîîò-
âåòñòâóåò ñâîé îïåðàòîð pi .
Èçâåñòíî [13], ÷òî ìíîæåñòâî ôóíêöèé, èìåþùèõ îáùèé ïîëèìîðôèçì íà ïî-
ëóêîëüöå ( , , , ){ }0 1 � � , çàìêíóòî ïî îïðåäåëåííûì îïåðàöèÿì íàä ýòèìè ôóíêöèÿìè.
Ñëåäóþùèå äâå ëåììû âûðàæàþò ýòè ñâîéñòâà íà ïîëóêîëüöå ( , , )W min max .
Îïðåäåëåíèå 5. Ïðîåêöèÿ ôóíêöèè � : K WT � íà ïîäìíîæåñòâî S T� —
ýòî ôóíêöèÿ �S
SK W: � , ïðèíèìàþùàÿ çíà÷åíèÿ � �S S
x K
S Rx x x
R
R
( ) min ( , )�
�
,
ãäå R T S� \ . �
70 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
Ëåììà 2. Åñëè ôóíêöèÿ �: K WT � èíâàðèàíòíà íà ïîëóêîëüöå
( , , )W min max îòíîñèòåëüíî îïåðàòîðà P, òî åå ïðîåêöèÿ �S íà ëþáîå ïîäìíî-
æåñòâî S T� èíâàðèàíòíà îòíîñèòåëüíî ýòîãî æå îïåðàòîðà. �
Ëåììà 3. Åñëè ôóíêöèè � : K WT � è � : K WT � èíâàðèàíòíû íà ïîëó-
êîëüöå ( , , )W min max îòíîñèòåëüíî îïåðàòîðà P, òî ôóíêöèÿ � : K WT � ñî çíà-
÷åíèÿìè � � �( ) max ( ), ( )x x x� { }, x K T� , èíâàðèàíòíà îòíîñèòåëüíî ýòîãî æå
îïåðàòîðà. �
Äîêàçàòåëüñòâà îáåèõ ëåìì ïðèâåäåíû â [10]. Îíè ÿâëÿþòñÿ åñòåñòâåííûì
îáîáùåíèåì ëåìì, äîêàçàííûõ äëÿ ïîëóêîëüöà ( , , , ){ }0 1 � � [13].
Îïðåäåëåíèå 6. Îïåðàòîð P p i Ti� �( | ) íàçûâàåòñÿ ìàæîðèòàðíûì, åñëè äëÿ
ëþáîãî i T� è ëþáûõ x y K, � âûïîëíÿþòñÿ ðàâåíñòâà p y x x p x y xi i( , , ) ( , , )� �
� �p x x y xi ( , , ) . �
Ôóíêöèè, èíâàðèàíòíûå íà ïîëóêîëüöå ( , )min max îòíîñèòåëüíî ìàæîðèòàð-
íûõ îïåðàòîðîâ, èìåþò äîïîëíèòåëüíîå âàæíîå ñâîéñòâî. Äëÿ ôóíêöèé ñ ìàæîðè-
òàðíûì ïîëèìîðôèçìîì â ïîëóêîëüöå ( , )� � ýòî ñâîéñòâî äîêàçàíî â [13] è îáîçíà-
÷àåò, ÷òî òàêèå ôóíêöèè ïðåäñòàâèìû â âèäå êîíúþíêöèè ñâîèõ ïðîåêöèé. Ñëåäóþ-
ùàÿ ëåììà ïðåäñòàâëÿåò åñòåñòâåííîå ðàñøèðåíèå ýòîãî óòâåðæäåíèÿ íà ôóíêöèè,
äëÿ êîòîðûõ ñóùåñòâóåò ìàæîðèòàðíûé ïîëèìîðôèçì â ïîëóêîëüöå ( , )min max .
Ëåììà 4. Ïóñòü � : K WT � — ôóíêöèÿ, à Q , R , S — ïîïàðíî íåïåðåñåêàþ-
ùèåñÿ ïîäìíîæåñòâà â T , òàêèå ÷òî Q R S T� � � . Ïóñòü �QR , �QS , �RS — ïðî-
åêöèè ôóíêöèè � íà ïîäìíîæåñòâà Q R� , Q S� , R S� ñîîòâåòñòâåííî.
Åñëè äëÿ � ñóùåñòâóåò ìàæîðèòàðíûé ïîëèìîðôèçì, òî ðàâåíñòâî
� � � �( ) max ( , ), ( , ), ( , )x x x x x x xQR Q R QS Q S RS R S� { }
âûïîëíÿåòñÿ äëÿ ëþáîé ðàçìåòêè x x x x KQ R S
T� �( , , ) . �
Ëåììà äîêàçàíà â ðàáîòå [10].
2. ÇÀÄÀ×È ÐÀÇÌÅÒÊÈ È d-ÎÏÒÈÌÈÇÀÖÈß: ÎÁÇÎÐ ÈÇÂÅÑÒÍÛÕ ÐÅØÅÍÈÉ
Èçâåñòíî [14], ÷òî, âûáèðàÿ íàäëåæàùèì îáðàçîì ïîëóêîëüöî ( , , )W � � ,
â ôîðìàòå ( , )� � -çàäà÷è ìîæíî ïðåäñòàâèòü òàêèå îáøèðíûå êëàññû çàäà÷,
êàê ïðîâåðêà ñîâìåñòèìîñòè îãðàíè÷åíèé [11, 13], ïîäñ÷åò êîëè÷åñòâà ðåøå-
íèé ñèñòåìû îãðàíè÷åíèé [5, 9], îöåíêà ñîâìåñòèìîñòè ðàçìûòûõ îãðàíè÷å-
íèé [2, 3] è ðàçíîîáðàçíûå îïòèìèçàöèîííûå çàäà÷è âèäà min ( )
x K S
S S
T
x
� �
�
�
� ,
ãäå � — ëþáàÿ îïåðàöèÿ, îáðàçóþùàÿ ñ îïåðàöèåé min ïîëóêîëüöî íà óïîðÿ-
äî÷åííîì ìíîæåñòâå W [12].  ðàáîòå [15] ïîêàçàíî, ÷òî â ôîðìàòå ( , )� � -çàäà-
÷è ìîæíî ïðåäñòàâèòü è âû÷èñëåíèå min ( )[ ]d
x K
S
S S
T
x
�
�
�
�
� — êà÷åñòâ d íàèëó÷-
øèõ ðàçìåòîê.  òåðìèíàõ è îáîçíà÷åíèÿõ íàñòîÿùåé ñòàòüè ýòîò ðåçóëüòàò
ñôîðìóëèðîâàí â ñëåäóþùåé ëåììå. ×àñòíûé ñëó÷àé ýòîé ëåììû äëÿ d-ìèíèìè-
çàöèè ôóíêöèé âèäà �S
S
Sx
�
�
�
( ) äîêàçàí â [16, 17].
Ëåììà 5. Äëÿ êîììóòàòèâíîãî ïîëóêîëüöà ( , , )W min � , ôóíêöèé
�S
SK W: ,� S � � , è ÷èñëà d ñóùåñòâóåò êîììóòàòèâíîå ïîëóêîëüöî
( , , )[ ] [ ] [ ]W d d d� � è ôóíêöèè �[ ] [ ]: ,d S
S
dK W� S � � , òàêèå ÷òî
� �
� �
�[ ] [ ] [ ] ( )d
x K
d
S
d S S
T
x
�
� min ( )[ ]d
x K
S
S S
T
x
�
�
�
�
� . �
Äîêàçàòåëüñòâî. Îïðåäåëèì W d[ ] êàê ìíîæåñòâî âñåõ ìîíîòîííî íåóáûâàþ-
ùèõ ïîñëåäîâàòåëüíîñòåé ( , , , )a a ad1 2 � , a Wi � , è äëÿ çàäàííîãî a W� îáîçíà-
÷èì � � �a W d[ ] ïîñëåäîâàòåëüíîñòü, ïåðâûé ýëåìåíò êîòîðîé ðàâåí a , à îñòàëü-
íûå ðàâíû � .
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 71
Ïóñòü a a a ad� ( , , , )1 2 � è b b b bd� ( , , , )1 2 � — äâå ïîñëåäîâàòåëüíîñòè.
Ïðåäñòàâèì ñîâîêóïíîñòü âåëè÷èí ( , , , , , , , )a a a b b bd d1 2 1 2� � â âèäå ìîíîòîííî
íåóáûâàþùåé ïîñëåäîâàòåëüíîñòè è îïðåäåëèì ñóììó a bd� [ ] êàê ïîñëåäîâàòåëü-
íîñòü ïåðâûõ d ýëåìåíòîâ â ïîëó÷åííîé óïîðÿäî÷åííîé ïîñëåäîâàòåëüíîñòè.
Ïðåäñòàâèì ñîâîêóïíîñòü âåëè÷èí a bi j� , i j d, , ,�1 � , â âèäå ìîíîòîííî íå-
óáûâàþùåé ïîñëåäîâàòåëüíîñòè è îïðåäåëèì ïðîèçâåäåíèå a bd�[ ] êàê ïîñëåäîâà-
òåëüíîñòü ïåðâûõ d ýëåìåíòîâ â ïîëó÷åííîé óïîðÿäî÷åííîé ïîñëåäîâàòåëüíîñòè.
Èç òîãî ôàêòà, ÷òî òðîéêà ( , , )W min � — êîììóòàòèâíîå ïîëóêîëüöî ñ íóëå-
âûì ýëåìåíòîì � , ñëåäóåò, ÷òî îïåðàöèè a bd� [ ] è a bd�[ ] íà ìíîæåñòâå W d[ ]
îáðàçóþò êîììóòàòèâíîå ïîëóêîëüöî ñ íóëåâûì ýëåìåíòîì ��� .
Îïðåäåëèì ôóíêöèè �[ ] [ ]: ,d S
S
dK W S� � � , òàê, ÷òî �[ ] ( )d S Sx �
� � ��S Sx( ) . Î÷åâèäíî, ÷òî äëÿ ëþáîé ôóíêöèè � : I W� ñïðàâåäëèâî, ÷òî
� �
� �
� � �[ ] ( ) ( )d
i I i I
i i� � , è ïîýòîìó � �
� �
� � �[ ] ( ) ( )d
S
S S
S
S Sx x
� �
� � .
Î÷åâèäíî òàêæå, ÷òî
�
� �
� � �[ ] [ ]( ) min ( )d
i I
d
i I
i i� � , è ïîýòîìó � � �
� � � �
� � �[ ] [ ] [ ]( ) min ( ).d
x K
d
S
S S d
x K
S
S S
T T
x x
�
�
� � �
Ëåììà 6. Ïóñòü Qmin è Q� — âðåìåíà âûïîëíåíèÿ îïåðàöèé min ,{ }a b è
a b� . Âû÷èñëèòåëüíàÿ ñëîæíîñòü îïåðàöèè a bd� [ ] èìååò ïîðÿäîê d Q� min . Âû-
÷èñëèòåëüíàÿ ñëîæíîñòü îïåðàöèè a bd�[ ] èìååò ïîðÿäîê ( log ) ( )mind d Q Q� � � . �
Îáà óòâåðæäåíèÿ ëåììû äîñòàòî÷íî ëåãêî äîêàçûâàþòñÿ, õîòÿ âòîðîå óòâåð-
æäåíèå íåñêîëüêî ìåíåå î÷åâèäíîå, ÷åì ïåðâîå.
Ìíîæåñòâî ( , )[ ] [ ]� �d d -çàäà÷ d-îïòèìèçàöèè ñîäåðæèò ìíîæåñòâî
( , )min � -çàäà÷ 1-îïòèìèçàöèè, êîòîðîå â ñâîþ î÷åðåäü ñîäåðæèò NP-ïîëíûé
êëàññ ( , )� � -çàäà÷ ñîâìåñòèìîñòè îãðàíè÷åíèé. Ïîýòîìó óíèâåðñàëüíîå ðåøåíèå
âñåãî êëàññà ( , )[ ] [ ]� �d d -çàäà÷ íåâîçìîæíî, òåì áîëåå óñêîðåííîå ðåøåíèå ýòî-
ãî êëàññà. Óñêîðåííàÿ d-îïòèìèçàöèÿ âîçìîæíà íå áîëåå ÷åì äëÿ òàêèõ ïîäêëàñ-
ñîâ ôóíêöèé, êîòîðûå äîïóñêàþò ýôôåêòèâíóþ 1-îïòèìèçàöèþ. Òàêèå ïîäêëàñ-
ñû ôóíêöèé âèäà �
�S
S Sx
�
� ( ) ôîðìèðóþò äâóìÿ ñïîñîáàìè. Ïðè ïåðâîì ñïîñîáå
òðåáóþò, ÷òîáû ñòðóêòóðà � çàäà÷è ïðèíàäëåæàëà îïðåäåëåííîìó çàäàííîìó
êëàññó ñòðóêòóð, ðàçðåøàÿ ïðè ýòîì ïðîèçâîëüíûå ôóíêöèè �S
SK W: � , S �� .
Ïðè âòîðîì ñïîñîáå, íàîáîðîò, ðàçðåøàþò ïðîèçâîëüíûå ñòðóêòóðû � çàäà÷è,
òðåáóÿ ïðè ýòîì, ÷òîáû ôóíêöèè �S
SK W: � ïðèíàäëåæàëè îïðåäåëåííîìó çà-
äàííîìó êëàññó ôóíêöèé, íàçûâàåìîìó ÿçûêîì çàäà÷.
Îãðàíè÷åíèÿ íà ñòðóêòóðó � ìíîæåñòâà T ôîðìóëèðóþò â òåðìèíàõ ãèïåð-
ãðàôà G T( , )� ñ ìíîæåñòâîì T âåðøèí è ìíîæåñòâîì � ãèïåððåáåð. Ñëîæíîñòü
ñòðóêòóðû � õàðàêòåðèçóþò òàê íàçûâàåìîé øèðèíîé width ( )� àöèêëè÷åñêîãî
ïîêðûòèÿ ãèïåðãðàôà G T( , )� [18]. Ðåøåíèå ( , )min � -çàäà÷ 1-îïòèìèçàöèè ñ ìà-
ëîé øèðèíîé width ( )� ìîæíî ïîëó÷èòü ñ ïîìîùüþ íåïîñëåäîâàòåëüíîãî äèíà-
ìè÷åñêîãî ïðîãðàììèðîâàíèÿ [19], è íà ýòîì îñíîâàí ðÿä àëãîðèòìîâ d-îïòèìè-
çàöèè, â êîòîðûõ d-îïòèìèçàöèÿ ñâîäèòñÿ ê òîé èëè èíîé ðàçóìíîé ïîñëåäîâà-
òåëüíîñòè 1-îïòèìèçàöèé. Â ðàáîòàõ [6, 8, 15] ïðåäñòàâëåíî ýëåãàíòíîå
îáîáùåíèå ýòèõ ÷àñòíûõ ìåòîäîâ íà îñíîâå ëåììû 5 è òîãî ôàêòà, ÷òî íåïîñëå-
äîâàòåëüíîå äèíàìè÷åñêîå ïðîãðàììèðîâàíèå ïðèìåíèìî äëÿ ðåøåíèÿ
( , )� � -çàäà÷ íà ïðîèçâîëüíîì ïîëóêîëüöå, à íå òîëüêî ( , )min � -çàäà÷. Ïðè
ýòîì â ñèëó ëåììû 6 d-îïòèìèçàöèÿ ôóíêöèè âèäà �
�S
S Sx
�
� ( ) îêàçûâàåòñÿ âñå-
ãî â d d� log ðàç ñëîæíåå åå 1-îïòèìèçàöèè, à íå â d T K� �| | | | ðàç. Òàêèì îáðà-
72 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
çîì, â èññëåäîâàíèÿõ d-îïòèìèçàöèè ôóíêöèé âèäà �
�S
S Sx
�
� ( ) íà ñòðóêòóðàõ
ìàëîé øèðèíû äîñòèãíóòà îïðåäåëåííàÿ ñòåïåíü çàâåðøåííîñòè.
×òî êàñàåòñÿ èññëåäîâàíèé d-îïòèìèçàöèè ôóíêöèé âèäà �
�S
S Sx
�
� ( ) íà ïðî-
èçâîëüíûõ ñòðóêòóðàõ, òî îíè åùå äàëåêè îò êàêîé-ëèáî çàâåðøåííîñòè. Â ðàáî-
òå [12] äîñòàòî÷íî ïîëíî îïèñàíû ÿçûêè, ò.å. ïîäêëàññû ôóíêöèé �S
SK W: � , ïî-
ðîæäàþùèå ïîëèíîìèàëüíî ðàçðåøèìûå ïîäêëàññû ( , )min � -çàäà÷ 1-îïòèìèçàöèè.
Íàèáîëåå èçâåñòíûìè ñðåäè íèõ ÿâëÿþòñÿ çàäà÷è ñóáìîäóëÿðíîé ìèíèìèçàöèè
(ñì. [20]). Ïîäêëàññû ôóíêöèé �S
SK: ,� { }0 1 , ïîðîæäàþùèå ïîëèíîìèàëüíî ðàç-
ðåøèìûå ïîäêëàññû ( , )� � -çàäà÷ ñîâìåñòèìîñòè, èññëåäîâàíû â [11]. Äëÿ ýòèõ ïîä-
êëàññîâ ôóíêöèé (è äëÿ íåêîòîðûõ äðóãèõ) èçâåñòíû êîíñåðâàòèâíûå àëãîðèòìû
1-îïòèìèçàöèè. Ñëåäîâàòåëüíî, äëÿ âñåõ ýòèõ êëàññîâ ôóíêöèé âûïîëíèìà d-îïòè-
ìèçàöèÿ ïî ìåòîäó Ëîóëåðà èëè ïî ìåòîäó, îïèñàííîìó â ðàçä. 3. Îäíàêî àâòîðàì
íàñòîÿùåé ñòàòüè íå èçâåñòíû ðàáîòû ïî óñêîðåííîé d-îïòèìèçàöèè äëÿ êàêî-
ãî-ëèáî èç óêàçàííûõ êëàññîâ. Îïèñàííàÿ â ðàçä. 4–6 óñêîðåííàÿ d-ìèíèìèçàöèÿ
ôóíêöèé âèäà max ( )
S
S Sx
��
� , èíâàðèàíòíûõ îòíîñèòåëüíî ìàæîðèòàðíîãî îïåðàòîðà,
çàïîëíÿåò îïðåäåëåííûé ôðàãìåíò â ýòîì åùå íå çàïîëíåííîì ïðîáåëå.
3. ÁÀÇÎÂÛÉ ÀËÃÎÐÈÒÌ d-ÎÏÒÈÌÈÇÀÖÈÈ
Ïóñòü � : K WT � — ôóíêöèÿ íà ìíîæåñòâå ðàçìåòîê, äëÿ êîòîðîé ñëåäóåò ïî-
ñòðîèòü ïîäìíîæåñòâî arg min ( )[ ]d
x KT
x
�
� . Äëÿ ëþáîãî ïîäìíîæåñòâà S T� îáîçíà-
÷èì �S ïðîåêöèþ ôóíêöèè � íà ïîäìíîæåñòâî S . Äëÿ S T� ââåäåì äëÿ êðàò-
êîñòè îáîçíà÷åíèå Sol xS d
x K
S S
S
S
�
�
arg min ( )[ ] � . Èñêîìûì ðåøåíèåì çàäà÷è ÿâëÿ-
åòñÿ SolT , è åãî ïîñòðîåíèå îñíîâàíî íà ñëåäóþùåé âçàèìîñâÿçè ìåæäó SolS
è SolS i\{ }.
Òåîðåìà 1. Ïóñòü S T� , i S� , P S i� \ { }, Sol xP d
x K
P P
P
P
�
�
arg min ( )[ ] � . Ïóñòü
Sol K S* � — íåêîòîðîå ïîäìíîæåñòâî ðàçìåòîê.
Åñëè Sol x xd
x x Sol K
S P i
P i P
�
� �
� arg min ( , )[ ]
( , )
� , òî Sol xd
x K
S S
S
S
�
�
� arg min ( )[ ] � . �
Äîêàçàòåëüñòâî. Îáîçíà÷èì y x x xP
x K
S P i
i
( ) ( , )�
�
arg min � è äîêàæåì, ÷òî
max ( ) max ( , ( )) max
( , )x Sol
P P
x Sol
S P P
x xP P P P P i
x x y x
� �
� �� �
� �Sol
S P ix x� ( , ). (8)
Ðàâåíñòâî â ýòîé öåïî÷êå ñïðàâåäëèâî, ïîòîìó ÷òî ôóíêöèÿ �P , ÿâëÿÿñü ïðîåê-
öèåé ôóíêöèè � íà P, îäíîâðåìåííî åñòü ïðîåêöèÿ ôóíêöèè �S íà P. Íåðàâåíñòâî
â ýòîé öåïî÷êå ñïðàâåäëèâî â ñèëó îáùåãî ñâîéñòâà (2) ìíîæåñòâ âèäà arg min [ ]d .
Äåéñòâèòåëüíî, Sol x xd
x x Sol K
S P i
P i P
*
[ ]
( , )
min ( , )�
� �
arg � , à ìíîæåñòâî { }( , ( )) |x y x x SolP P P P�
åñòü ïîäìíîæåñòâî â Sol KP � , ñîñòîÿùåå èç d ðàçìåòîê.
Äëÿ ëþáîé ðàçìåòêè ( , )x x Sol KP i P
� � ñïðàâåäëèâà öåïî÷êà
� �S P i
y K
S Px x x y( , ) min ( , )�
�
�� �
� � ��
� � �
� � �P P
x Sol
P P
x x Sol
S P ix x x x
P P P i
( ) max ( ) max ( , )
( , )
. (9)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 73
Ïåðâîå íåðàâåíñòâî â ýòîé öåïî÷êå î÷åâèäíî. Ñëåäóþùåå çà íèì ðàâåíñòâî
ñïðàâåäëèâî, ïîòîìó ÷òî �P åñòü ïðîåêöèÿ �S íà P. Íåðàâåíñòâî
� �P P
x Sol
P Px x
P P
( ) max ( )* �
�
â öåïî÷êå ñïðàâåäëèâî, ïîòîìó ÷òî ( , )x x Sol KP i P
� �
è, ñëåäîâàòåëüíî, x SolP P
� . Ïîñëåäíåå íåðàâåíñòâî â öåïî÷êå (9) ñëåäóåò èç ðà-
íåå äîêàçàííîé öåïî÷êè (8).
Òàêèì îáðàçîì, íåðàâåíñòâî � �
S P i
x x Sol
S P ix x x x
P i
( , ) max ( , )
( , )
�
� �
âûïîëíÿåò-
ñÿ äëÿ ëþáîé ðàçìåòêè ( , )x x Sol KP i P � , îòêóäà â ñèëó (3) ñëåäóåò, ÷òî
Sol xd
x K
S S
S
S
�
�
� arg min ( )[ ] � . �
Èç äîêàçàííîé òåîðåìû ñëåäóåò àëãîðèòì d-îïòèìèçàöèè �. Àëãîðèòì ñòðî-
èò Sol i{ }0
äëÿ ïîäìíîæåñòâà, ñîñòîÿùåãî èç åäèíñòâåííîãî îáúåêòà i0 , à çàòåì âû-
ïîëíÿåò ïîñëåäîâàòåëüíîñòü ïåðåñ÷åòîâ SolS i\{ } â SolS . Ðåçóëüòàòîì ðàáîòû àë-
ããîðèòìà ÿâëÿåòñÿ Sol x
T d
x KT
�
�
arg min ( )[ ] � .
Ñëîæíîñòü ïîñòðîåíèÿ Sol i{ }0
îïðåäåëÿåòñÿ ñëîæíîñòüþ ñëåäóþùèõ âû÷èñëåíèé:
— äëÿ êàæäîé ìåòêè x Ki0
� âû÷èñëÿþò âåëè÷èíû � �{ }i i
x K
i Rx x x
R
R0 0 0
( ) min ( , )�
�
,
ãäå R T i� \ { }0 . Ñëîæíîñòü ýòèõ âû÷èñëåíèé ðàâíà ñëîæíîñòè | |K -êðàòíîé
1-îïòèìèçàöèè;
— èç ïîëó÷åííûõ | |K âåëè÷èí �{ }i ix
0 0
( ), x Ki0
� , âûáèðàþò d íàèìåíüøèõ. Èç-
âåñòíî [21], ÷òî ñëîæíîñòü ýòîãî âûáîðà ëèíåéíî çàâèñèò îò | |K , ò.å. ðàâíà O K(| | ).
Òàêèì îáðàçîì, ñëîæíîñòü ïîñòðîåíèÿ Sol i{ }0
ðàâíà O K C O K(| | ) (| | )� � �
� �O K C(| | ), ãäå C — ñëîæíîñòü îäíîêðàòíîé 1-îïòèìèçàöèè.
Ñëîæíîñòü ïåðåñ÷åòà SolS i\{ } â SolS îïðåäåëÿåòñÿ ñëîæíîñòüþ ñëåäóþùèõ
âû÷èñëåíèé:
— äëÿ êàæäîé ðàçìåòêè x SolS i S i\ \{ } { }� è êàæäîãî çíà÷åíèÿ x Ki � âû÷èñëÿ-
þò âåëè÷èíû
� �S S i i
x K
S i i Rx x x x x
R
R
( , ) min ( , , )\ \{ } { }�
�
, (10)
ãäå R T S� \ . Ñëîæíîñòü ýòèõ âû÷èñëåíèé ðàâíà ñëîæíîñòè d K� | |-êðàòíîé
1-îïòèìèçàöèè;
— èç ïîëó÷åííûõ d K� | | âåëè÷èí �S S i ix x( , )\{ } âûáèðàþò d íàèìåíüøèõ.
Òàêèì îáðàçîì, ïåðåñ÷åò SolS i\{ } â SolS èìååò ñëîæíîñòü O d K C( | | )� � ,
à ñëîæíîñòü âû÷èñëåíèÿ Sol x
T d
x KT
�
�
arg min ( )[ ] � ðàâíà O d K T C( | | | | )� � � .
Àëãîðèòì d-îïòèìèçàöèè, êîòîûé ñëåäóåò èç òåîðåìû 1, èìååò òàêóþ æå îá-
ëàñòü ïðèìåíèìîñòè è òàêóþ æå ñëîæíîñòü, ÷òî è êëàññè÷åñêèé àëãîðèòì Ëîóëå-
ðà. Îáà àëãîðèòìà ïðèìåíèìû ïðè íàëè÷èè êîíñåðâàòèâíîãî àëãîðèòìà 1-îïòè-
ìèçàöèè è ñâîäÿòñÿ ê ( | | | | )d K T� � -êðàòíîé 1-îïòèìèçàöèè. Îäíàêî èç òåîðå-
ìû 1 ñëåäóåò íå òîëüêî àëãîðèòì d-îïòèìèçàöèè, ïî ñóùåñòâó íå óñòóïàþùèé
êëàññè÷åñêîìó àëãîðèòìó Ëîóëåðà, íî è âîçìîæíîñòü óñêîðåííîé d-îïòèìèçà-
öèè òàêèõ ôóíêöèé, êîòîðûå äîïóñêàþò ýôôåêòèâíûé ïåðåñ÷åò ïðîåêöèè �S
â ïðîåêöèþ �S i\{ } äëÿ ëþáîãî ïîäìíîæåñòâà S T� .  ÷àñòíîñòè, êàê áóäåò ïîêà-
çàíî â ðàçä. 5, òàêîé ýôôåêòèâíûé ïåðåñ÷åò âîçìîæåí äëÿ ôóíêöèé � : K WT �
âèäà �� �x x
S
S S) max ( )�
��
íà ñòðóêòóðàõ âòîðîãî ïîðÿäêà, èíâàðèàíòíûõ îòíîñè-
òåëüíî ìàæîðèòàðíîãî îïåðàòîðà.
74 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
4. ÏÐÅÎÁÐÀÇÎÂÀÍÈÅ (min, max)-ÇÀÄÀ× Â ÇÀÄÀ×È ÂÒÎÐÎÃÎ ÏÎÐßÄÊÀ
Äàëåå èññëåäóþòñÿ ( , )� � -çàäà÷è íå îáùåãî âèäà (4)–(6), à çàäà÷è â ïîëóêîëüöå
(min, max) ïðè ïðîèçâîëüíî âûáðàííûõ, íî ôèêñèðîâàííûõ ìíîæåñòâàõ K è W.
Ïîýòîìó çàäà÷ó áóäåì ïðåäñòàâëÿòü íå â âèäå ïÿòåðêè (4), à áîëåå êðàòêî
â âèäå òðîéêè �� � � �T SS, , ( | )� �� . Öåëåâàÿ ôóíêöèÿ � : K WT � çàäà÷è �
îïðåäåëÿåò êà÷åñòâî � �( ) max ( )x x
S
S S�
� �
ðàçìåòêè x K T� . Ðåøåíèåì çàäà÷è �
ÿâëÿåòñÿ ïîäìíîæåñòâî Sol xd
x KT
( ) min ( )[ ]� �
�
arg � , ñîñòîÿùåå èç d íàèëó÷øèõ
ðàçìåòîê.
Ëåììà 7. Åñëè äëÿ çàäà÷è �� � � �T SS, , ( | )� �� ñóùåñòâóåò ìàæîðèòàðíûé
ïîëèìîðôèçì, òî ñóùåñòâóåò çàäà÷à � � � � ��T SS, , ( | )*
� �� íà ñòðóêòóðå âòî-
ðîãî ïîðÿäêà, òàêàÿ ÷òî äëÿ ëþáîé ðàçìåòêè x K T� , âûïîëíÿåòñÿ ðàâåíñòâî
max ( ) max ( )
S
S S
S
S Sx x
� �
�
�� �
� � . � (11)
Ëåììà 7 ÿâëÿåòñÿ î÷åâèäíûì ñëåäñòâèåì ëåììû 4.
Çàäà÷ó íà ñòðóêòóðå âòîðîãî ïîðÿäêà áóäåì ïðåäñòàâëÿòü íå òðîéêîé
� � �T SS, , ( | )� �� , à ïàðîé � � �T i j Tij, ( | , )� , ãäå � ij , i j T, � , — ôóíêöèè âèäà
K K W� � , òàêèå ÷òî � �ij jik k k k( , ) ( , )� � � äëÿ ëþáûõ i j T, � , k k K, � � è
� ii k k W( , ) min� � äëÿ ëþáîãî i T� . Ïðàâàÿ ñòîðîíà ðàâåíñòâà (11), ò.å. çíà÷åíèå
öåëåâîé ôóíêöèè � íà ðàçìåòêå x K T� , ïðèîáðåòàåò âèä max ( , )
,i j T
ij i jx x
�
� .
Ôóíêöèè �S , S �� , ïðåîáðàçóþòñÿ â ôóíêöèè � ij , i j T, � , ñëåäóþùèì îá-
ðàçîì. Âíà÷àëå âû÷èñëÿþòñÿ ïðîåêöèè ôóíêöèé �S , S �� , íà ïàðû { }i j S, � ,
ò.å. âû÷èñëÿþòñÿ âåëè÷èíû
� �ij
S
i j
x K
S R i jx x x x x
R
R
( , ) min ( , , )�
�
, (12)
ãäå R S i j� \ ,{ }. Ñëîæíîñòü ýòîãî ïåðåñ÷åòà ðàâíà O( ( ) ( ( )) )Vol Ord� �� 2 , ãäå
Vol ( )� è Ord ( )� — îáúåì èñõîäíûõ äàííûõ è ïîðÿäîê çàäà÷è � ñîîòâåò-
ñòâåííî.
Çàòåì âû÷èñëÿþòñÿ âåëè÷èíû
� �ij
S
ij
Sx y x y( , ) max ( , )�
��
(13)
äëÿ êàæäîé ïàðû i j T, � è äëÿ êàæäîé ïàðû x y K, � . Ñëîæíîñòü ýòèõ âû÷èñëå-
íèé ðàâíà O T K(| | | | | | )2 2� � � .
Âû÷èñëåíèÿ ïî ôîðìóëàì (12) è (13) íå çàâèñÿò îò âèäà ìàæîðèòàðíîãî îïå-
ðàòîðà, ñóùåñòâîâàíèå êîòîðîãî ÿâëÿåòñÿ óñëîâèåì ëåììû 7. Áîëåå òîãî, ýòè âû-
÷èñëåíèÿ ïðèìåíèìû ê ëþáûì ôóíêöèÿì �S , S �� , à íå òîëüêî ê òåì, äëÿ êîòî-
ðûõ òàêîé îïåðàòîð ñóùåñòâóåò. Îäíàêî, åñëè äëÿ � ñóùåñòâóåò ìàæîðèòàðíûé
ïîëèìîðôèçì, òî ãàðàíòèðóåòñÿ ýêâèâàëåíòíîñòü ôóíêöèé � è �, à â ïðîòèâíîì
ñëó÷àå òàêàÿ ýêâèâàëåíòíîñòü íå èñêëþ÷åíà, íî è íå ãàðàíòèðóåòñÿ.  ñèëó ýòîãî,
êàçàëîñü áû, íà âõîä àëãîðèòìà (12), (13) ñëåäóåò ïîäàâàòü òîëüêî òàêèå ôóíêöèè �,
äëÿ êîòîðûõ ñóùåñòâóåò ìàæîðèòàðíûé ïîëèìîðôèçì. Ïðîâåðêà èíâàðèàíòíîñòè
âõîäíîé ôóíêöèè � îòíîñèòåëüíî íåêîòîðîãî àïðèîðè íåèçâåñòíîãî ìàæîðèòàðíîãî
îïåðàòîðà ìîæåò îêàçàòüñÿ ñëèøêîì ñëîæíîé, îñîáåííî, åñëè ó÷åñòü, ÷òî ðå÷ü èäåò
î íåîäíîðîäíûõ ïî ìíîæåñòâó T ïîëèìîðôèçìàõ. Ñëåäóÿ [18], ìîæíî ïðåîäîëåòü
ýòè òðóäíîñòè, âêëþ÷èâ â âû÷èñëåíèÿ (12) è (13) ïðîöåäóðó ñàìîêîíòðîëÿ, êîòî-
ðàÿ ïðåäîòâðàòèò íåýêâèâàëåíòíîå ïðåîáðàçîâàíèå � â � áåç ïðîâåäåíèÿ, âîçìîæ-
íî, òðóäíîé ïðîâåðêè èíâàðèàíòíîñòè çàäà÷è � îòíîñèòåëüíî íåêîòîðîãî ìàæî-
ðèòàðíîãî ïîëèìîðôèçìà. Â ðàññìàòðèâàåìûé àëãîðèòì (12), (13) ñðàâíèòåëüíî
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 75
ëåãêî ââåñòè òàêîé ñàìîêîíòðîëü. Äëÿ ýòîãî íåîáõîäèìî ïðîâåðèòü, âûïîëíÿþòñÿ
ëè ðàâåíñòâà
� �S S
i j
i j
S
i jx x x( ) max ( , )
,
,�
��
(14)
äëÿ âñåõ S �� è äëÿ âñåõ x KS
S� .
Ñëîæíîñòü O( ( ) ( ( )) )Vol Ord� �� 2 ýòîé ïðîâåðêè òàêàÿ æå, êàê è âû÷èñëå-
íèÿ (12), è ïîýòîìó âêëþ÷åíèå ñàìîêîíòðîëÿ (14) â àëãîðèòì (12), (13) íå óâåëè÷è-
âàåò åãî ñëîæíîñòè. Ñàìîêîíòðîëèðóþùèéñÿ àëãîðèòì ýêâèâàëåíòíîãî ïðåîáðàçî-
âàíèÿ ñîñòîèò èç âû÷èñëåíèé (12), ñàìîêîíòðîëÿ (14) è âû÷èñëåíèé (13), åñëè âû-
ïîëíÿþòñÿ âñå ðàâåíñòâà (14).  ýòîì ñëó÷àå ðåçóëüòàòîì ðàáîòû àëãîðèòìà
ÿâëÿåòñÿ çàäà÷à � âòîðîãî ïîðÿäêà, ýêâèâàëåíòíàÿ èñõîäíîé çàäà÷å �. Åñëè õîòÿ
áû îäíî èç ðàâåíñòâ (14) íå âûïîëíÿåòñÿ, àëãîðèòì âûäàåò ñîîáùåíèå î íåâîçìîæ-
íîñòè æåëàåìîãî ýêâèâàëåíòíîãî ïðåîáðàçîâàíèÿ. Îäíàêî ýòî ïðîèñõîäèò, òîëüêî
åñëè äëÿ èñõîäíîé çàäà÷è � îòñóòñòâóåò ìàæîðèòàðíûé ïîëèìîðôèçì.
Ñëåäóåò èìåòü â âèäó, ÷òî àëãîðèòì ìîæåò çàâåðøèòüñÿ óñïåøíûì ïîëó÷åíèåì
çàäà÷è � äëÿ íåêîòîðûõ âõîäíûõ çàäà÷ �, äëÿ êîòîðûõ ìàæîðèòàðíûé ïîëèìîðôèçì
îòñóòñòâóåò. Ýòî, âîîáùå-òî, ïîëîæèòåëüíîå ñâîéñòâî íåèçáåæíî ïðèâîäèò ê ðèñêó
ïðè ïîñëåäóþùåì ðåøåíèè çàäà÷è �, äëÿ êîòîðîé òîæå ìîæåò îòñóòñòâîâàòü ìàæî-
ðèòàðíûé ïîëèìîðôèçì. Ïîýòîìó ïîñëåäóþùèå àëãîðèòìû ðåøåíèÿ ïîëó÷åííîé çà-
äà÷è � âòîðîãî ïîðÿäêà òàêæå äîëæíû áûòü ñàìîêîòðîëèðóþùèìèñÿ.
5. ÔÓÍÊÖÈÈ ÂÒÎÐÎÃÎ ÏÎÐßÄÊÀ È ÈÕ d-ÎÏÒÈÌÈÇÀÖÈß
Ïðèìåì äëÿ óäîáñòâà, ÷òî T n� { }1 2, , ,� , è îïðåäåëèì ñåìåéñòâî ïîäìíî-
æåñòâ S Tr � , r n�{ }2 3, , ,� , S Tn � , S S rr r
�1 \ { }.
Îïðåäåëåíèå 7. Çàäà÷ó �� � � �T i j Tij, ( | , )� íàçîâåì ñîãëàñîâàííîé ïî ñå-
ìåéñòâó S Tr � , r n� 2, ,� , åñëè äëÿ ëþáîãî r ïðîåêöèÿ ôóíêöèè
max ( , )
,i j T
ij i jx x
�
� íà S r åñòü ôóíêöèÿ max ( , )
,i j S
ij i j
r
x x
�
� . �
Óñêîðåííàÿ d-îïòèìèçàöèè ôóíêöèé âèäà max ( , )
,i j T
ij i jx x
�
� îñíîâàíà íà äâóõ
èäåÿõ. Ïåðâàÿ èäåÿ ñîñòîèò â òîì, ÷òî åñëè äëÿ çàäà÷è �� � � �T i j Tij, ( | , )� ñó-
ùåñòâóåò ìàæîðèòàðíûé ïîëèìîðôèçì, òî äëÿ íåå ñóùåñòâóåò ñîãëàñîâàííàÿ çà-
äà÷à �� �� � � �T i j Tij, ( | , )� , ýêâèâàëåíòíàÿ çàäà÷å � â òîì ñìûñëå, ÷òî
max ( , ) max ( , )
, ,i j T
ij i j
i j T
ij i jx x x x
�
�
�
�� � äëÿ âñåõ x K T� . Âòîðàÿ èäåÿ ñîñòîèò â ýôôåê-
òèâíîì âû÷èñëåíèè arg min max ( , )[ ]
,
,d
x K
i j T
i j i j
T
x x
�
�
�� ñ ïîìîùüþ áàçîâîãî àëãîðèòìà
d-îïòèìèçàöèè, îñíîâàííîãî íà òåîðåìå 1. Ýêâèâàëåíòíîå ïðåîáðàçîâàíèå
( , )min max -çàäà÷è ê ñîãëàñîâàííîìó âèäó îñíîâàíî íà ñëåäóþùåé ëåììå.
Ëåììà 8. Ïóñòü �� � � �T i j Tij, ( | , )� — ( )min, max -çàäà÷à, t T� , S T t� \ { }.
Åñëè äëÿ � ñóùåñòâóåò ìàæîðèòàðíûé ïîëèìîðôèçì, òî ñóùåñòâóåò çàäà÷à
� � � � �T i j Tij, ( | , )� , òàêàÿ ÷òî
max ( , ) max ( , )
, ,i j T
ij i j
i j T
ij i jx x x x
� �
�� � , x K T� , (15)
max ( , ) min max ( , )
, ,i j S
ij i j
x K i j T
ij i jx x x x
t� � �
�
!"
#
$%
� � , x K S� . � (16)
Äîêàçàòåëüñòâî. Ââåäåì â ðàññìîòðåíèå âñïîìîãàòåëüíóþ ôóíêöèþ
�� �: K WT ñî çíà÷åíèÿìè � ��
�
�( ) max ( , )x x x
i S
it i t è ôóíêöèþ �� �: K WS —
ïðîåêöèþ �� íà S . Ïîñêîëüêó äëÿ çàäà÷è � ñóùåñòâóåò ìàæîðèòàðíûé ïîëèìîð-
76 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
ôèçì, òî â ñèëó ëåììû 2 ôóíêöèÿ �� èíâàðèàíòíà îòíîñèòåëüíî ýòîãî æå ïîëè-
ìîðôèçìà.  ñâîþ î÷åðåäü, èç ëåììû 4 ñëåäóåò, ÷òî ôóíêöèÿ �� ïðåäñòàâèìà
â âèäå � ��
�
��( ) max ( , )
,
x x x
i j S
ij i j , ãäå � ij
� — ïðîåêöèÿ �� íà { }i j, . Îïðåäåëèì âå-
ëè÷èíû � ij i jx x( , ), i j T, � , x x Ki j, � , òàê ÷òî
� � �ij i j ij i j ij i jx x x x x x( , ) max ( , ), ( , )*� { } äëÿ i j S, � , (17)
� �it i t it i tx x x x( , ) ( , )� äëÿ i S� , (18)
è ïîêàæåì, ÷òî äëÿ íèõ ñïðàâåäëèâû ðàâåíñòâà (15) è (16).
Ïîñêîëüêó �� — ýòî ïðîåêöèÿ �� íà S , òî íåðàâåíñòâî max ( , )
,i j S
ij i jx x
�
� ��
�
�
max ( , )
i S
it i tx x� âûïîëíÿåòñÿ äëÿ ëþáîãî x K T� è ïîýòîìó
max ( , ) max max ( , ), max
, ,i j T
ij i j
i j S
ij i j
i S
x x x x
� � �
� &
'
(
� � � it i tx x( , )
)
*
+
�
� &
'
( � �
�max max ( , ), max ( , ), max
, ,i j S
ij i j
i j S
ij i j
i
x x x x� �
�
)
*
+
�
S
it i tx x� ( , )
� &
'
(
)
*
+
�
� �
max max ( , ), max ( , ) max
,i j S
ij i j
i S
it i t
i
x x x x� �
,
( , )
j T
ij i jx x
�
� ,
÷òî äîêàçûâàåò ðàâåíñòâî (15). Ðàâåíñòâî (16) äîêàçûâàåò öåïî÷êà
min max ( , ) min max max
, ,x K i j T
ij i j
x K i j S
ij
t t
x x
� � � �
� &
'
(
� � ( , ), max ( , )x x x xi j
i S
it i t
�
)
*
+
��
� &
'
(
)
� � �
max max ( , ), min max ( , )
,i j S
ij i j
x K i S
it i tx x x x
t
� � *
+
�
� &
'
(
)
*
+
�
� �
�max max ( , ), max ( , ) m
, ,i j S
ij i j
i j S
ij i jx x x x� � ax ( , )
,i j S
ij i jx x
�
� . �
Ñëîæíîñòü ïðåîáðàçîâàíèÿ � â � îïðåäåëÿåòñÿ ñëîæíîñòüþ âû÷èñëåíèÿ
ïðîåêöèè ôóíêöèè �� �: K WT íà S T t� \ { }, ò.å. ïåðåñ÷åòà âåëè÷èí � it i tx x( , ),
i S� , â âåëè÷èíû � ij i jx x� ( , ), i j S, � . Âûïîëíèì ýòîò ïåðåñ÷åò ïîäîáíî ïðåîáðà-
çîâàíèþ çâåçäû â ñèìïëåêñ, îïèñàííîìó â [22] äëÿ èíîé ñèòóàöèè. Â ðàññìàòðè-
âàåìîì ñëó÷àå ýòîò ïåðåñ÷åò îñíîâàí íà ñëåäóþùèõ ðàññóæäåíèÿõ.
Âûáåðåì îáúåêòû m n S, � , îáîçíà÷èì R S m n� \ ,{ } è äëÿ ôóíêöèè � mn
� , êî-
òîðàÿ ÿâëÿåòñÿ ïðîåêöèåé �� íà { }m n, , çàïèøåì öåïî÷êó ðàâåíñòâ
� �mn m n
x K x K x K x K
x x x
t R
R
t R
R
�
� �
�
� �
� �( , ) min min ( ) min min max ( , )
i S
it i tx x
�
��
� &
'
(� � �
min min max ( , ), ( , ), max
x K x K
mt m t nt n t
i Rt R
R
x x x x� � � it i tx x( , )
)
*
+
�
� &
'
(� � �
min max ( , ), ( , ), min max
x K
mt m t nt n t
x K i Rt R
R
x x x x� � � it i tx x( , )
)
*
+
�
� &
'
(� � �
min max ( , ), ( , ), max min
x K
mt m t nt n t
i R x Kt i
x x x x� � � it i tx x( , )
)
*
+
�
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 77
� &
'
(� � �
min max ( , ), ( , ), max min
x K
mt m t nt n t
i S x Kt i
x x x x� � � it i tx x( , )
)
*
+
. (19)
Èç öåïî÷êè (19) ñëåäóåò, ÷òî âû÷èñëåíèå çíà÷åíèé � ij x y� ( , ), i j S, � , x y K, � ,
ñâîäèòñÿ ê âû÷èñëåíèþ âñïîìîãàòåëüíûõ âåëè÷èí
q k x kt
i S x K
it i
i
( ) max min ( , )�
� �
� , k K� , (20)
à çàòåì — âåëè÷èí
� � �ij
k K
it jt tx y x k y k q k�
�
�( , ) min max ( , ), ( , ), ( ){ }. (21)
Âû÷èñëåíèÿ (20) èìåþò ñëîæíîñòü ïîðÿäêà (| | | | )K T2� , à âû÷èñëåíèÿ (21) —
ïîðÿäêà (| | | | )K T3 2� . Òàêèì îáðàçîì, ïðåîáðàçîâàíèå çàäà÷è � â çàäà÷ó �
èìååò ñëîæíîñòü O K T(| | | | )3 2� , à ýêâèâàëåíòíîå ïðåîáðàçîâàíèå çàäà÷è â ñî-
ãëàñîâàííóþ — ñëîæíîñòü O K T(| | | | )3 3� , ïîòîìó ÷òî ñâîäèòñÿ ê T-êðàòíîìó
âûïîëíåíèþ îïåðàöèé (20) è (21).
Ïóñòü S Tr � , r n� 2 3, , ,� , — ñåìåéñòâî ïîäìíîæåñòâ, òàêèõ ÷òî S Tn � ,
S S rr r
�1 \ { }, à �� � � �T i j Tij, ( | , )� — ñîãëàñîâàííàÿ ïî ýòîìó ñåìåéñòâó çàäà-
÷à. Îáîçíà÷èì Sol x xr d
x K
i j S
ij i j
Sr r
�
�
�
arg min max ( , )[ ]
,
� . Ïîñêîëüêó max ( , )
,i j S
ij i j
r
x x
�
�
åñòü ïðîåêöèÿ ôóíêöèè max ( , )
,i j T
ij i jx x
�
� íà S r , òî â ñèëó òåîðåìû 1 äëÿ ìíî-
æåñòâ Solr
1 è Solr ñïðàâåäëèâà ðåêóðñèÿ
Solr d
x k Sol K
i j S
ij
r
r
� &
'
(�
� �
�
arg min max max ([ ]
( , )
,
1
1
� x x x ki j
i S
ir i
r
� �
�
�
)
*
+
, ), max ( , )
1
� .
(22)
Àëãîðèòì ïîñòðîåíèÿ ðåøåíèÿ Sol x xn d
x K
i j T
ij i j
T
�
�
�
arg min max ( , )[ ]
,
� íà÷èíàåò
ðàáîòó ñ ïîñòðîåíèÿ Sol2 äëÿ S 2 1 2� { }, , à çàòåì â ðåçóëüòàòå ïîñëåäîâàòåëüíîñòè
ïåðåñ÷åòîâ Solr
1 â Solr â ñîîòâåòñòâèè ñ (22) ïîëó÷àåò ðåøåíèå Soln . Ïîñòðîåíèå
Sol2 ñîñòîèò â âûáîðå d íàèìåíüøèõ âåëè÷èí èç | |K 2 âåëè÷èí �12 ( , )x y ,
x y K, � :
Sol x yd
x y K
2 12�
�
arg min ( , )[ ]
,
� , (23)
è èìååò ñëîæíîñòü O K(| | )2 .
Ïåðåñ÷åò Solr
1 â Solr â ñîîòâåòñòâèè ñ (22) ñîñòîèò èç ñëåäóþùèõ âû÷èñëå-
íèé. Äëÿ êàæäîé ðàçìåòêè x Solr
�
� 1 è êàæäîé ìåòêè k K� âû÷èñëÿåòñÿ
âåëè÷èíà
f x k x x
i j S
ij i j
i S
ir
r r
( , ) max max ( , ), max
,
�
�
� �
�
� &
'
(
1 1
� � ( , )*x ki
)
*
+
. (24)
Ñ ó÷åòîì òîãî, ÷òî âåëè÷èíû max ( , )
,i j S
ij i j
r
x x
�
� �
1
� óæå áûëè ïîëó÷åíû ïðè ôîð-
ìèðîâàíèè Solr
1, âû÷èñëåíèå çíà÷åíèÿ f x k( , )� äëÿ îäíîé ïàðû x Solr
�
� 1,
k K� , èìååò îöåíêó ñëîæíîñòè O T(| | ), à íå O T(| | )2 , à ñëîæíîñòü âû÷èñëå-
íèÿ f x k( , )� äëÿ d K� | | òàêèõ ïàð ðàâíà O d K T( | | | | )� � .
Çàòåì íàõîäÿò d íàèìåíüøèõ ÷èñåë â ïîëó÷åííîé ñîâîêóïíîñòè d K� | | ÷è-
ñåë è ñòðîÿò
Sol f x kr d
x k Sol Kr
�
�
� �
�arg min ( , )[ ]
( , ) 1
. (25)
78 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
Ñëîæíîñòü ýòîãî ïîèñêà ðàâíà O d K( | | )� . Ñóììàðíàÿ ñëîæíîñòü ïåðåñ÷åòà
Solr
1 â Solr ðàâíà O d K T( | | | | )� � , ïîòîìó ÷òî ñîñòîèò èç ñëîæíîñòè
d K T� �| | | | âû÷èñëåíèé (24) è ñëîæíîñòè O d K( | | )� âû÷èñëåíèé (25).  ðå-
çóëüòàòå | |T -êðàòíîãî ïåðåñ÷åòà Solr
1 â Solr , r n� 3 4, , ,� , ïîëó÷àåòñÿ ðåøå-
íèå Sol x xn d
x K
i j T
ij i j
T
�
�
�
arg min max ( , )[ ]
,
� . Ñëîæíîñòü ýòîãî ïåðåñ÷åòà èìååò ïîðÿ-
äîê ( | | | | )d K T� � 2 .
Òàêèì îáðàçîì, ïðåäñòàâëåííûé àëãîðèòì d-îïòèìèçàöèè ñîñòîèò èç äâóõ
÷àñòåé: ïðåîáðàçîâàíèÿ ðåøàåìîé çàäà÷è â ñîãëàñîâàííóþ ïî ôîðìóëàì (20),
(21) è | |T -êðàòíîãî ïåðåñ÷åòà Solr
1 â Solr ïî ôîðìóëàì (24), (25). Âû÷èñëèòåëü-
íàÿ ñëîæíîñòü àëãîðèòìà â öåëîì îïðåäåëÿåòñÿ ñëîæíîñòüþ ïåðâîé ÷àñòè, êîòî-
ðàÿ íå çàâèñèò îò d è èìååò òîò æå ïîðÿäîê (| | | | )K T3 3� , ÷òî è èçâåñòíûé êîí-
ñåðâàòèâíûé àëãîðèòì 1-îïòèìèçàöèè [10]. Âòîðàÿ ñîñòàâëÿþùàÿ àëãîðèòìà
èìååò ñëîæíîñòü O d K T( | | | | )� � 2 è ëèíåéíî çàâèñèò îò d ñ êîýôôèöèåíòîì
ïðîïîðöèîíàëüíîñòè, êîòîðûé íà ïîðÿäîê ìåíüøå, ÷åì | | | |K T3 3� . Ýòî çíà÷èò,
÷òî âîïðåêè îæèäàíèÿì ñëîæíîñòü d-îïòèìèçàöèè ðàññìàòðèâàåìîãî êëàññà
ôóíêöèé íåñóùåñòâåííî çàâèñèò îò d. Åñëè äëÿ êàêîé-òî ôóíêöèè âûïîëíåíà
1-îïòèìèçàöèÿ ïîñðåäñòâîì ïðåîáðàçîâàíèÿ ýòîé ôóíêöèè â ñîãëàñîâàííóþ, òî
ïîëó÷åííóþ ñîãëàñîâàííóþ ôóíêöèþ ìîæíî áåç ñóùåñòâåííûõ çàòðàò
èñïîëüçîâàòü è äëÿ 2-îïòèìèçàöèè, 3-îïòèìèçàöèè è ò.ä.
6. ÑÀÌÎÊÎÍÒÐÎËÈÐÓÞÙÈÉÑß ÀËÃÎÐÈÒÌ d-ÎÏÒÈÌÈÇÀÖÈÈ
Ïðèìåíåíèå àëãîðèòìà (20)–(25) d-îïòèìèçàöèè èìååò òå æå îñîáåííîñòè, ÷òî
è àëãîðèòìà (12), (13) ýêâèâàëåíòíîãî ïðåîáðàçîâàíèÿ çàäà÷. Äëÿ åãî ðåàëèçà-
öèè íå òðåáóåòñÿ çíàíèÿ òîãî ìàæîðèòàðíîãî îïåðàòîðà, îòíîñèòåëüíî êîòîðî-
ãî èíâàðèàíòíà ðåøàåìàÿ çàäà÷à. Áîëåå òîãî, ýòè âû÷èñëåíèÿ ìîæíî âûïîë-
íèòü äëÿ ëþáîé ( , )min max -çàäà÷è, à íå òîëüêî äëÿ òåõ, êîòîðûå èìåþò ìàæî-
ðèòàðíûé ïîëèìîðôèçì. Ïðè ðàáîòå ñ ëþáîé âõîäíîé çàäà÷åé àëãîðèòì çà
êîíå÷íîå âðåìÿ âûõîäèò íà îñòàíîâ, è â ýòîì ñìûñëå îáëàñòüþ îïðåäåëåíèÿ
àëãîðèòìà ÿâëÿåòñÿ NP-òðóäíûé êëàññ âñåõ âîçìîæíûõ ( , )min max -çàäà÷ âòî-
ðîãî ïîðÿäêà. Îäíàêî, åñëè âõîäíàÿ çàäà÷à �� � � �T i j Tij, ( | , )� èìååò ìàæî-
ðèòàðíûé ïîëèìîðôèçì, òî àëãîðèòì ãàðàíòèðóåò ïîëó÷åíèå ïðàâèëüíîãî ðå-
çóëüòàòà Sol x xn d
x K
i j T
ij i j
T
�
�
�
arg min max ( , )[ ]
,
� , à â ïðîòèâíîì ñëó÷àå ýòî íå ãàðàí-
òèðóåòñÿ. Ïîýòîìó àëãîðèòì ñëåäóåò äîïîëíèòü ñðåäñòâàìè ñàìîêîíòðîëÿ,
êîòîðûå äëÿ äàííîãî àëãîðèòìà ìåíåå î÷åâèäíû, ÷åì äëÿ àëãîðèòìà (12), (13),
è îñíîâàíû íà ñëåäóþùèõ ñâîéñòâàõ d-îïòèìèçàöèè.
Ïóñòü �� � � �T i j Tij, ( | , )� — ( , )min max -çàäà÷à (íå îáÿçàòåëüíî ñîãëàñîâàí-
íàÿ). Êàê è ïðåæäå, áóäåì ñ÷èòàòü, ÷òî T n� { }1 2, , ,� . Äëÿ r n� 2 3, , ,� îáîçíà÷èì
S r ïîäìíîæåñòâî { }1 2, , ,� r T� , îáîçíà÷èì xr ìåòêó îáúåêòà r T� , à xr — ðàçìåò-
êó S Kr � ìíîæåñòâà S Tr � . Îáîçíà÷èì òàêæå � r
S
K Wr: � ôóíêöèþ r ïåðåìåí-
íûõ, êîòîðàÿ íà ðàçìåòêå xr ïðèíèìàåò çíà÷åíèå � �r r r rx x x x( ) ( , , , )� �1 2 �
�
�
max ( , )
,i j S
ij i j
r
x x� . Îáîçíà÷èì Sol xr d
x K
r r
Sr
�
�
arg min ( )[ ] � . Äëÿ ìíîæåñòâ Solr
1 è
Solr , r n� 3 4, , ,� , ñïðàâåäëèâî ðåêóððåíòíîå îòíîøåíèå, ïîäîáíîå ñôîðìóëèðî-
âàííîìó â òåîðåìå 1.
Ëåììà 9. Ïóñòü r — ëþáîå ÷èñëî èç ìíîæåñòâà r n�{ }3 4, , ,� è
Sol x xr d
x x Sol K
r r r
r r r
�
� �
�
arg min ( , )[ ]
( , )1 1
1� . (26)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 79
Åñëè ðàâåíñòâî
� �r r
x K
r r rx x x
r
�
�1 1 1( ) min ( , ) (27)
âûïîëíÿåòñÿ äëÿ ëþáîé ðàçìåòêè x Solr r
�1 1, òî
Sol x xr d
x x K
r r r
r r
Sr
�
�
�
arg min ( , )[ ]
( , )1
1� . �
Äîêàçàòåëüñòâî. Îáîçíà÷èì y x x xr
x K
r r r
r
( ) ( , )
�
�1 1arg min � è çàïèøåì öåïî÷êó
max ( ) max ( , (
x Sol
r r
x Sol
r r
r r r r
x x y x
�
�
�
1 1 1 1
1 1 1� � r
x x Sol
r r r
r r r
x x
�
�
�1 1
1
)) max ( , ).
( , )
� (28)
Ðàâåíñòâî â ýòîé öåïî÷êå ñïðàâåäëèâî â ñèëó óñëîâèÿ (27). Ñëåäóþùåå çà
íèì íåðàâåíñòâî ñïðàâåäëèâî â ñèëó îáùåãî ñâîéñòâà (2) ìíîæåñòâ âèäà
arg min [ ]d . Äåéñòâèòåëüíî, ðàâåíñòâî Sol x xr d
x x Sol K
r r r
r r r
�
� �
�
arg min ( , )[ ]
( , )1 1
1� åñòü óñ-
ëîâèå (26) ëåììû, à ìíîæåñòâî {( , ( )) |x y xr r
1 1 x Solr r
�1 1} åñòü ïîäìíîæåñò-
âî â Sol Kr
�1 , ñîñòîÿùåå èç d ðàçìåòîê.
Äëÿ ëþáîé ðàçìåòêè ( , )x x Sol Kr r r
�
�1 1 ñïðàâåäëèâà öåïî÷êà
� � �r r r r r
x Sol
r rx x x x
r r
( , ) ( ) max ( )
�
�
�
� � �
1 1 1 1 1
1 1
max ( , ).
( , )x x Sol
r r r
r r r
x x
��
1
1� (29)
Ïåðâîå íåðàâåíñòâî â ýòîé öåïî÷êå ñïðàâåäëèâî, ïîòîìó ÷òî
� �r r r
i j S
ij i j
i S
x x x x
r r
( , ) max max ( , ), max
,
�
�
� �
�
� &
'
(
1
1
� )
*
+
�
1
�ir i rx x( , )
� �
�
� �
�
max ( , ) ( )
,i j S
ij i j r r
r
x x x
1
1 1� � . (30)
Ñëåäóþùåå çà íèì íåðàâåíñòâî � �r r
x Sol
r rx x
r r
�
�
�
1 1 1 1
1 1
( ) max ( ) ñïðàâåäëèâî
ïî îïðåäåëåíèþ 1, ïîñêîëüêó ( , )x x Sol Kr r r
�
�1 1 , òî x Solr r
�
1 1. Ïîñëåäíåå
íåðàâåíñòâî â öåïî÷êå (29) ñëåäóåò èç ðàíåå äîêàçàííîé öåïî÷êè (28). Òàêèì
îáðàçîì,
� �r r r
x x Sol
r r rx x x x
r r r
( , ) max ( , )
( , )
�
�
�
�1 1
1
äëÿ ëþáîé ðàçìåòêè ( , )x x Sol Kr r r
�
�1 1 , îòêóäà â ñèëó (3) ñëåäóåò, ÷òî
Sol x xr d
x x K
r r r
r r
Sr
�
�
�
arg min ( , )[ ]
( , )1
1� . �
Èç ëåììû 9 ñëåäóåò àëãîðèòì, êîòîðûé ïðîâåðÿåò óñëîâèå (27) ïðè êàæäîì
ïåðåñ÷åòå Solr
1 â Solr ïî ôîðìóëàì (24) è (25). Åñëè ýòî óñëîâèå âûïîëíÿåòñÿ
äëÿ êàæäîãî r n� 3 4, , ,� , òî ðåçóëüòàò Soln , ïîëó÷åííûé â êîíöå ðàáîòû àëãî-
ðèòìà, ãàðàíòèðîâàííî ïðàâèëüíûé, ò.å. Sol xn d
x K
n
T
�
�
arg min ( )[ ] � âíå çàâèñèìîñòè
îò ñóùåñòâîâàíèÿ èëè îòñóòñòâèÿ ìàæîðèòàðíîãî ïîëèìîðôèçìà, à òàêæå âíå çà-
âèñèìîñòè îò ñîãëàñîâàííîñòè èëè íåñîãëàñîâàííîñòè ðåøàåìîé çàäà÷è. Èíûìè
ñëîâàìè, ìíîæåñòâî çàäà÷, äëÿ êîòîðûõ óñëîâèå (27) âûïîëíÿåòñÿ, îáðàçóåò ïîä-
îáëàñòü êîìïåòåíòíîñòè ýòîãî àëãîðèòìà. Âñå ñîãëàñîâàííûå çàäà÷è âõîäÿò â ýòó
ïîäîáëàñòü, ïîòîìó ÷òî â òàêèõ çàäà÷àõ ðàâåíñòâî (27) âûïîëíÿåòñÿ äëÿ ëþáîé
ðàçìåòêè x K
S r�
1 , à íå òîëüêî äëÿ x Solr�
1.  ñâîþ î÷åðåäü, ëþáóþ çàäà÷ó,
80 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
äëÿ êîòîðîé ñóùåñòâóåò ìàæîðèòàðíûé ïîëèìîðôèçì, ïóñòü è íåèçâåñòíûé,
ìîæíî ñâåñòè ê ñîãëàñîâàííîé.
Ñëîæíîñòü ïðîâåðêè óñëîâèÿ (27) ïðè r-ì ïåðåñ÷åòå Solr
1 â Solr ðàâíà
O d K T( | | | | )� � 2 . Îäíàêî åñëè ó÷åñòü, ÷òî âåëè÷èíû � r x y( , ), x Solr�
1, y K� ,
óæå âû÷èñëåíû â ïðîöåññå ñàìîãî ïåðåñ÷åòà Solr
1 â Solr , òî ñëîæíîñòü äîïîëíè-
òåëüíûõ âû÷èñëåíèé, íåîáõîäèìûõ äëÿ êîíòðîëÿ (27), ðàâíà O d K( | | )� . Êîíò-
ðîëü óñëîâèÿ (27) íà âñåõ | |T ïåðåñ÷åòàõ Solr
1 â Solr óâåëè÷èâàåò ñëîæíîñòü àë-
ãîðèòìà íà âåëè÷èíó ïîðÿäêà O d K T( | | | | )� � , ÷òî ïðåíåáðåæèòåëüíî ìàëî ïî
ñðàâíåíèþ ñî ñëîæíîñòüþ O K T d K T(| | | | | | | | )3 3 2� � � � àëãîðèòìà â öåëîì, ò.å.
âû÷èñëåíèé ïî ôîðìóëàì (20)–(25).
Ïðåäñòàâèì ïîñëåäîâàòåëüíîñòü âû÷èñëåíèé ïî ôîðìóëàì (20), (21),
(23)–(25), (27) â âèäå ñëåäóþùåãî àëãîðèòìà è ñîîòâåòñòâóþùåé òåîðåìû. Êàê è
ïðåæäå, â àëãîðèòìå èñïîëüçóåòñÿ îáîçíà÷åíèå S rr � { }1� äëÿ r n�{ }1� .
Àëãîðèòì 1
Ïðèâåäåíèå çàäà÷è ê ñîãëàñîâàííîìó âèäó:
for t n:� downto 3 do
for all k K� do q k x kt
i S x K
it i
t i
( ): max min ( , )�
� �
1
� end for // ñîãëàñíî (20)
for all ( , , , )i j x y S S K Kt t� � � �
1 1 do
� � � �ij ij
k K
it jtx y x y x k y( , ) : max ( , ), min max ( , ), ( ,� &
'
( �
{ k q kt), ( )}
)
*
+
// ñîãëàñíî (21)
end for
end for
Ïîñòðîåíèå ðåøåíèÿ:
Sol x yd
x y K
2 12: min ( , )[ ]
,
�
�
arg � // ñîãëàñíî (23)
for r :� 3 to n do
for all x Solr
*�
1 do
for all k K� do
f x k x x
i j S
ij i j
i S
i
r r
( , ): max max ( , ), max
,
�
�
� �
�
� &
'
(
1 1
� � r ix k( , )� )
*
+
// ñîãëàñíî (24)
end for
if min ( , ) max ( , )
,k K i j S
ij i jf x k x x
r�
�
�
� �
1
� then ÎÒÊÀÇ! end if // ñîãëàñíî (27)
end for
Sol f x kr d
x k Sol Kr
: min ( , )[ ]
( , )
�
�
� �
�arg
1
// ñîãëàñíî (25)
end for
Îáîñíîâàíèå àëãîðèòìà, ïðèâåäåííîå â ðàçä. 5 è 6, ÿâëÿåòñÿ äîêàçàòåëüñò-
âîì ñëåäóþùåé òåîðåìû.
Òåîðåìà 2. Àëãîðèòì 1 çàâåðøàåò ðàáîòó çà âðåìÿ O K T d K T(| | | | | | | | )3 3 2� � � � .
Ðåçóëüòàòîì ÿâëÿåòñÿ ëèáî d íàèëó÷øèõ ðàçìåòîê Soln , ëèáî îòêàç îò ðåøåíèÿ
çàäà÷è. Ïîñëåäíåå âîçìîæíî òîëüêî, åñëè äëÿ âõîäíîé çàäà÷è îòñóòñòâóåò ìàæî-
ðèòàðíûé ïîëèìîðôèçì. �
ÇÀÊËÞ×ÅÍÈÅ
Èññëåäîâàíà çàäà÷à ïîèñêà d íàèëó÷øèõ ðàçìåòîê âèäà x T K: � , ãäå T è K —
êîíå÷íûå ìíîæåñòâà, à êà÷åñòâî � : K WT � ðàçìåòîê ïðåäñòàâëåíî â ôîðìà-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 81
òå, ïðèíÿòîì â òåîðèè óäîâëåòâîðåíèÿ îãðàíè÷åíèé. Ïîêàçàíî, ÷òî åñëè ôóíê-
öèÿ � : K WT � èíâàðèàíòíà îòíîñèòåëüíî íåîäíîðîäíîãî ìàæîðèòàðíîãî îïå-
ðàòîðà, ïóñòü è íåèçâåñòíîãî, òî ïîèñê d íàèìåíüøèõ ÷èñåë èç | |K T ÷èñåë
ñâîäèòñÿ çà ïîëèíîìèàëüíîå âðåìÿ ê (| | )T
2 -êðàòíîìó ïîèñêó d íàèìåíüøèõ
÷èñåë èç | |K d� ÷èñåë.  ÷àñòíîñòè, ïðè d �1 ìèíèìèçàöèÿ ôóíêöèè | |T ïåðå-
ìåííûõ ñâîäèòñÿ ê (| | )T
2 -êðàòíîé ìèíèìèçàöèè ôóíêöèè îäíîé ïåðåìåí-
íîé, ïðèíèìàþùåé | |K çíà÷åíèé.
Ýòî äîñòîèíñòâî áûëî áû ñóùåñòâåííî îáåñöåíåíî, åñëè áû íå áûëî èçâåñòíî,
êàê ñåáÿ ïîâåäåò ðàçðàáîòàííûé àëãîðèòì ïðè ïîäà÷å íà åãî âõîä çàäà÷è, äëÿ êîòîðîé
íå ñóùåñòâóåò ìàæîðèòàðíîãî ïîëèìîðôèçìà. Äëÿ ýòîãî ñëó÷àÿ åãî ñëåäîâàëî áû äî-
ïîëíèòü àëãîðèòìîì âõîäíîãî êîíòðîëÿ çàäà÷è, êîòîðûé ïðîâåðÿåò ñóùåñòâîâàíèå
èëè îòñóòñòâèå äëÿ íåå ïîäõîäÿùåãî ïîëèìîðôèçìà. Àâòîðàì íå èçâåñòåí òàêîé àëãî-
ðèòì, è, âîçìîæíî, îí äîâîëüíî òðóäíûé. Äîñòîèíñòâî ðàçðàáîòàííîãî àëãîðèòìà
â òîì, ÷òî äëÿ íåãî òàêîé âõîäíîé êîíòðîëü íå íóæåí. Ìíîæåñòâî çàäà÷, êîòîðûå
ìîæíî ïîäàâàòü íà âõîä àëãîðèòìà, — ýòî NP-òðóäíûé êëàññ âñåõ âîçìîæíûõ ìèíè-
ìàêñíûõ çàäà÷, ïðåäñòàâëåííûõ â îïðåäåëåííîì ôîðìàòå. Ðàáîòà ñ ëþáîé çàäà÷åé çà-
âåðøàåòñÿ ëèáî åå ðåøåíèåì, ëèáî ñîîáùåíèåì «îòêàç», ïîñëåäíåå âîçìîæíî òîëüêî
â òîì ñëó÷àå, åñëè äëÿ ðåøàåìîé çàäà÷è îòñóòñòâóåò ìàæîðèòàðíûé ïîëèìîðôèçì.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Rossi F., van Beek P., Walsh T. Handbook of constraint programming (foundations of artificial
intelligence). New York: Elsevier Science Inc., 2006. 975 p.
2. Cooper M.C. Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets and
Systems. 2003. Vol. 134, N 3. P. 311–342.
3. Ruttkay Z. Fuzzy constraint satisfaction. IEEE World Congress on Computational Intelligence. Proc. of
he Third IEEE Conference. Fuzzy Systems. 1994. Vol. 2. P. 1263–1268.
4. Lawler E.L. A procedure for computing the k best solutions to discrete optimization problems and its
application to the shortest path problem. Management Science. 1972. Vol. 18, N 7. P. 401–405.
5. Bulatov A.A., Dalmau V., Grohe M., Marx D. Enumerating homomorphisms. J. Comput. Syst. Sci.
2012. Vol. 78, N 2. P. 638–650.
6. Dechter R., Flerova N., Marinescu R. Search algorithms for m best solutions for graphical models.
Proc. of the Twenty-Sixth AAAI Conference on Artificial Intelligence. AAAI’12. AAAI Press, 2012.
P. 1895–1901.
7. Eppstein D. Finding the k shortest paths. SIAM J. Comput. 1999. Vol. 28, N 2. P. 652–673.
8. Flerova N., Rollon E., Dechter R. Bucket and mini-bucket schemes for M best solutions over
graphical models. Berlin; Heidelberg: Springer, 2012. P. 91–118.
9. Greco G. and Scarcello F. Structural tractability of enumerating csp solutions. Constraints. 2013.
Vol. 18, N 1. P. 38–74.
10. Âîäîëàçñêèé Å., Ôëàõ Á., Øëåçèíãåð Ì. Ìèíèìàêñíûå çàäà÷è äèñêðåòíîé îïòèìèçàöèè, èíâà-
ðèàíòíûå îòíîñèòåëüíî ìàæîðèòàðíûõ îïåðàòîðîâ. ÆÂÌÌÔ. 2014. Ò. 54, ¹ 8. Ñ. 1368–1378.
11. Cohen D., Jeavons P. The complexity of constraint languages. F. Rossi, P. van Beek, T. Walsh
(Eds). Handbook of Constraint Programming. Ch. 6. Amsterdam: Elsevier, 2006. P. 169–204.
12. Jeavons P., Krokhin A., Zivny S. The complexity of valued constraint satisfaction. Bulletin of
EATCS. 2014. Vol. 113. 35 p.
13. Jeavons P., Cohen D., Cooper M.C. Constraints, consistency and closure. Artif. Intell. 1998.
Vol. 101, N 1–2. P. 251–265.
14. Bistarelli S., Montanari U., Rossi F., Schiex T., Verfaillie G., Fargier H. Semiring-based csps and
valued CSPS: Frameworks, properties, and comparison. Constraints. 1999. Vol. 4, N 3. P. 199–240.
15. Rollon E., Flerova N., Dechter R. Inference schemes for m best solutions for soft CSPS. Proc.
of Workshop on Preferences and Soft Constraints, 2011. P. 124–138.
16. Øëåçèíãåð Ì. Ìàòåìàòè÷åñêèå ñðåäñòâà îáðàáîòêè èçîáðàæåíèé. Êèåâ: Íàóê. äóìêà, 1989.
197 c.
82 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
17. Øëåçèíãåð Ì., Ãëàâà÷ Â. Äåñÿòü ëåêöèé ïî ñòàòèñòè÷åñêîìó è ñòðóêòóðíîìó ðàñïîçíàâàíèþ.
Êèåâ: Íàóê. äóìêà, 2004. 545 c.
18. Hubie Chen, Dalmau V. Beyond hypertree width: Decomposition methods without decompositions.
Berlin; Heidelberg: Springer, 2005. P. 167–181.
19. Bertele U., Brioschi F. Nonserial dynamic programming. Orlando, FL: Academic Press, Inc., 1972.
235 p.
20. Kolmogorov V. Minimizing a sum of submodular functions. Discrete Appl. Math., 2012. Vol. 160,
N 15. P. 2246–2258.
21. Blum M., Floyd R.W., Pratt V., Rivest R.L., Tarjan R.E. Time bounds for selection. Journal of
Computer and System Sciences. 1973. Vol. 7, N 4. P. 448–461.
22. Schlesinger M., Flach B. Some solvable subclasses of structural recognition problems. Czech Pattern
Recognition Workshop. 2000. P. 55–62.
Íàä³éøëà äî ðåäàêö³¿ 06.10.2016
Ì.². Øëåç³íãåð, Á. Ôëàõ, ª.Â. Âîäîëàçñüêèé
ÏÎØÓÊ ÇÀÄÀÍί ʲËÜÊÎÑÒ² ÐÎÇÂ’ßÇʲ ÑÈÑÒÅÌÈ ÐÎÇÌÈÒÈÕ ÎÁÌÅÆÅÍÜ
Àíîòàö³ÿ. Äîñë³äæåíî ì³í³ìàêñíó ìîäèô³êàö³þ çàäà÷³ ðîçï³çíàâàííÿ íåñóïå-
ðå÷íîñò³ ñèñòåìè îáìåæåíü, êîëè äëÿ êîæíîãî ðîçâ’ÿçêó âèçíà÷åíî íå á³íàðíó
äîïóñòèì³ñòü, à ¿¿ ê³ëüê³ñíó õàðàêòåðèñòèêó. Îïèñàíèé â ñòàòò³ àëãîðèòì çíàõî-
äèòü çà ïîë³íîì³àëüíèé ÷àñ çàäàíó ê³ëüê³ñòü íàéêðàùèõ ðîçâ’ÿçê³â ñèñòåìè ðîç-
ìèòèõ îáìåæåíü, ÿêùî ö³ îáìåæåííÿ ³íâàð³àíòí³ â³äíîñíî äåÿêîãî ìàæîðèòàð-
íîãî îïåðàòîðà. Âàæëèâî, ùî äëÿ ðåàë³çàö³¿ àëãîðèòìó íå ïîòð³áíî çíàííÿ öüî-
ãî îïåðàòîðà, á³ëüø òîãî, íå ïîòð³áíî ãàðàíòóâàòè éîãî ³ñíóâàííÿ. Äëÿ
äîâ³ëüíî¿ ñèñòåìè ðîçìèòèõ îáìåæåíü àëãîðèòì àáî çíàõîäèòü çàäàíó ê³ëüê³ñòü
íàéá³ëüø äîïóñòèìèõ ðîçâ’ÿçê³â, àáî äຠâ³äìîâó â³ä ðîçâ’ÿçêó çàäà÷è. Îñòàííº
ìîæëèâî, ò³ëüêè ÿêùî äëÿ ðîçâ’ÿçàíî¿ ñèñòåìè îáìåæåíü òàêîãî îïåðàòîðà íå
³ñíóº.
Êëþ÷îâ³ ñëîâà: äèñêðåòíà îïòèì³çàö³ÿ, ì³í³ìàêñí³ çàäà÷³, ðîçì³òêè, ³íâà-
ð³àíòè, ïîë³ìîðô³çìè.
M.I. Schlesinger, B. Flach, E. Vodolazskiy
FINDING A GIVEN NUMBER OF SOLUTIONS TO A SYSTEM OF FUZZY CONSTRAINTS
Abstract. A minimax modification of a fuzzy constraint satisfaction problem is
considered, where constraints determine not whether a given solution is feasible
but the numerical value of satisfiability. The algorithm is proposed that finds
a given number of solutions with the highest value of satisfiability in
polynomial time for a subclass of problems with constraints invariant to some
majority operator. It is essential that knowing the operator itself is not required.
Moreover, it is not necessary to guarantee its existence. For any system of fuzzy
constraints, the algorithm either finds a given number of best solutions or
declines the problem. The latter is only possible when no such operator exists.
Keywords: discrete optimization, minimax problems, labeling, invariants,
polymorphisms.
Øëåçèíãåð Ìèõàèë Èâàíîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, ãëàâíûé íàó÷íûé ñîòðóäíèê Ìåæäóíàðîäíîãî íàó÷íî-ó÷åáíîãî
öåíòðà èíôîðìàöèîííûõ òåõíîëîãèé è ñèñòåì ÍÀÍ Óêðàèíû è ÌÎÍ Óêðàèíû, Êèåâ,
e-mail: schles@irtc.org.ua.
Ôëàõ Áîðèñ,
äîêòîð íàóê, äîöåíò, Öåíòð ìàøèííîãî çðåíèÿ, ×åøñêèé òåõíè÷åñêèé óíèâåðñèòåò, Ïðàãà,
e-mail: flachbor@cmp.felk.cvut.cz.
Âîäîëàçñêèé Åâãåíèé Âàëåðèåâè÷,
íàó÷íûé ñîòðóäíèê Ìåæäóíàðîäíîãî íàó÷íî-ó÷åáíîãî öåíòðà èíôîðìàöèîííûõ òåõíîëîãèé è ñèñòåì
ÍÀÍ Óêðàèíû è ÌÎÍ Óêðàèíû, Êèåâ, e-mail: waterlaz@gmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 83
|