Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации
На примере задачи о коммивояжере рассмотрен класс труднорешаемых задач комбинаторной оптимизации, которые имеют полиномиальный алгоритм решения. Доказано, что этому классу принадлежат задачи, у которых специальным образом смоделирована структура исходных данных. A class of polynomially solvable prob...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2014 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/115729 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации / Г.А. Донец, И.В. Сергиенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 3-10. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-115729 |
|---|---|
| record_format |
dspace |
| spelling |
Донец, Г.А. Сергиенко, И.В. 2017-04-11T18:37:34Z 2017-04-11T18:37:34Z 2014 Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации / Г.А. Донец, И.В. Сергиенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 3-10. — Бібліогр.: 8 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/115729 519.1 На примере задачи о коммивояжере рассмотрен класс труднорешаемых задач комбинаторной оптимизации, которые имеют полиномиальный алгоритм решения. Доказано, что этому классу принадлежат задачи, у которых специальным образом смоделирована структура исходных данных. A class of polynomially solvable problems of combinatorial optimization is treated. It is shown that this class includes certain problems with specially structured initial data. The reasoning is illustrated with the NP-hard traveling salesman problem. На прикладі задачі про комівояжера розглянуто клас важкорозв’язних задач, які мають поліноміальний алгоритм розв’язання. Доведено, що цьому класу належать задачі, в яких спеціальним чином змодельована структура вхідних даних. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации Method of initial data structure modeling and subclasses of solvable combinatorial optimization problems Метод моделювання структури вхідних даних та підкласи розв’язних задач комбінаторної оптимізації Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| spellingShingle |
Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации Донец, Г.А. Сергиенко, И.В. Кибернетика |
| title_short |
Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| title_full |
Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| title_fullStr |
Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| title_full_unstemmed |
Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| title_sort |
метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| author |
Донец, Г.А. Сергиенко, И.В. |
| author_facet |
Донец, Г.А. Сергиенко, И.В. |
| topic |
Кибернетика |
| topic_facet |
Кибернетика |
| publishDate |
2014 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Method of initial data structure modeling and subclasses of solvable combinatorial optimization problems Метод моделювання структури вхідних даних та підкласи розв’язних задач комбінаторної оптимізації |
| description |
На примере задачи о коммивояжере рассмотрен класс труднорешаемых задач комбинаторной оптимизации, которые имеют полиномиальный алгоритм решения. Доказано, что этому классу принадлежат задачи, у которых специальным образом смоделирована структура исходных данных.
A class of polynomially solvable problems of combinatorial optimization is treated. It is shown that this class includes certain problems with specially structured initial data. The reasoning is illustrated with the NP-hard traveling salesman problem.
На прикладі задачі про комівояжера розглянуто клас важкорозв’язних задач, які мають поліноміальний алгоритм розв’язання. Доведено, що цьому класу належать задачі, в яких спеціальним чином змодельована структура вхідних даних.
|
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/115729 |
| citation_txt |
Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации / Г.А. Донец, И.В. Сергиенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 3-10. — Бібліогр.: 8 назв. — рос. |
| work_keys_str_mv |
AT donecga metodmodelirovaniâstrukturyishodnyhdannyhipodklassyrazrešimyhzadačkombinatornoioptimizacii AT sergienkoiv metodmodelirovaniâstrukturyishodnyhdannyhipodklassyrazrešimyhzadačkombinatornoioptimizacii AT donecga methodofinitialdatastructuremodelingandsubclassesofsolvablecombinatorialoptimizationproblems AT sergienkoiv methodofinitialdatastructuremodelingandsubclassesofsolvablecombinatorialoptimizationproblems AT donecga metodmodelûvannâstrukturivhídnihdanihtapídklasirozvâznihzadačkombínatornoíoptimízacíí AT sergienkoiv metodmodelûvannâstrukturivhídnihdanihtapídklasirozvâznihzadačkombínatornoíoptimízacíí |
| first_indexed |
2025-11-26T19:03:47Z |
| last_indexed |
2025-11-26T19:03:47Z |
| _version_ |
1850769062914686976 |
| fulltext |
Ã.À. ÄÎÍÅÖ, È.Â. ÑÅÐÃÈÅÍÊÎ
ÓÄÊ 519.1 ÌÅÒÎÄ ÌÎÄÅËÈÐÎÂÀÍÈß ÑÒÐÓÊÒÓÐÛ
ÈÑÕÎÄÍÛÕ ÄÀÍÍÛÕ È ÏÎÄÊËÀÑÑÛ
ÐÀÇÐÅØÈÌÛÕ ÇÀÄÀ× ÊÎÌÁÈÍÀÒÎÐÍÎÉ
ÎÏÒÈÌÈÇÀÖÈÈ
Àííîòàöèÿ. Íà ïðèìåðå çàäà÷è î êîììèâîÿæåðå ðàññìîòðåí êëàññ òðóäíîðåøàåìûõ çàäà÷
êîìáèíàòîðíîé îïòèìèçàöèè, êîòîðûå èìåþò ïîëèíîìèàëüíûé àëãîðèòì ðåøåíèÿ. Äîêàçà-
íî, ÷òî ýòîìó êëàññó ïðèíàäëåæàò çàäà÷è, ó êîòîðûõ ñïåöèàëüíûì îáðàçîì ñìîäåëèðîâàíà
ñòðóêòóðà èñõîäíûõ äàííûõ.
Êëþ÷åâûå ñëîâà: òðóäíîðåøàåìûå çàäà÷è, ïîëèíîìèàëüíûé àëãîðèòì, NP-ïîëíûå çàäà-
÷è, çàäà÷à î êîììèâîÿæåðå, çàäà÷à î íàçíà÷åíèÿõ, ðàçðåøèìûé ïîäêëàññ çàäà÷, êîìáèíà-
òîðíàÿ îïòèìèçàöèÿ, ìàòðèöû Ñóïíèêà, Êàëüìàíñîíà, Äåìèäåíêî, Ìîíæà.
ÂÂÅÄÅÍÈÅ
Ïðè ðåøåíèè íîâûõ çàäà÷ ÷àñòî âîçíèêàåò âîïðîñ, ìîæíî ëè èõ ðåøèòü ïîëè-
íîìèàëüíûì àëãîðèòìîì.  ñëó÷àå îòðèöàòåëüíîãî îòâåòà íåîáõîäèì áîëåå
äåòàëüíûé àíàëèç ýòîé çàäà÷è ñ èñïîëüçîâàíèåì èçâåñòíîé òåîðèè î òðóäíîðå-
øàåìûõ çàäà÷àõ [1].
Åñëè çàäà÷à NP-ïîëíàÿ, òî åå íåëüçÿ ðåøèòü ïîëèíîìèàëüíûì àëãîðèòìîì.
 ýòîì ñëó÷àå äàëüíåéøèé àíàëèç çàäà÷è ìîæíî ïðîâåñòè äâóìÿ ïóòÿìè.
Ïåðâûé ïóòü ñîñòîèò â òîì, ÷òîáû äåòàëüíåå ïðîàíàëèçèðîâàòü ïàðàìåòðû çà-
äà÷è. Èçâåñòíû ïðèìåðû NP-ïîëíûõ çàäà÷, êîòîðûå ïðè îïðåäåëåííûõ çíà÷åíèÿõ
ïàðàìåòðîâ ñòàíîâÿòñÿ ìåíåå ñëîæíûìè è äîïóñêàþò ðåøåíèå çà ïîëèíîìèàëüíîå
âðåìÿ. Íåêîòîðûå NP-ïîëíûå çàäà÷è ñ ÷èñëîâûìè ïàðàìåòðàìè ìîãóò èìåòü åñòåñ-
òâåííûå îãðàíè÷åíèÿ ïîëèíîìèàëüíîãî õàðàêòåðà íà âåëè÷èíû ýòèõ ïàðàìåòðîâ.
Òîãäà ýòó çàäà÷ó ìîæíî ðåøèòü ñ ïîìîùüþ ïñåâäîïîëèíîìèàëüíîãî àëãîðèòìà.
Âòîðîé ïóòü âîçìîæåí, åñëè çàäà÷à âîçíèêàåò â ïðàêòè÷åñêîé îáëàñòè.  ïðî-
öåññå åå ôîðìàëèçàöèè ÷àñòî àáñòðàãèðóþòñÿ îò íåêîòîðûõ êàæóùèõñÿ íåñóùåñ-
òâåííûìè äåòàëåé è îñîáåííîñòåé. Îäíàêî åñëè èõ ó÷åñòü, òî çàäà÷à ìîæåò èçìå-
íèòüñÿ äî òàêîé ñòåïåíè, ÷òî ñòàíåò ðàçðåøèìîé çà ïîëèíîìèàëüíîå âðåìÿ, ëèáî
ó íåå ïîÿâÿòñÿ íåêîòîðûå âàæíûå ÷àñòíûå ïîäçàäà÷è, êîòîðûå ìîæíî ðåøèòü çà
ïîëèíîìèàëüíîå âðåìÿ. Áûâàåò, ÷òî èíäèâèäóàëüíûå çàäà÷è, ïëîõî ïîääàþùèåñÿ
ðåøåíèþ, âñòðå÷àþòñÿ îòíîñèòåëüíî ðåäêî è èìåþò òàêèå ëåãêî îáíàðóæèâàåìûå
îñîáåííîñòè, ïîçâîëÿþùèå çàáëàãîâðåìåííî ðàñïîçíàòü ýòè çàäà÷è. Òàêèì îáðà-
çîì, âòîðîé ïóòü ñâîäèòñÿ ê àíàëèçó ïîäçàäà÷ ðàññìàòðèâàåìîé çàäà÷è, êîòîðûå
âîçíèêàþò, êîãäà íà ìíîæåñòâî èíäèâèäóàëüíûõ çàäà÷ íàêëàäûâàþòñÿ äîïîëíè-
òåëüíûå îãðàíè÷åíèÿ â øèðîêîì ñìûñëå ñëîâà — áóäü òî óïðîùåíèå èñõîäíûõ
äàííûõ èëè èçìåíåíèå îñíîâíûõ ïàðàìåòðîâ çàäà÷è.
 íàñòîÿùåé ñòàòüå ðàññìîòðåíû ïîäîáíûå îãðàíè÷åíèÿ íà èñõîäíûå äàííûå
â ïðåäïîëîæåíèè, ÷òî îíè ïðåäñòàâëåíû îïðåäåëåííûì ñïîñîáîì, ïîýòîìó ïðåäëà-
ãàåìûé ìåòîä íàçâûâàåòñÿ ìåòîäîì ìîäåëèðîâàíèÿ ñòðóêòóðû èñõîäíûõ äàííûõ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 3
� Ã.À. Äîíåö, È.Â. Ñåðãèåíêî, 2014
ÏÎÄÊËÀÑÑÛ ÐÀÇÐÅØÈÌÎÑÒÈ ÇÀÄÀ×È Î ÊÎÌÌÈÂÎßÆÅÐÅ
Çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè äîñòàòî÷íî õîðîùî èññëåäîâàíû [2, 3].
Äëÿ íåêîòîðûõ èç íèõ ñóùåñòâóþò ýôôåêòèâíûå àëãîðèòìû òî÷íîãî ðåøåíèÿ.
Ñîãëàñíî [1] ýôôåêòèâíûì íàçûâàåòñÿ àëãîðèòì, ñëîæíîñòü êîòîðîãî îöåíèâà-
åòñÿ ïîëèíîìîì îò äëèíû âõîäíûõ äàííûõ, êàê ïðàâèëî, ñ íå î÷åíü âûñîêîé
ñòåïåíüþ. Ïîäàâëÿþùåå áîëüøèíñòâî êîìáèíàòîðíûõ çàäà÷ îïòèìèçàöèè
NP-ïîëíûå, ò.å. òàêèå, äëÿ êîòîðûõ ìàëîâåðîÿòíî ñóùåñòâîâàíèå ïîëèíîìè-
àëüíûõ àëãîðèòìîâ ðåøåíèÿ. Íàèáîëåå èçâåñòíà çàäà÷à î êîììèâîÿæåðå (ÇÊ),
êîòîðàÿ ôîðìóëèðóåòñÿ ñëåäóþùèì îáðàçîì.
Ïóñòü Rn — ïðîñòðàíñòâî âñåõ ñèììåòðè÷åñêèõ n n� -ìàòðèö íàä ïîëåì âå-
ùåñòâåííûõ ÷èñåë R, à C cij� | | | | — ìàòðèöà ðàññòîÿíèé èç Rn . Íåîáõîäèìî íàé-
òè öèêëè÷åñêóþ ïåðåñòàíîâêó � íà ìíîæåñòâå { }1 2, , ,� n , êîòîðàÿ ìèíèìèçèðóåò
ôóíêöèþ
f ci i
i
n
( ) ( )� ��
�
�
1
. (1)
Ýòî îçíà÷àåò, ÷òî êîììèâîÿæåð äîëæåí îáúåõàòü âñå ãîðîäà îò 1 äî n â ïðî-
èçâîëüíîé ïîñëåäîâàòåëüíîñòè è âåðíóòüñÿ â èñõîäíûé ãîðîä, ïðè ýòîì âûáðàòü
êðàò÷àéøèé ïóòü � � � � �� �1 1 2 3 1, ( ), ( ), ( ), .... , ( )n .
Çàäà÷à î êîììèâîÿæåðå ÿâëÿåòñÿ îäíîé èç ôóíäàìåíòàëüíûõ ïðîáëåì êîì-
áèíàòîðíîé îïòèìèçàöèè. Ïðåæäå âñåãî îíà èìååò âàæíîå ïðàêòè÷åñêîå çíà÷å-
íèå, òàê êàê ïðèìåíåíÿåòñÿ â ðàçëè÷íûõ ñôåðàõ ÷åëîâå÷åñêîé äåÿòåëüíîñòè è íà-
óêè, òàêèõ êàê êðèñòàëëîãðàôèÿ, ñîöèîëîãèÿ, ïðèáîðîñòðîåíèå, ïëàíèðîâàíèå,
òåîðèÿ ðàñïèñàíèé è äð. Îíà èìååò òàêæå âàæíîå òåîðåòè÷åñêîå çíà÷åíèå, ïî-
ñêîëüêó âñå íîâûå ìåòîäû, êîòîðûå áûëè ïðåäëîæåíû äëÿ ðåøåíèÿ òðóäíûõ
êîìáèíàòîðíûõ çàäà÷, ïðîõîäèëè ñâîþ ïåðâóþ ïðîâåðêó íà ÇÊ. Èìåííî ñ íåå íà-
÷àëè èçó÷àòü ðàçëè÷íûå ïîäêëàññû èíäèâèäóàëüíûõ çàäà÷, íàëàãàÿ íà âõîäíûå
äàííûå äîïîëíèòåëüíûå îãðàíè÷åíèÿ.
Îïðåäåëåíèå 1. Ïîäêëàññ { }�, S NP-ïîëíîé çàäà÷è � ñ äîïîëíèòåëüíûìè
îãðàíè÷åíèÿìè S íàçûâàåòñÿ ðàçðåøèìûì, åñëè ïðè ýòèõ îãðàíè÷åíèÿõ ñóùåñ-
òâóåò ïîëèíîìèàëüíûé àëãîðèòì åå ðåøåíèÿ.
Èçâåñòíî, ÷òî ïðîáëåìà ìèíèìèçàöèè ôóíêöèè (1) íà âñåõ (íå îáÿçàòåëüíî
öèêëè÷åñêèõ) ïåðåñòàíîâêàõ íàçûâàåòñÿ çàäà÷åé î íàçíà÷åíèÿõ. Î÷åâèäíî, ÷òî
åñëè ðåøåíèå ýòîé çàäà÷è ÿâëÿåòñÿ öèêëè÷åñêîé ïåðåñòàíîâêîé, òî îíî òàêæå
îïòèìàëüíî è äëÿ ÇÊ. Åñëè áû èìåëàñü âîçìîæíîñòü òàê ñôîðìóëèðîâàòü äîïîë-
íèòåëüíûå îãðàíè÷åíèÿ S , ïî êîòîðûì îïòèìàëüíîå ðåøåíèå î íàçíà÷åíèÿõ ÿâ-
ëÿëîñü öèêëè÷åñêîé ïåðåñòàíîâêîé, òî áûë áû íàéäåí ïîäêëàññ ðàçðåøèìîñòè
äëÿ ÇÊ, òàê êàê ëþáàÿ çàäà÷à î íàçíà÷åíèÿõ ðåøàåòñÿ ïîëèíîìèàëüíûì
âåíãåðñêèì àëãîðèòìîì.
 ðàáîòå [4] ïðèâåäåí êëàññè÷åñêèé îáçîð ïóáëèêàöèé î ÇÊ, èç êîòîðîãî
ñëåäóåò, ÷òî ñïèñîê ðàçðåøèìûõ ïîäêëàññîâ ÇÊ ñðàâíèòåëüíî íåáîëüøîé [4, ãë. 4].
Ïåðâûå ðàçðåøèìûå ÇÊ áûëè ïîëó÷åíû, êîãäà îíè ðàññìàòðèâàëàñü äëÿ ãîðî-
äîâ, ðàçìåùåííûõ íà îäíîé ïëîñêîñòè. Ñëåäóþùèé ïîäêëàññ ìîæíî ïîëó÷èòü,
åñëè íà ýëåìåíòû ìàòðèöû ðàññòîÿíèé íàëîæèòü îãðàíè÷åíèå, ÷òîáû èõ çíà÷åíèÿ
ïîä÷èíÿëèñü ïðàâèëó òðåóãîëüíèêà. Îäíàêî íàèáîëüøåå ðàñïðîñòðàíåíèå ïîëó÷è-
ëè ðàçëè÷íûå ñïîñîáû îãðàíè÷åíèé íà ÷åòûðå ýëåìåíòà ìàòðèöû ðàññòîÿíèé.
Ïóñòü 1 � � � � �i j k l n — ïðîèçâîëüíûå ÷åòâåðêè öåëûõ ÷èñåë, à C cij� | | | |
Rn — ïðîèçâîëüíàÿ ìàòðèöà ðàññòîÿíèé. Îáîçíà÷èì �1 �
c cij kl ;
�2 �
c cik jl ; �3 � c cil jk
.
Îïðåäåëåíèå 2. Ñèììåòðè÷åñêàÿ ìàòðèöà C Rn íàçûâàåòñÿ ìàòðèöåé
Êàëüìàíñîíà, åñëè âûïîëíÿþòñÿ óñëîâèÿ
� �1 2� , � �3 2� . (2)
Ìíîæåñòâî ìàòðèö Êàëüìàíñîíà îáîçíà÷èì � . Óñëîâèå (2) ìîæíî çàïèñàòü
â âèäå � � � �2 1 2 3� max , ,{ }. Êàëüìàíñîí äîêàçàë, ÷òî åñëè C � , òî îïòèìàëü-
íûì ìàðøðóòîì ÇÊ áóäåò � � �( , , , , )1 2 1� n n .
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
Îïðåäåëåíèå 3. Ñèììåòðè÷åñêàÿ ìàòðèöà C Rn íàçûâàåòñÿ ìàòðèöåé Ñóï-
íèêà, åñëè âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ:
� �1 2� , � �3 2� . (3)
Ìíîæåñòâî ìàòðèö Ñóïíèêà îáîçíà÷èì �. Óñëîâèå (3) ìîæíî çàïèñàòü
â âèäå � � � �1 1 2 3� min , ,{ }. Ñóïíèê äîêàçàë, ÷òî äëÿ ÇÊ ñ ìàòðèöåé Ñóïíèêà
îïòèìàëüíûì ìàðøðóòîì áóäåò � � ( , , , , , , , , )1 3 5 7 8 6 4 2� .
Íåòðóäíî çàìåòèòü, ÷òî â (2) è (3) èìååòñÿ îáùåå ïåðâîå óñëîâèå. Åñëè îíî
âûïîëíÿåòñÿ, à îáà âòîðûõ óñëîâèÿ íå âûïîëíÿþòñÿ, òî ïîëó÷èì áîëåå ìîùíîå
ìíîæåñòâî � ñèììåòðè÷åñêèõ ìàòðèö Äåìèäåíêî, êîòîðûå íàçâàíû â ÷åñòü àâòî-
ðà ñòàòüè [5], ãäå îíè âïåðâûå ðàññìàòðèâàëèñü. Òàêèì îáðàçîì, ( )� � �
.
Îïðåäåëåíèå 4. Ïèðàìèäàëüíûì ìàðøðóòîì ÇÊ íàçûâàåòñÿ òàêîé ìàðøðóò
� � �
�( , , , , , , , , , )1 1 2 1 1 2 2i i i n i i ik k k n� � , â êîòîðîì i i ik1 2 1� � �
� è ik
�1
� � �
�i ik n2 2� .
×èñëî òàêèõ ìàðøðóòîâ äîñòàòî÷íî áîëüøîå è ðàâíî 2 2n� . Îäíàêî, êàê ïîêàçà-
íî â [6], íàèëó÷øèé ìàðøðóò ñðåäè íèõ ìîæíî íàéòè ïîëèíîìèàëüíûì àëãîðèòìîì
ïîðÿäêà O n( )2 . Â.Ì. Äåìèäåíêî òàêæå äîêàçàë, ÷òî äëÿ ìàòðèöû C � âñåãäà
ñóùåñòâóåò îïòèìàëüíûé ìàðøðóò, êîòîðûé ÿâëÿåòñÿ ïèðàìèäàëüíûì. Òàêèì îáðà-
çîì, óñòàíîâëåíî, ÷òî ÇÊ ñ ìàòðèöåé ðàññòîÿíèé Äåìèäåíêî (Êàëüìàíñîíà è Ñóïíè-
êà) ïðåäñòàâëÿåò ïîäêëàññ ðàçðåøèìûõ çàäà÷. Ïðîâåðèòü âûïîëíåíèå óñëîâèé (2) èëè
(3) äëÿ ïðîèçâîëüíîé ìàòðèöû C ìîæíî çà ïîëèíîìèàëüíîå âðåìÿ ïîðÿäêà O n( )4 .
Èçâåñòíî, ÷òî ìíîæåñòâî îïòèìàëüíûõ ðåøåíèé ÇÊ èìååò ñëåäóþùèå òàê íàçûâàå-
ìûå ñâîéñòâà óñòîé÷èâîñòè îòíîñèòåëüíî âîçäåéñòâèé íà ìàòðèöû ðàññòîÿíèé :
1) ìíîæåñòâî îïòèìàëüíûõ ðåøåíèé äëÿ ÇÊ ñ ìàòðèöåé C cij� | | | | òî æå, ÷òî
è äëÿ ìàòðèöû � �
C c a bij i j| | | |, ãäå ( )ai è ( )b j — ïðîèçâîëüíûå âåêòîðû;
2) îäíîâðåìåííàÿ ïåðåñòàíîâêà ñòîëáöîâ è ñòðîê ìàòðèöû C cij� | | | | â ñîîòâå-
òñòâèè ñ ïåðåñòàíîâêîé � íå èçìåíÿåò äëèíû îïòèìàëüíîãî ìàðøðóòà ÇÊ. Îïòèìàëü-
íûé ìàðøðóò äëÿ ìàòðèöû � �C c i j| | | |( ) ( )� � ïîëó÷àåòñÿ èç îïòèìàëüíîãî ìàðøðóòà
äëÿ ìàòðèöû C âñëåäñòâèå äåéñòâèÿ ïåðåñòàíîâêè � íà åãî ñîñòàâëÿþùèå ýëåìåíòû.
Îäíàêî òå æå âîçäåéñòâèÿ íå âñåãäà ñîõðàíÿþò ïðèíàäëåæíîñòü ìàòðèöû
ðàññòîÿíèé ê ïîäêëàññó � (� , �). Äåéñòâèòåëüíî, íåòðóäíî ïðîâåðèòü, ÷òî ëè-
íåéíûå ïðåîáðàçîâàíèÿ (ñâîéñòâî 1) íå âëèÿþò íà êîìáèíàòîðíûå ñâîéñòâà ìàò-
ðèö Äåìèäåíêî, Êàëüìàíñîíà è Ñóïíèêà. Â òî æå âðåìÿ ïåðåñòàíîâêè ñòðîê èëè
ñòîëáöîâ ìàòðèöû ìîãóò ïðèâåñòè ê ïîòåðå íåêîòîðûõ åå ñâîéñòâ, ñîãëàñíî êîòî-
ðûì îíà îïðåäåëÿåòñÿ êàê ìàòðèöà, ïðèíàäëåæàùàÿ ïîäêëàññàì � � �( , ). Â ñâÿ-
çè ñ ýòèì êàê íåîáõîäèìîñòü âîçíèêàåò ñëåäóþùàÿ ïðîáëåìà.
Ïðîáëåìà ðàñïîçíàâàíèÿ. Çàäàíà ìàòðèöà C c Rij n� | | | | . Íàéòè ïåðåñòà-
íîâêó � òàêóþ, ÷òî ìàòðèöà � � C c i j| | | |( ) ( )� � �.
Åñëè òàêàÿ ïåðåñòàíîâêà ñóùåñòâóåò, òî ìàòðèöà C íàçûâàåòñÿ ïåðåóïîðÿäî-
÷åííîé ìàòðèöåé Äåìèäåíêî (Êàëüìàíñîíà, Ñóïíèêà). Î÷åâèäíî, ÷òî ïîèñê ïå-
ðåñòàíîâêè � â äàííîì ñëó÷àå íàìíîãî ñëîæíåå, ÷åì ðàñïîçíàâàíèå óñëîâèé (2)
èëè (3). Îáîáùàÿ ïîíÿòèå ðàçðåøèìîñòè, ìîæíî óòâåðæäàòü, ÷òî ðàçðåøèìûé
ñëó÷àé åñòü äåéñòâèòåëüíî ðàçðåøèìûì, åñëè åãî ìîæíî ðàñïîçíàòü çà ïîëèíî-
ìèàëüíîå âðåìÿ. Îòìåòèì, ÷òî äî ñèõ ïîð íå ðåøåí âîïðîñ î ñóùåñòâîâàíèè òà-
êîé ïåðåñòàíîâêè äëÿ êîíêðåòíîé ìàòðèöû ðàññòîÿíèé.
Ïðè ðåøåíèè ýòîãî âîïðîñà ìîæíî îñëàáèòü óñëîâèå òîãî, ÷òî ïåðåñòàíîâêà
äîëæíà áûòü îäèíàêîâîé êàê äëÿ ñòðîê, òàê è äëÿ ñòîëáöîâ. Ñ ó÷åòîì ýòèõ îáñòî-
ÿòåëüñòâ óñèëèÿ ìíîãèõ èññëåäîâàòåëåé áûëè íàïðàâëåíû íà òî, ÷òîáû íàéòè òà-
êóþ ïåðåñòàíîâêó � äëÿ ñòðîê ìàòðèöû ðàññòîÿíèé C c Rij n� | | | | , à òàêæå òàêóþ
ïåðåñòàíîâêó � äëÿ åå ñòîëáöîâ, ÷òîáû ìàòðèöà ðàññòîÿíèé � �C c i j| | | |( ) ( )� � èìåëà
ñòðóêòóðó, ñîãëàñíî êîòîðîé ñîîòâåòñòâóþùàÿ ÇÊ ïðèíàäëåæàëà áû ê ïîäêëàññó
ðàçðåøèìûõ çàäà÷. Â ðåçóëüòàòå áûëè íàéäåíû ìàòðèöû ñî ñïåöèàëüíîé
êîìáèíàòîðíîé ñòðóêòóðîé — ìàòðèöû Ìîíæà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 5
Îïðåäåëåíèå 5. Ïðîèçâîëüíàÿ ìàòðèöà C c Rij n� | | | | íàçûâàåòñÿ ìàòðèöåé
Ìîíæà, åñëè �1 �
c cil kj äëÿ âñåõ 1 � � �i k n, 1 � � �j l n .
Îòìåòèì, ÷òî çäåñü â îòëè÷èå îò îïðåäåëåíèé 2 è 3 ìàòðèöà C íå îáÿçàòåëü-
íî ñèììåòðè÷åñêàÿ, à ÷åòûðå ýëåìåíòà èìåþò èíóþ óïîðÿäî÷åííîñòü ñâîèõ èí-
äåêñîâ. Çàäà÷à î êîììèâîÿæåðå ñ ïåðåóïîðÿäî÷åííîé ìàòðèöåé ðàññòîÿíèé
Ìîíæà íàçûâàåòñÿ ÇÊ Ìîíæà.
Ìàòðèöû Ìîíæà èíòåíñèâíî èçó÷àëèñü, ÷òî ñïîñîáñòâîâàëî îáíàðóæåíèþ
ðàçëè÷íûõ èõ ñâîéñòâ, êîòîðûå íå èìåëè ïðÿìîãî îòíîøåíèÿ ê ÇÊ. Áëàãîäàðÿ
ýòèì ñâîéñòâàì íàéäåíû ðåøåíèÿ ìíîãèõ êîìáèíàòîðíûõ çàäà÷, î ðåøåíèè
êîòîðûõ ðàíüøå è íå ïîäîçðåâàëè. Çàäà÷è î êîììèâîÿæåðå Ìîíæà ïîÿâèëèñü
âñëåäñòâèå óñîâåðøåíñòâîâàíèÿ ðàíåå èçâåñòíûõ ÇÊ Ãèëìîðà è Ãîìîðè [7].
Çíà÷èòåëüíûé âêëàä â ðåøåíèå ýòîé ïðîáëåìû ñäåëàëà ãðóïïà ó÷åíûõ èç
Ìèíñêà ïîä ðóêîâîäñòâîì Ä.À. Ñóïðóíåíêî (Â. Àéçåíøòàäò, Â. Äåìèäåíêî,
Í. Ìåòåëüñêèé, Ä. Êðàâ÷óê), à òàêæå ó÷åíûå èç Äíåïðîïåòðîâñêà (Â. Áóðäþê,
Â. Òðîôèìîâ, Â. Äåéíåêî).
ÏÎÄÊËÀÑÑÛ ÐÀÇÐÅØÈÌÛÕ ÇÀÄÀ× È ÔÎÐÌÈÐÎÂÀÍÈÅ ÑÒÐÓÊÒÓÐÛ
ÈÑÕÎÄÍÛÕ ÄÀÍÍÛÕ
Êàê èçâåñòíî, òåîðèÿ NP-ïîëíûõ çàäà÷ áàçèðóåòñÿ íà òåîðèè ðåøåíèÿ çàäà÷
ðàñïîçíàâàíèÿ. Ýòî îáúÿñíÿåòñÿ òåì, ÷òî ïîñëåäíèå èìåþò åñòåñòâåííûé ôîð-
ìàëüíûé ýêâèâàëåíò, óäîáíûé äëÿ èçó÷åíèÿ ìåòîäàìè âû÷èñëåíèé è íàçûâàå-
ìûé ÿçûêîì. Ñîîòíîøåíèå ìåæäó çàäà÷àìè ðàñïîçíàâàíèÿ è ÿçûêàìè óñòàíàâ-
ëèâàþòñÿ ñ ïîìîùüþ ñõåì êîäèðîâàíèÿ, êîòîðûå îáû÷íî ïðèìåíÿþòñÿ äëÿ
ïðåäñòàâëåíèÿ èíäèâèäóàëüíîé çàäà÷è ïðè åå ðåøåíèè íà êîìïüþòåðå. Äëÿ
ëþáîé ðàçóìíîé ñõåìû êîäèðîâàíèÿ ââîäèòñÿ ôóíêöèÿ, êîòîðàÿ ïîëèíîìèàëü-
íî ýêâèâàëåíòíà äëèíå êîäà èíäèâèäóàëüíîé çàäà÷è. Ïîñêîëüêó äâå ðàçëè÷-
íûå ñõåìû êîäèðîâàíèÿ îäíîé è òîé æå çàäà÷è ïîëèíîìèàëüíî ýêâèâàëåíòíû,
äèàïàçîí äëÿ âûáîðà ñõåì êîäèðîâàíèÿ øèðîê è ïîëó÷åííûå ðåçóëüòàòû áó-
äóò âåðíû äëÿ îáîèõ ñëó÷àåâ. Ìíîæåñòâî îáúåêòîâ ìîæåò ïðåäñòàâëÿòüñÿ
â âèäå ïðîèçâîëüíî óïîðÿäî÷åííîé ïîñëåäîâàòåëüíîñòè ýëåìåíòîâ ýòîãî ìíî-
æåñòâà è ñîîòâåòñòâåííî êîäèðîâàòüñÿ.
Ãðàô G V E( , ) ñ ìíîæåñòâîì âåðøèí V è ìíîæåñòâîì ðåáåð E, êàê ïðàâèëî,
ïðåäñòàâëÿåòñÿ íàáîðîì íåóïîðÿäî÷åííûõ (èëè óïîðÿäî÷åííûõ) ïàð ( , )x y , ãäå
x y V, ÿâëÿþòñÿ êîíöàìè ðåáðà. Ýòîò æå ãðàô ìîæíî çàäàòü â âèäå êâàäðàòíîé
n n� -ìàòðèöû ñìåæíîñòåé A G aij( ) | | | |� , ãäå aij �1 , åñëè âåðøèíû ñ íîìåðàìè i è
j ñìåæíû, è aij � 0 â ïðîòèâíîì ñëó÷àå. Ââèäó ñèììåòðè÷íîñòè ìàòðèöû A G( )
äëÿ åå çàäàíèÿ äîñòàòî÷íî âûïèñàòü â îïðåäåëåííîì ïîðÿäêå ëèøü òå ýëåìåíòû,
êîòîðûå ðàñïîëîæåíû íàä ãëàâíîé äèàãîíàëüþ, ò.å. çàäàòü êîðòåæ äëèíû Cn
2 :
( , , , , , , , , , , )a a a a a a a an n n n12 13 1 23 24 2 1� � � � .
×èñëî �( ) ,G a a a an n
Cn�
�
�
12 13
1
14
2
12 2 2 1
2
� íàçûâàåòñÿ äâîè÷íûì êî-
äîì ìàòðèöû A G( ). Ïðè ðàçëè÷íûõ íóìåðàöèÿõ âåðøèí ïîëó÷àåòñÿ n! ðàçëè÷íûõ
êîäîâ ìàòðèöû ñìåæíîñòè. Íàèìåíüøèé èç ýòèõ êîäîâ íàçûâàåòñÿ ìèíè-êîäîì
�( )G , à íàèáîëüøèé — ìàêñè-êîäîì �( )G . Ñóùåñòâóåò åùå îäèí ñïîñîá ïðåä-
ñòàâëåíèÿ ãðàôîâ â âèäå ÷èñëîâûõ ãðàôîâ.
Îïðåäåëåíèå 6. ×èñëîâûì ãðàôîì G X U F g� ( , , , ) íàçûâàåòñÿ n-âåðøèííûé
ãðàô, ïðåäñòàâëåííûé äâóìÿ ìíîæåñòâàìè: X n N n �{ }1 2, , ,� — ìíîæåñòâî
âåðøèí è U N — ìíîæåñòâî îáðàçóþùèõ, à òàêæå ôóíêöèÿìè ñìåæíîñòè
F x xi j( , ) è èñêëþ÷åíèÿ g x( ) .  íåì âåðøèíà x Xk � , åñëè g xk( ) � 0, à âåðøèíû
x x Xi j, ñìåæíû, åñëè F x x Ui j( , ) .
Åñëè F x x x xi j i j( , ) �
, òî òàêîé ÷èñëîâîé ãðàô íàçûâàåòñÿ àðèôìåòè÷åñ-
êèì, åñëè F x x x xi j i j( , ) | |� � , òî — ìîäóëüíûì, åñëè ôóíêöèÿ g x( ) îòñóòñòâóåò,
÷òî ðàâíîñèëüíî X N n� , òî, — íàòóðàëüíûì ÷èñëîâûì ãðàôîì. Ôóíêöèÿ g x( )
íèêàêèõ îïðåäåëåííûõ ñâîéñòâ íå èìååò, îíà ìîæåò ïåðå÷èñëÿòü ïîäìíîæåñòâî
âåðøèí, íå ïðèíàäëåæàùèõ X .
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
 áîëüøèíñòâå ñëó÷àåâ, êîãäà çàäàííûé ãðàô èìååò îïðåäåëåííóþ ñòðóêòó-
ðó — íåñêîëüêî îñåé ñèììåòðèè èëè ïåðèîäè÷åñêè ïîâòîðÿþùèåñÿ ÷àñòè, çàäàòü
ôóíêöèè F x xi j( , ) è g x( ) íå ñëîæíî. Îäíàêî äëÿ ïðîèçâîëüíî âçÿòûõ ãðàôîâ òà-
êîå ïðåäñòàâëåíèå ñîïðÿæåíî ñ îïðåäåëåííûìè òðóäíîñòÿìè. Îñíîâíîå ñâîéñòâî
è ïðåèìóùåñòâî ÷èñëîâûõ ãðàôîâ ñîñòîèò â òîì, ÷òî èõ ñòðóêòóðà çàäàåòñÿ òîëü-
êî èõ îáðàçóþùèìè, ÷òî â çíà÷èòåëüíîé ñòåïåíè ýêîíîìèò ïàìÿòü ïðè èõ ðàçìå-
ùåíèè â êîìïüþòåðå. Êðîìå òîãî, îáû÷íûé ïîèñê â ìàññèâàõ äàííûõ çàìåíÿåòñÿ
âû÷èñëèòåëüíûìè îïåðàöèÿìè. Åùå îäíî ïðåèìóùåñòâî ÷èñëîâûõ ãðàôîâ ïî
ñðàâíåíèþ ñ îáû÷íûìè îïèñàíî â [8] â âèäå ãèïîòåçû: âñå NP-ïîëíûå çàäà÷è íà
÷èñëîâûõ ãðàôàõ èìåþò ïîëèíîìèàëüíûé àëãîðèòì ðåøåíèÿ.
Àíàëîãè÷íî ïî-ðàçíîìó ïðåäñòàâëÿþòñÿ ïðîèçâîëüíûå ìàòðèöû: â âèäå äâó-
ìåðíîãî ìàññèâà A aij� | | | | ( , , , ; , , , )i m j n� �1 2 1 2� � è êàê îäíîìåðíûé ìàññèâ
äëèíû mn, åñëè ñ÷èòûâàòü ýëåìåíòû ïî ñòðîêàì èëè ïî ñòîëáöàì. Äëÿ êâàäðàò-
íûõ ìàòðèö ìîæíî ñ÷èòûâàòü ýëåìåíòû äàæå ïî äèàãîíàëÿì.
Î÷åâèäíî, ÷òî ïåðå÷èñëåííûå ñõåìû êîäèðîâàíèÿ ñîîòâåòñòâóþò íåôîð-
ìàëüíîìó ïîíÿòèþ ðàçóìíûõ ñõåì êîäèðîâàíèÿ, ïîòîìó ÷òî îíè ÿâëÿþòñÿ äîñòà-
òî÷íî ñæàòûìè è ëåãêî äîïóñêàþò äåêîäèðîâàíèå çà ïîëèíîìèàëüíîå âðåìÿ. Òà-
êèì îáðàçîì, ìîæíî ïðåäïîëîæèòü, ÷òî äëÿ ðåøåíèÿ çàäà÷ ñõåìà êîäèðîâàíèÿ íå
èãðàåò îñîáîé ðîëè.
Îäíàêî ïðè ïîèñêå ðàçðåøèìûõ ïîäêëàññîâ NP-ïîëíûõ çàäà÷, êàê óæå îòìå-
÷àëîñü, íåîáõîäèìî íàêëàäûâàòü äîïîëíèòåëüíûå îãðàíè÷åíèÿ íà óñëîâèÿ çàäà-
÷è. Î÷åâèäíî, ÷òî åñëè óñëîâèÿ çàäà÷è çàêîäèðîâàíû î÷åíü ñëîæíîé ñõåìîé, òî
ïîèñê äîïîëíèòåëüíûõ îãðàíè÷åíèé áóäåò ñâÿçàí ñ îïðåäåëåííûìè òðóäíîñòÿ-
ìè. Åñëè óñëîâèÿ çàäà÷è çàêîäèðîâàíû ñ ïîìîùüþ îáúåêòîâ áîëåå ïðîñòîé
ñòðóêòóðû, òî äîïîëíèòåëüíûå îãðàíè÷åíèÿ òàêæå áóäóò íàõîäèòüñÿ è çàïèñû-
âàòüñÿ ïðîùå. Ýòî âàæíî íå òîëüêî äëÿ âîïðîñîâ êîäèðîâàíèÿ, íî è äëÿ
ðàñïîçíàâàíèÿ ðàçðåøèìûõ óñëîâèé çàäà÷è.
Îïðåäåëåíèå 7. Ïîäêëàññ { }�, ,e S èíäèâèäóàëüíûõ çàäà÷ �( , )e S NP-ïîëíîé
çàäà÷è ñî ñõåìîé êîäèðîâàíèÿ e è äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè S e( ) íà ýëå-
ìåíòû ýòîé ñõåìû íàçûâàåòñÿ ðàçðåøèìûì, åñëè ïðè ýòèõ îãðàíè÷åíèÿõ ñóùåñ-
òâóåò ïîëèíîìèàëüíûé àëãîðèòì ðåøåíèÿ çàäà÷è.
Ðàññìîòðèì ïðèìåíåíèå ýòîãî ïîäõîäà ê àíàëèçó ïîäçàäà÷ ÇÊ. Ïóñòü åå èñ-
õîäíûå äàííûå ïðåäñòàâëÿþòñÿ â âèäå ñèììåòðè÷åñêîé n n� -ìàòðèöû ðàññòîÿ-
íèé C c Rij n� | | | | . Çàïèøåì òîëüêî åå íàääèàãîíàëüíûå ýëåìåíòû: ñíà÷àëà —
ïåðâóþ ñòðîêó, çàòåì — âòîðóþ è òàê äàëåå, ò.å. ïðåäñòàâèì ýòó ñòðóêòóðó
â áîëåå ïðîñòîì âèäå — îäíîìåðíûì ìàññèâîì
c c c c c c c cn n n n12 13 1 23 24 2 34 1, , , , , , , , , , ,� � � � .
Ïîñòàâèì â ñîîòâåòñòâèå ýòîé ïîñëåäîâàòåëüíîñòè ôóíêöèþ íàòóðàëüíîãî
àðãóìåíòà � � � �( ) ( ), ( ), , ( )t m� { }1 2 � , ãäå m
n n
�
�( )1
2
.
Ëåììà 1. Äëÿ j i� èìååò ìåñòî ñîîòâåòñòâèå �( )t cij� , ãäå
t n i
i i
j� � �
( )
( )
1
1
2
.
(4)
Äåéñòâèòåëüíî, åñëè áû ó÷èòûâàëèñü âñå ýëåìåíòû êàæäîé ñòðîêè, òî ýëå-
ìåíò cij èìåë áû íîìåð t n i j� �
( )1 . Èç ýòîãî ÷èñëà íåîáõîäèìî âû÷åñòü êîëè-
÷åñòâî íåäèàãîíàëüíûõ ýëåìåíòîâ ïåðâûõ i ñòðîê, ò.å. ÷èñëî k
i i
k
i
�
� �
1
1
2
( )
, ÷òî è
ïðèâåäåò ê ôîðìóëå (4).
Ââåäåì îáîçíà÷åíèÿ:
�( )t cij1 � ; �( )t cik2 � ; �( )t cil3 � ; �( )t c jk4 � ; �( )t c jl5 � ; �( )t ckl6 � .
 äàëüíåéøåì áóäåì ñ÷èòàòü, ÷òî ìàòðèöà c cij� | | | | ïðåäñòàâëåíà ìàòðèöåé
íàòóðàëüíîãî àðãóìåíòà �( )t .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 7
Ëåììà 2. Äëÿ ïðîèçâîëüíûõ 1 � � � � �i j k l n èìååì t t t t1 2 5 6� � � .
Èñïîëüçóÿ ôîðìóëó (4), ïðîâåðèì ïîñëåäîâàòåëüíî òðè íåðàâåíñòâà:
n i
i i
j n i
i i
k j k( )
( )
( )
( )
� �
� � �
� �1
1
2
1
1
2
,
n i
i i
k n j
j j
l j i
n i j
( )
( )
( )
( )
( )� �
� � �
� � �
� � �
1
1
2
1
1
2
0
2 1
2
�
�
�
�
�
�
�l k,
n j
j j
l n k
k k
l n k j
n j k
( )
( )
( )
( )
( )� �
� � �
� � �
� � �
1
1
2
1
1
2
0
2 1
2
�
�
�
�
�
� .
Ó÷èòûâàÿ, ÷òî ìàêñèìàëüíûå çíà÷åíèÿ ïàðàìåòðîâ i n� – 3, j n� – 2, k n� �1
è l n� , â ïðàâûõ ÷àñòÿõ ïîñëåäíèõ äâóõ ñðàâíåíèé âñåãäà áóäóò ïîëîæèòåëüíûå
÷èñëà, ÷òî è ïîäòâåðæäàåò ñïðàâåäëèâîñòü ëåììû 2.
Ëåììà 3. Äëÿ ïðîèçâîëüíûõ çíà÷åíèé 1 � � � � �i j k l n ñïðàâåäëèâî
t t t t1 6 2 5
�
. (5)
Ïîäñòàâëÿÿ ñîîòâåòñòâóþùèå çíà÷åíèÿ, ïîëó÷èì
n i
i i
j n k
k k
l( )
( )
( )
( )
� �
� �
�1
1
2
1
1
2
n i
i i
k n j
j j
l( )
( )
( )
( )
� �
� �
1
1
2
1
1
2
.
Îòñþäà ñëåäóåò n k j
k j k j
( )
( )( )
� �
�
1
2
. Ïîñêîëüêó k j� , îíî ðàâíîñèëüíî
n
k j
�
1
2
. Ìàêñèìàëüíûå çíà÷åíèÿ k n� –1, j n� �2, ïîýòîìó íåðàâåíñòâî
ñïðàâåäëèâî äëÿ ïðîèçâîëüíûõ k è j. Ýòî îçíà÷àåò, ÷òî íåðàâåíñòâî (5) ñïðà-
âåäëèâî, êàê è ëåììà 3.
Òåîðåìà 1. Åñëè �( )t — ëèíåéíàÿ ôóíêöèÿ ñ îòðèöàòåëüíûì óãëîâûì êîýô-
ôèöèåíòîì, òî ñîîòâåòñòâóþùàÿ ïîäçàäà÷à ÇÊ ïðèíàäëåæèò ïîäêëàññó ðàçðåøè-
ìûõ çàäà÷.
Äîêàçàòåëüñòâî. Ïðåäñòàâèì ëèíåéíóþ ôóíêöèþ â âèäå � ( )t t c�
, ãäå
— óãëîâîé êîýôôèöèåíò ïðÿìîé, à c — ïðîèçâîëüíàÿ êîíñòàíòà. Âîçüìåì ïðî-
èçâîëüíûå çíà÷åíèÿ 1 � � � � �i j k l n è ïðîâåðèì äëÿ ýòîé ôóíêöèè ñîîòíîøå-
íèå (2): � �1 2� èëè, ÷òî ðàâíîñèëüíî
� � � �( ) ( ) ( ) ( )t t t t1 6 2 5
�
. (6)
Ïîäñòàâëÿÿ ñþäà çíà÷åíèÿ ôóíêöèè, ïîëó÷àåì
n i
i i
j c n k
k k
l( )
( )
( )
( )
� �
�
�
�
�
�
�
� �
�
�
�
�
�
�
1
1
2
1
1
2
c �
� � �
�
�
�
�
�
�
� �
�
�
�
�
�
� n i
i i
k c n j
j j
l( )
( )
( )
( )
1
1
2
1
1
2
c.
Ïîñëå ïðåîáðàçîâàíèé èìååì ñîîòíîøåíèå
2 3
2
0
n k j
k j
� � ��
�
�
�
�
� �
�
�
�
�
�
� �( ) .
Ïîñêîëüêó k j� , à äàæå ìàêñèìàëüíûå çíà÷åíèÿ k è j íå èçìåíÿò â ïåðâûõ
ñêîáêàõ íåîòðèöàòåëüíîãî çíà÷åíèÿ, ýòî ñîîòíîøåíèå ñïðàâåäëèâî òîëüêî äëÿ
� 0, ÷òî ñîîòâåòñòâóåò íåâîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè �( )t .
Ðàññìîòðèì òåïåðü âòîðîå ñîîòíîøåíèå èç (2) äëÿ ýòîé ôóíêöèè. Îíî
ðàâíîñèëüíî ñîîòíîøåíèþ � � � �( ) ( ) ( ) ( )t t t t3 4 2 5
�
. Ïîäñòàâèì ñþäà
ñîîòâåòñòâóþùèå çíà÷åíèÿ:
8 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
n i
i i
l c n j
j j
k( )
( )
( )
( )
� �
�
�
�
�
�
�
� �
�
�
�
�
�
�
1
1
2
1
1
2
c �
� � �
�
�
�
�
�
�
� �
�
�
�
�
�
� n i
i i
k c n j
j j
l( )
( )
( )
( )
1
1
2
1
1
2
c.
 ðåçóëüòàòå óïðîùåíèé ïîëó÷àåì 0 0� . Àíàëîãè÷íûé ðåçóëüòàò èìååì
è äëÿ ñëó÷àÿ, êîãäà çàìåíèì â (6) çíàê íåðàâåíñòâà íà ïðîòèâîïîëîæíûé, ò.å.
ñïðàâåäëèâî âòîðîå óñëîâèå äëÿ ìàòðèöû Ñóïíèêà.
Ñëåäñòâèå. Ìàòðèöà ðàññòîÿíèé ÇÊ, ïðåäñòàâëåííàÿ ëèíåéíîé ôóíêöèåé
�( )t , ÿâëÿåòñÿ îäíîâðåìåííî ìàòðèöåé Êàëüìàíñîíà è Ñóïíèêà.
Òàêèì îáðàçîì, äàííàÿ ïîäçàäà÷à ÇÊ ïðèíàäëåæèò ïîäêëàññó ðàçðåøèìûõ
çàäà÷, ÷òî è òðåáîâàëîñü äîêàçàòü. Í.Ê. Òèìîôååâà â ñâîåé äèññåðòàöèè íà ñîèñ-
êàíèå ó÷åíîé ñòåïåíè äîêòîðà òåõíè÷åñêèõ íàóê âïåðâûå â êà÷åñòâå ôóíêöèè
ðàññòîÿíèé ïðåäëîæèëà ëèíåéíóþ ôóíêöèþ.
Îòìåòèì, ÷òî äëÿ äîêàçàòåëüñòâà òåîðåìû íå áûëî íåîáõîäèìîñòè äîêàçûâàòü
âòîðîå íåðàâåíñòâî, òàê êàê ïîñëå âûïîëíåíèÿ óñëîâèÿ (6) áûëî ÿñíî, ÷òî äàííàÿ ìàò-
ðèöà ÿâëÿåòñÿ ìàòðèöåé Äåìèäåíêî, ÷òî äîñòàòî÷íî äëÿ ñïðàâåäëèâîñòè òåîðåìû 1.
Íàïîìíèì, ÷òî âûïóêëîé (ââåðõ) ôóíêöèåé íà îòðåçêå [ , ]c d íàçûâàåòñÿ
ôóíêöèÿ f x( ), äëÿ êîòîðîé ñïðàâåäëèâî
f
x x
f x f x1 2
1 2
2
1
2
�
�
��
�
�
�� �
[ ( ) ( )] ,
ãäå x x c d1 2, [ , ] .
Ñóùåñòâóåò ðàâíîñèëüíîå, áîëåå îáùåå îïðåäåëåíèå äëÿ àíàëîãè÷íûõ òî÷åê
ñ òàêèì íåðàâåíñòâîì:
f x x f x f x[ ( ) ] ( ) ( ) ( )
1 2 1 21 1
� �
� .
Öåëî÷èñëåííàÿ ôóíêöèÿ ñ öåëûìè àðãóìåíòàìè 1 2, , ,� m áóäåò âûïóêëîé,
åñëè äëÿ ïðîèçâîëüíûõ òðåõ çíà÷åíèé 1 � � � �p q r m ñïðàâåäëèâî
f q
q p
r p
f p
r q
r p
f r( ) ( ) ( )�
�
�
�
�
.
Òåîðåìà 2. Åñëè �( )t âûïóêëàÿ è íåâîçðàñòàþùàÿ ôóíêöèÿ, òî ñîîòâåòñòâó-
þùàÿ ïîäçàäà÷à ÇÊ ïðèíàäëåæèò ïîäêëàññó ðàçðåøèìûõ çàäà÷.
Äîêàçàòåëüñòâî. Âûáåðåì ïðîèçâîëüíûå çíà÷åíèÿ1 � �i j k l n� � � è ñîîò-
âåòñòâóþùèå èì çíà÷åíèÿ s s s s1 2 3 4, , , . Ïðîâåðèì íåðàâåíñòâî c cij kl
�
�
c cik jl . Äëÿ ýòîãî ïîñòðîèì ãðàôèê ôóíêöèè �( )s è çàôèêñèðóåì çíà÷åíèÿ
ôóíêöèè �( )s1 , �( )s2 , �( )s3 è �( )s4 (ðèñ. 1).
Ñîåäèíèì õîðäîé êîíöû ôóíêöèè è íàéäåì îðäèíàòû òî÷åê ïåðåñå÷åíèÿ
õîðäû ñ àáñöèññàìè s2 è s3 . Çàïèøåì
z
s s
s s
d s
s s
s s
d s1
4 2
4 1
1
2 1
4 1
1�
�
�
�
�
( ) ( ) , z
s s
s s
d s
s s
s s
d s2
4 3
4 1
1
3 1
4 1
4�
�
�
�
�
( ) ( ) .
 ñèëó âûïóêëîñòè ôóíêöèè ñïðàâåäëèâî d s z( )2 1� ; d s z( )3 2� ;
d s d s z z( ) ( )2 3 1 3
�
. Ïîäñòàâëÿÿ â íåðàâåíñòâî d s d s z z( ) ( )2 3 1 3
�
çíà÷åíèÿ
z1 è z2 , ïîñëå íåñëîæíûõ ïðåîáðàçîâàíèé ïîëó÷àåì
d s d s d s d s
s s s s
s s
d( ) ( ) ( ) ( ) [2 3 1 4
4 1 2 3
4 1
�
� �
�
�
�
��
�
�
�� ( ) ( )]s d s1 4� .
 ñèëó ëåììû 3 âûðàæåíèå â ñêîáêàõ èìååò ïîëîæèòåëüíûé çíàê, ïîýòîìó
d s d s d s d s( ) ( ) ( ) ( )2 3 1 4
�
, ÷òî ðàâíîñèëüíî a a a aij kl ik jl
�
. Ýòî îçíà÷àåò,
÷òî çàäàííàÿ ôóíêöèÿ ñîîòâåòñòâóåò îñíîâíîìó óñëîâèþ ìàòðèö ðàçðåøèìûõ
ñëó÷àåâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 9
Ïðîâåðèì âòîðîå óñëîâèå. Îáîçíà÷èì
s i l r( , ) � 1, s j k r( , ) � 2 . Íåïîñðåäñòâåííî ìîæ-
íî óáåäèòüñÿ, ÷òî
s v v s2 1 2 3� � � ; r r s s1 2 2 3
�
. (7)
Ðàññìîòðèì ãðàôèê ôóíêöèè �( )s íà îò-
ðåçêå [ , ]s s2 3 è ïðîâåäåì õîðäó, ñîåäè-
íÿþùóþ çíà÷åíèÿ ôóíêöèè �( )s2 è �( )s3 .
 ðåçóëüòàòå èìååì ãðàôèê, êîòîðûé ñîîò-
âåòñòâóåò ðèñ. 1. Åñëè â íåì ñäåëàåì ïîä-
ñòàíîâêó ñèìâîëîâ P
s s s s
s v v s
�
�
�
��
�
�
��
1 2 3 4
2 2 3 3
, òî
ïîëó÷èì çíà÷åíèÿ òèïà (7):
z
s v
s s
s
v s
s s
s1
3 1
3 2
2
1 2
3 2
3�
�
�
�
�
� �( ) ( ) , z
s v
s s
s
v s
s s
s2
3 2
3 2
2
2 2
3 2
3�
�
�
�
�
� �( ) ( ) .
Ïðè ñëîæåíèè äâóõ íåðàâåíñòâ: d v z( )1 1� è d v z( )2 2� , êîòîðûå ñëåäóþò èç
âûïóêëîñòè ôóíêöèè �( )s , èìååì
� � � �( ) ( ) ( ) ( )v v s
s v v
s s
s
v v
1 2 2
3 1 2
3 2
3
1 22
�
� �
�
�
�
��
�
�
��
�
�
�
�
��
�
�
��
2 2
3 2
s
s s
.
Ïîäñòàâèì ñþäà çíà÷åíèÿ v v1 2
(íåðàâåíñòâî (7)) è ïîëó÷èì �( )v1
�
� � �( ) ( ) ( )v s s2 2 3 . Ýòî ðàâíîñèëüíî c c c cil jk ik jl
�
, ò.å. çàäàííàÿ ôóíê-
öèÿ �( )s ñîîòâåòñòâóåò òàáëèöå ðàññòîÿíèé, êîòîðàÿ ÿâëÿåòñÿ ìàòðèöåé Ñóïíè-
êà. Èòàê, çàäàííàÿ ïîäçàäà÷à ðàçðåøèìà, ÷òî è äîêàçûâàåò òåîðåìó 2.
ÇÀÊËÞ×ÅÍÈÅ
Òàêèì îáðàçîì, ìîæíî ìîäåëèðîâàòü ïðîèçâîëüíóþ ôóíêöèþ ðàññòîÿíèé, íà-
êëàäûâàÿ íà íåå îïðåäåëåííûå îãðàíè÷åíèÿ, ÷òî èíîãäà ïðèâîäèò ê ðàçðåøè-
ìûì ñëó÷àÿì. Òàê, íàïðèìåð, Â.Ì. Ñóïðóíåíêî â [6] âçÿë òàêóþ ôóíêöèþ
ðàññòîÿíèé, äëÿ êîòîðîé ýëåìåíòû ìàòðèöû ðàññòîÿíèé A Rij n� | | | |
óäîâ-
ëåòâîðÿëè ñëåäóþùèì óñëîâèÿì: | | | | ,j i l k ij kl� � � � �
ij ji� .
Áûëî äîêàçàíî, ÷òî îïòèìàëüíûé ìàðøðóò íàõîäèòñÿ ñðåäè ïèðàìèäàëüíûõ öèêëîâ.
Îòìåòèì, ÷òî ïðîáëåìà ðàñïîçíàâàíèÿ çàäà÷, ãäå ìîäåëèðóþòñÿ èñõîäíûå
äàííûå, ðåøàåòñÿ ïðîùå, ÷åì çàäà÷à ðàñïîçíàâàíèÿ ìàòðèö Äåìèäåíêî (Êàëü-
ìàíñîíà, Ñóïíèêà, Ìîíæà), è èìååò ïî÷òè ëèíåéíóþ ñëîæíîñòü.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. à ý ð è Ì . , Ä æ î í ñ î í Ä . Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è. — Ì.: Ìèð,
1982. — 416 ñ.
2. Ï à ï à ä è ì è ò ð è ó Õ . , Ñ ò à é ã ë è ö Ê . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ. Àëãîðèòìû è ñëîæíîñòü. —
Ì.: Ìèð, 1985. — 512 ñ.
3. Ñå ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû ðåøåíèÿ,
èññëåäîâàíèÿ. — Ê.: Íàóê. äóìêà, 2003. — 264 ñ.
4. T h e t r u v e l l i n g salesman problem / E.I. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys. —
Chichester: Wiley, 1983. — 375 c.
5. Ä å ì è ä å í ê î  . Ì . Ñïåöèàëüíûé ñëó÷àé çàäà÷è î áðîäÿ÷åì òîðãîâöå // Âåñö³ àêàä. íàâóê Áåëàðóñ.
ÑÑÐ. — 1976. — ¹ 5. — Ñ. 28–32.
6. Ñ ó ï ð ó í å í ê î Ä . À . Ê çàäà÷å î áðîäÿ÷åì òîðãîâöå // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
1975. — ¹ 5. — Ñ. 121–128.
7. G i l m o r y P . C . , G o m o r y R . E . Seqnencing a one state variable machine a solvable case of the
traveling salesman problem // Oper. Res. — 1964. — 12. — P. 635–675.
8. Ä î í å ö à . À . , Ø ó ë è í î ê È . Ý . Îá îáùåì ïðåäñòàâëåíèè ÷èñëîâèõ ãðàôîâ // Òåîð³ÿ
îïòèìàëüíèõ ð³øåíü. — 2004. — ¹ 3. — Ñ. 11–18.
Ïîñòóïèëà 23.04.2013
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
Ðèñ. 1. Ãðàôèê âûïóêëîé ââåðõ ôóíêöèè
�( )s1 �( )s
2
�( )s3
�( )s4
s
z1
z2
s3s2s1 s4
d
0
|