Новые подходы к решению задач дискретного программирования на основе лексикографического поиска
Предложены новые подходы к решению задач дискретного программирования на основе поиска лексикографического упорядочения векторов, при котором оптимальное решение задачи либо совпадает с лексикографическим экстремумом множества допустимых решений задачи, либо находится достаточно близко от него в лек...
Gespeichert in:
| Datum: | 2016 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/141997 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Новые подходы к решению задач дискретного программирования на основе лексикографического поиска / С.В. Чупов // Кибернетика и системный анализ. — 2016. — Т. 52, № 4. — С. 43-54. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-141997 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1419972018-09-20T01:23:15Z Новые подходы к решению задач дискретного программирования на основе лексикографического поиска Чупов, С.В. Кибернетика Предложены новые подходы к решению задач дискретного программирования на основе поиска лексикографического упорядочения векторов, при котором оптимальное решение задачи либо совпадает с лексикографическим экстремумом множества допустимых решений задачи, либо находится достаточно близко от него в лексикографическом смысле. Описаны обобщенная схема такого лексикографического поиска и возможности для ее модификации. Проиллюстрированы значительные преимущества в эффективности работы данного подхода по сравнению со стандартным алгоритмом лексикографического поиска. Запропоновано нові підходи до розв’язання задач дискретного програмування на основі пошуку лексикографічного впорядкування векторів, при якому оптимальний розв’язок задачі або збігається з лексикографічним екстремумом множини допустимих розв’язків задачі, або знаходиться достатньо близько від нього в лексикографічному сенсі. Описано узагальнену схему такого лексикографічного пошуку та можливості для її модифікації. Проілюстровано значні переваги в ефективності роботи цього підходу в порівнянні з стандартним алгоритмом лексикографічного пошуку. The author proposes new approaches to solving discrete programming problems based on the search for lexicographical ordering of vectors, such that the optimal problem solution either coincides with the lexicographic extremum of the feasible set of problem solutions or is close enough to it in the lexicographic sense. The general scheme of such lexicographic search and the possibilities for its modification are described. Significant advantages in the efficiency of this approach compared with the the standard lexicographic search algorithm are illustrated. 2016 Article Новые подходы к решению задач дискретного программирования на основе лексикографического поиска / С.В. Чупов // Кибернетика и системный анализ. — 2016. — Т. 52, № 4. — С. 43-54. — Бібліогр.: 7 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/141997 519.854 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Чупов, С.В. Новые подходы к решению задач дискретного программирования на основе лексикографического поиска Кибернетика и системный анализ |
| description |
Предложены новые подходы к решению задач дискретного программирования на основе поиска лексикографического упорядочения векторов, при котором оптимальное решение задачи либо совпадает с лексикографическим экстремумом множества допустимых решений задачи, либо находится достаточно близко от него в лексикографическом смысле. Описаны обобщенная схема такого лексикографического поиска и возможности для ее модификации. Проиллюстрированы значительные преимущества в эффективности работы данного подхода по сравнению со стандартным алгоритмом лексикографического поиска. |
| format |
Article |
| author |
Чупов, С.В. |
| author_facet |
Чупов, С.В. |
| author_sort |
Чупов, С.В. |
| title |
Новые подходы к решению задач дискретного программирования на основе лексикографического поиска |
| title_short |
Новые подходы к решению задач дискретного программирования на основе лексикографического поиска |
| title_full |
Новые подходы к решению задач дискретного программирования на основе лексикографического поиска |
| title_fullStr |
Новые подходы к решению задач дискретного программирования на основе лексикографического поиска |
| title_full_unstemmed |
Новые подходы к решению задач дискретного программирования на основе лексикографического поиска |
| title_sort |
новые подходы к решению задач дискретного программирования на основе лексикографического поиска |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2016 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/141997 |
| citation_txt |
Новые подходы к решению задач дискретного программирования на основе лексикографического поиска / С.В. Чупов // Кибернетика и системный анализ. — 2016. — Т. 52, № 4. — С. 43-54. — Бібліогр.: 7 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT čupovsv novyepodhodykrešeniûzadačdiskretnogoprogrammirovaniânaosnoveleksikografičeskogopoiska |
| first_indexed |
2025-07-10T13:55:27Z |
| last_indexed |
2025-07-10T13:55:27Z |
| _version_ |
1837268448989675520 |
| fulltext |
ÓÄÊ 519.854
Ñ.Â. ×ÓÏÎÂ
ÍÎÂÛÅ ÏÎÄÕÎÄÛ Ê ÐÅØÅÍÈÞ ÇÀÄÀ×
ÄÈÑÊÐÅÒÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß ÍÀ ÎÑÍÎÂÅ
ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÎÃÎ ÏÎÈÑÊÀ
Àííîòàöèÿ. Ïðåäëîæåíû íîâûå ïîäõîäû ê ðåøåíèþ çàäà÷ äèñêðåòíîãî ïðî-
ãðàììèðîâàíèÿ íà îñíîâå ïîèñêà ëåêñèêîãðàôè÷åñêîãî óïîðÿäî÷åíèÿ âåêòî-
ðîâ, ïðè êîòîðîì îïòèìàëüíîå ðåøåíèå çàäà÷è ëèáî ñîâïàäàåò ñ ëåêñèêîãðà-
ôè÷åñêèì ýêñòðåìóìîì ìíîæåñòâà äîïóñòèìûõ ðåøåíèé çàäà÷è, ëèáî íàõî-
äèòñÿ äîñòàòî÷íî áëèçêî îò íåãî â ëåêñèêîãðàôè÷åñêîì ñìûñëå. Îïèñàíû
îáîáùåííàÿ ñõåìà òàêîãî ëåêñèêîãðàôè÷åñêîãî ïîèñêà è âîçìîæíîñòè äëÿ åå
ìîäèôèêàöèè. Ïðîèëëþñòðèðîâàíû çíà÷èòåëüíûå ïðåèìóùåñòâà â ýôôåêòèâ-
íîñòè ðàáîòû äàííîãî ïîäõîäà ïî ñðàâíåíèþ ñî ñòàíäàðòíûì àëãîðèòìîì
ëåêñèêîãðàôè÷åñêîãî ïîèñêà.
Êëþ÷åâûå ñëîâà: ëåêñèêîãðàôè÷åñêèé ïîðÿäîê, ëåêñèêîãðàôè÷åñêèé ìàê-
ñèìóì, çàäà÷à äèñêðåòíîãî ïðîãðàììèðîâàíèÿ, àëãîðèòì ëåêñèêîãðàôè÷åñ-
êîãî ïîèñêà.
ÂÂÅÄÅÍÈÅ
Ïðàêòè÷åñêèå çàäà÷è îïòèìèçàöèè òðåáóþò ýôôåêòèâíûõ àëãîðèòìîâ äëÿ îòûñêà-
íèÿ èõ ðåøåíèé. Â ñîâðåìåííûõ óñëîâèÿõ â ñâÿçè ñ áûñòðûì ðàçâèòèåì ñðåäñòâ
âû÷èñëèòåëüíîé òåõíèêè è ðàçíîîáðàçíûõ òåõíîëîãèé, â ÷àñòíîñòè òåõíîëîãèè
ïàðàëëåëüíûõ âû÷èñëåíèé, âîçíèêàåò íåîáõîäèìîñòü â ðàçðàáîòêå íîâûõ àëãîðèò-
ìîâ è ìåòîäîâ, ïîçâîëÿþùèõ çà ïðèåìëåìîå âðåìÿ ïîëó÷àòü îïòèìàëüíûå èëè
áëèçêèå ê íèì ðåøåíèÿ. Ýòî îñîáåííî àêòóàëüíî âñëåäñòâèå çíà÷èòåëüíîãî ðîñòà
ðàçìåðíîñòè ðåàëüíûõ ïðèêëàäíûõ çàäà÷. Â äàííîé ðàáîòå òàêèå ìåòîäû è àëãî-
ðèòìû èñïîëüçóþòñÿ â öåëÿõ ïîâûøåíèÿ ýôôåêòèâíîñòè àëãîðèòìà ëåêñèêîãðà-
ôè÷åñêîãî ïîèñêà ðåøåíèÿ äèñêðåòíûõ çàäà÷ îïòèìèçàöèè [1, 2].
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È. ÎÑÍÎÂÍÛÅ ÎÏÐÅÄÅËÅÍÈß
Ðàññìîòðèì çàäà÷ó äèñêðåòíîãî ïðîãðàììèðîâàíèÿ: ìàêñèìèçèðîâàòü
x f x0 0� ( ) (1)
ïðè óñëîâèÿõ
f x b( ) � , (2)
x D� , (3)
ãäå f R Rn m: � , b R m� , D D D Dn� � � �1 2 � — äèñêðåòíîå ìíîæåñòâî,
D Rj j j� �[ , ]� � , j n�1 2, , ,� , — äèñêðåòíûå ìíîæåñòâà. Åñëè f x0 ( ) è âåê-
òîðíàÿ ôóíêöèÿ f x( ) ëèíåéíû, à êàæäîå èç ìíîæåñòâ D j , j n�1 2, , ,� , — ïîä-
ìíîæåñòâî öåëûõ ÷èñåë, òî çàäà÷à (1)–(3) ÿâëÿåòñÿ çàäà÷åé öåëî÷èñëåííîãî ëè-
íåéíîãî ïðîãðàììèðîâàíèÿ. Ìíîæåñòâî ðåøåíèé, óäîâëåòâîðÿþùèõ óñëîâèÿì
(2), (3), îáîçíà÷èì X D . Ïîëàãàåì, ÷òî êàæäàÿ ïåðåìåííàÿ çàäà÷è îãðàíè÷åíà êàê
ñíèçó, òàê è ñâåðõó, ò.å. ìíîæåñòâî X D îãðàíè÷åíî. Îïðåäåëèì ëåêñèêîãðàôè-
÷åñêîå óïîðÿäî÷åíèå âåêòîðîâ ñëåäóþùèì îáðàçîì: âåêòîð x R n� ëåêñèêîãðà-
ôè÷åñêè ïîëîæèòåëüíûé, x L� 0 (�L — çíàê îòíîøåíèÿ «ëåêñèêîãðàôè÷åñêè
áîëüøå»), åñëè ïåðâàÿ ïî ïîðÿäêó îòëè÷íàÿ îò íóëÿ êîîðäèíàòà ýòîãî âåêòîðà
ïîëîæèòåëüíà; âåêòîð x R n� ëåêñèêîãðàôè÷åñêè áîëüøå âåêòîðà y R n� , x yL� ,
åñëè âåêòîð ( )x y ëåêñèêîãðàôè÷åñêè ïîëîæèòåëüíûé, x y L � 0. Ðàâåíñòâî âåê-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 43
© Ñ.Â. ×óïîâ, 2016
òîðîâ îïðåäåëÿåòñÿ ñòàíäàðòíûì îáðàçîì. Ïðè òàêîì óïîðÿäî÷åíèè ëþáûå
äâà âåêòîðà îäíîé ðàçìåðíîñòè ñðàâíèìû ìåæäó ñîáîé. Íà îñíîâå ëåêñèêîãðà-
ôè÷åñêîãî óïîðÿäî÷åíèÿ âåêòîðîâ ôîðìóëèðóåòñÿ ïîíÿòèå ëåêñèêîãðàôè÷åñêî-
ãî ìàêñèìóìà ìíîæåñòâà. Ðåøåíèå x L èç íåêîòîðîãî ìíîæåñòâà G R n� íàçû-
âàåòñÿ ëåêñèêîãðàôè÷åñêèì ìàêñèìóìîì ýòîãî ìíîæåñòâà, x GL L� max , åñëè
ëþáîå ðåøåíèå èç ìíîæåñòâà G ëåêñèêîãðàôè÷åñêè íå áîëüøå x L, ò.å. äëÿ
êàæäîãî äîïóñòèìîãî âåêòîðà x èç ìíîæåñòâà G âûïîëíÿåòñÿ óñëîâèå x xL L�
(� L — çíàê îòíîøåíèÿ «ëåêñèêîãðàôè÷åñêè íå áîëüøå»). Àíàëîãè÷íî ââîäèò-
ñÿ ïîíÿòèå ëåêñèêîãðàôè÷åñêîãî ìèíèìóìà ìíîæåñòâà.
Ðàññìîòðèì ìíîæåñòâî
{( , ) | , ( ) }x x R x X f x xn D
0
1
0 0 0� �
� . (4)
Òåîðåìà 1. Ëåêñèêîãðàôè÷åñêèé ìàêñèìóì ( , )x x0
� � ìíîæåñòâà (4) îïðåäå-
ëÿåò âåêòîð x� — îïòèìàëüíîå ðåøåíèå çàäà÷è (1)–(3).
Äîêàçàòåëüñòâî. Ðàññìîòðèì çàäà÷ó îïòèìèçàöèè: ìàêñèìèçèðîâàòü
z x� 0 (5)
ïðè óñëîâèÿõ
f x x0 0 0( )
, (6)
x X D� . (7)
Íåòðóäíî âèäåòü, ÷òî çàäà÷è (1)–(3) è (5)–(7) ýêâèâàëåíòíû. Ïóñòü ( , )x x0
� � —
ëåêñèêîãðàôè÷åñêèé ìàêñèìóì ìíîæåñòâà (4). Òîãäà ïðîèçâîëüíîå ðåøåíèå
( , )x x0 , êîòîðîå ïðèíàäëåæèò ìíîæåñòâó (4), ëåêñèêîãðàôè÷åñêè íå áîëüøå ðå-
øåíèÿ ( , )x x0
� � , ïîýòîìó x x0 0
�
. Ïîñêîëüêó çíà÷åíèå x0 â çàäà÷å (5)–(7) ìàêñè-
ìèçèðóåòñÿ, òî÷êà ( , )x x0
� � — îïòèìàëüíîå ðåøåíèå çàäà÷è (5)–(7). Âñëåäñòâèå
òîãî, ÷òî çàäà÷è (1)–(3) è (5)–(7) ýêâèâàëåíòíû, âåêòîð x� — îïòèìàëüíîå ðåøå-
íèå çàäà÷è (1)–(3).
ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÉ ÀËÃÎÐÈÒÌ ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÎÃÎ ÏÎÈÑÊÀ
Èñïîëüçóÿ ïîíÿòèå ëåêñèêîãðàôè÷åñêîãî ìàêñèìóìà ìíîæåñòâà è òåîðåìó 1,
ïðîöåññ íàõîæäåíèÿ îïòèìàëüíîãî ðåøåíèÿ çàäà÷è (1)–(3) ìîæíî ñâåñòè
ê îòûñêàíèþ ëåêñèêîãðàôè÷åñêèõ ìàêñèìóìîâ ïîñëåäîâàòåëüíîñòè ìíîæåñòâ
X 0, X X k1, ... , , ... , ãäå X X D0 � , X x X x x f x xk D L k k� � �
� { | , ( ) }1
0 0
1 1 ,
k �1 2, ,� , x Xk L k� max , x f xk k
0 0� ( ), k � 0 1, ,� Íà òàêîì îïðåäåëåíèè ìíî-
æåñòâ áàçèðóåòñÿ àëãîðèòì ïîñëåäîâàòåëüíîãî ëåêñèêîãðàôè÷åñêîãî ïîèñêà
ðåøåíèÿ çàäà÷è (1)–(3) [2, 7]. Åñëè X 0
�, òî â ðåçóëüòàòå ðåàëèçàöèè îïè-
ñàííîé ñõåìû ïîñëåäîâàòåëüíîãî ëåêñèêîãðàôè÷åñêîãî ïîèñêà ñòðîèòñÿ ëåê-
ñèêîãðàôè÷åñêè óáûâàþùàÿ ïîñëåäîâàòåëüíîñòü äîïóñòèìûõ ðåøåíèé
x x xL L L k L0 1� � � �� � , (8)
êîòîðîé ñîîòâåòñòâóåò âîçðàñòàþùàÿ ïîñëåäîâàòåëüíîñòü x x x k
0
0
0
1
0
� � � �� �
çíà÷åíèé öåëåâîé ôóíêöèè (1). Ïðîöåññ ðåøåíèÿ çàäà÷è çàêàí÷èâàåòñÿ, êàê
òîëüêî íà íåêîòîðîì øàãå k k�
1 0( ) ïîëó÷èì X k� ��1 . Ýòî óñëîâèå ôàê-
òè÷åñêè îçíà÷àåò, ÷òî ñðåäè äîïóñòèìûõ ðåøåíèé, ëåêñèêîãðàôè÷åñêè ìåíü-
øèõ x k , íå ñóùåñòâóåò ëó÷øèõ ïî çíà÷åíèþ öåëåâîé ôóíêöèè. Ïîñêîëüêó
êàæäàÿ òî÷êà x i ki, , , ,�{ }0 1 � , ÿâëÿåòñÿ ëåêñèêîãðàôè÷åñêèì ìàêñèìóìîì ñîîò-
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
âåòñòâóþùåãî ìíîæåñòâà X i , âåêòîð x k áóäåò ðåøåíèåì çàäà÷è (1)–(3). Êîíå÷-
íîñòü ïîèñêà îáåñïå÷èâàåòñÿ îãðàíè÷åííîñòüþ äîïóñòèìîãî ìíîæåñòâà X D .
Îïèñàííûé àëãîðèòì ëåêñèêîãðàôè÷åñêîãî ïîèñêà äîñòàòî÷íî ïðîñò, åñëè èìååòñÿ
âîçìîæíîñòü áûñòðî îïðåäåëèòü ëåêñèêîãðàôè÷åñêèé ìàêñèìóì ìíîæåñòâà X D
èëè íåêîòîðîãî åãî ïîäìíîæåñòâà {x X x xD L� �| }. Îäíàêî ïðè îòûñêàíèè
îòäåëüíûõ äîïóñòèìûõ ðåøåíèé ïîñëåäîâàòåëüíîñòè (8) ïðîöåññ ïîèñêà ìî-
æåò çàíèìàòü äëèòåëüíîå âðåìÿ. Êàæäîå äîïóñòèìîå ðåøåíèå x kk,
1, îïðå-
äåëÿåòñÿ â ðåçóëüòàòå ïîñòðîåíèÿ ëåêñèêîãðàôè÷åñêè óáûâàþùåé ïîñëåäîâà-
òåëüíîñòè òî÷åê
x y z y z yk L L L L r L r L � � � � � � �1 0 1 1
� � , (9)
ãäå z x D x y f x xr L L r k� � � � max | , ( ) }{ 1
0 0
1 , y x X x zr L D L r� � �max | }{ .
Î÷åâèäíî, x zk r� , åñëè z Xr D� , è x yk r� , åñëè f y xr k
0 0
1( ) � . Â ïðîöåññå
ïîñòðîåíèÿ òàêîé ïîñëåäîâàòåëüíîñòè ãàðàíòèðóåòñÿ, ÷òî êàæäàÿ òî÷êà
ïðîñìàòðèâàåòñÿ òîëüêî îäèí ðàç è íå áóäåò ïðîïóùåíî íè îäíîãî ïîäõîäÿùå-
ãî ðåøåíèÿ. Òàêèì îáðàçîì, îïòèìàëüíîå ðåøåíèå òàêæå íå áóäåò ïðîïóùåíî.
Îïèñàííûé àëãîðèòì ëåêñèêîãðàôè÷åñêîãî ïîèñêà ðåøåíèÿ çàäà÷è (1)–(3) è ñî-
îòâåòñòâóþùèé ìåòîä íàçîâåì äåòåðìèíèðîâàííûìè [6]. Äàëåå ïîä ïîäõîäÿ-
ùèì ðåøåíèåì áóäåì ïîíèìàòü äîïóñòèìîå ðåøåíèå, äëÿ êîòîðîãî çíà÷åíèå
öåëåâîé ôóíêöèè íå ìåíüøå (äëÿ çàäà÷è ìàêñèìèçàöèè) èëè íå áîëüøå (äëÿ
çàäà÷è ìèíèìèçàöèè) óæå äîñòèãíóòîãî ðåêîðäíîãî çíà÷åíèÿ.
ÀÍÀËÈÇ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÎÃÎ ÀËÃÎÐÈÒÌÀ
Ýôôåêòèâíîñòü äåòåðìèíèðîâàííîãî àëãîðèòìà ñóùåñòâåííî çàâèñèò îò êîëè-
÷åñòâà òî÷åê â ïîñëåäîâàòåëüíîñòè (9). Êàê ïðàâèëî, èõ ÷èñëî çíà÷èòåëüíî âîç-
ðàñòàåò ñ óâåëè÷åíèåì íîìåðà øàãà k , ÷òî ñíèæàåò ýôôåêòèâíîñòü ïîèñêà. Ýòî
îñîáåííî çàìåòíî ïðè ðåøåíèè çàäà÷, ÷èñëî ïåðåìåííûõ â êîòîðûõ áîëüøå 80.
 êà÷åñòâå èëëþñòðàöèè ïðîäåìîíñòðèðóåì ðåçóëüòàòû ðåøåíèÿ òåñòîâûõ çà-
äà÷ î ìíîãîìåðíîì ðàíöå ñ áóëåâûìè ïåðåìåííûìè ñòàíäàðòíûì äåòåðìèíèðî-
âàííûì àëãîðèòìîì ëåêñèêîãðàôè÷åñêîãî ïîèñêà ïðè ðàçëè÷íûõ çíà÷åíèÿõ êîëè-
÷åñòâà ïåðåìåííûõ è ðàçíûõ ñòðóêòóðàõ ìàòðèöû îãðàíè÷åíèé çàäà÷è. Íà ðèñ. 1
èçîáðàæåíû òðè êðèâûå, ñîîòâåòñòâóþùèå ðàçíûì ñòðóêòóðàì ìàòðèöû îãðàíè÷å-
íèé çàäà÷è. Êðèâàÿ 1 ñîîòâåòñòâóåò ñòðóêòóðå ìàòðèöû îãðàíè÷åíèé, äëÿ êîòîðîé
äîëÿ åäèíè÷íûõ çíà÷åíèé â îïòèìàëüíîì ðåøåíèè ñîñòàâëÿåò îêîëî 25 % îáùåãî
÷èñëà ïåðåìåííûõ, êðèâàÿ 2 — 50 % , êðèâàÿ 3 — 75 %. Ïðîöåíòíîå îòíîøåíèå
êîëè÷åñòâà íåíóëåâûõ çíà÷åíèé â
ðåøåíèè ê îáùåìó ÷èñëó ïåðåìåí-
íûõ íàçîâåì ïëîòíîñòüþ çíà÷åíèé
ðåøåíèÿ. Ïîñëåäîâàòåëüíî ðåøà-
ëèñü ñåðèè ïî ïÿòü çàäà÷ ñ êîëè-
÷åñòâîì îãðàíè÷åíèé, ðàâíûì 20,
è êîëè÷åñòâîì ïåðåìåííûõ 20, 25,
30, 35, 40, 45, 50, 55, 60. Ïîñëå ðå-
øåíèÿ îòäåëüíîé ñåðèè ïîäñ÷èòû-
âàëîñü ñðåäíåå âðåìÿ åãî ïîëó÷å-
íèÿ. Îòìåòèì, ÷òî âðåìÿ ðåøåíèÿ
çàäà÷è — ýòî âðåìÿ, çàòðà÷åííîå
íà àíàëèç è ïîëó÷åíèå âñåõ äîïóñ-
òèìûõ ðåøåíèé x kk,
0, ïîñëåäî-
âàòåëüíîñòè (8).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 45
0
2
4
6
8
10
12
14
16
18
20 25 30 35 40 45 50 55 60
n
t �10
3
, c
1
2
3
Ðèñ. 1. Ãðàôèêè çàâèñèìîñòè ðàçìåðíîñòè îò âðåìåíè
ðåøåíèÿ çàäà÷è (1 — 25 %, 2 — 50 %, 3 — 75 %)
Àíàëèçèðóÿ ïðåäñòàâëåííûå ðåçóëüòàòû, ìîæíî ñäåëàòü âûâîä, ÷òî, âî-ïåð-
âûõ, ýôôåêòèâíîñòü ðàáîòû äåòåðìèíèðîâàííîãî àëãîðèòìà ëåêñèêîãðàôè÷åñêîãî
ïîèñêà â çíà÷èòåëüíîé ñòåïåíè çàâèñèò îò ñòðóêòóðû ìàòðèöû îãðàíè÷åíèé çàäà÷è.
Ëåãêî âèäåòü, ÷òî ÷åì áîëüøå äîïóñòèìûõ ðåøåíèé ñîäåðæèò ìíîæåñòâî X D , òåì
áîëüøå íóæíî âðåìåíè íà èõ àíàëèç. Ïðè ïëîòíîñòè çíà÷åíèé 75 % îáùåå ÷èñëî
äîïóñòèìûõ ïåðåñìàòðèâàåìûõ ðåøåíèé ñóùåñòâåííî ìåíüøå, ÷åì ñîîòâåòñòâóþ-
ùåå ÷èñëî ïðè ïëîòíîñòè 50 %, à ïðè ïëîòíîñòè 25 % îíî ëèøü â íåñêîëüêî ðàç
áîëüøå, ÷åì ïðè ïëîòíîñòè 75 %, è çíà÷èòåëüíî ìåíüøå, ÷åì ñîîòâåòñòâóþùåå êî-
ëè÷åñòâî ïðè ïëîòíîñòè 50 %. Âî-âòîðûõ, ïðè óâåëè÷åíèè ðàçìåðíîñòè çàäà÷è,
â ÷àñòíîñòè ÷èñëà ïåðåìåííûõ, ñ îïðåäåëåííîãî ìîìåíòà «ýêñïîíåíöèàëüíî» âîç-
ðàñòàåò âðåìÿ ïîëó÷åíèÿ ðåøåíèÿ. Èç ïðèâåäåííûõ ðåçóëüòàòîâ âèäíî, ÷òî ïðè íå-
áîëüøîì ÷èñëå ïåðåìåííûõ ( )n� 50 è ñîîòâåòñòâóþùåé ñòðóêòóðå îãðàíè÷åíèé
(ïëîòíîñòü â ïðåäåëàõ (0 %, 20 %] è [70 %, 100 %)) äåòåðìèíèðîâàííûé àëãîðèòì
ëåêñèêîãðàôè÷åñêîãî ïîèñêà äîñòàòî÷íî ýôôåêòèâåí. Ñîâðåìåííûå ïðàêòè÷åñêèå
çàäà÷è âêëþ÷àþò ñîòíè è òûñÿ÷è ïåðåìåííûõ, ïîýòîìó ÿâíîå èñïîëüçîâàíèå äåòåð-
ìèíèðîâàííîãî àëãîðèòìà äëÿ çàäà÷ áîëüøîé ðàçìåðíîñòè ìàëîýôôåêòèâíî. Òðåáó-
åòñÿ ìîäèôèêàöèÿ äåòåðìèíèðîâàííûõ ñõåì ëåêñèêîãðàôè÷åñêîãî ïîèñêà, ÷òîáû çà
ïðèåìëåìîå âðåìÿ ïîëó÷àòü ïîäõîäÿùèå ðåçóëüòàòû.
ÏÎÈÑÊ Â ÐÀÇËÈ×ÍÛÕ ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÈÕ ÏÎÐßÄÊÀÕ
Ðàññìîòðèì íåêîòîðûå âîçìîæíîñòè, ïîçâîëÿþùèå ïîâûñèòü ýôôåêòèâíîñòü ïðî-
öåññà ïîèñêà îïòèìàëüíîãî ðåøåíèÿ, îñíîâàííîãî íà ëåêñèêîãðàôè÷åñêîì óïîðÿ-
äî÷åíèè âåêòîðîâ. Îòìåòèì, ÷òî ëåêñèêîãðàôè÷åñêîå óïîðÿäî÷åíèå êàê ïîëíûé
ïîðÿäîê îïðåäåëÿåò îäíîçíà÷íîå íàïðàâëåíèå äâèæåíèÿ (äâèæåíèå â ïîðÿäêå
ëåêñèêîãðàôè÷åñêîãî óáûâàíèÿ ðåøåíèé, íàïðèìåð ïðè ïîñòðîåíèè ëåêñèêîãðà-
ôè÷åñêè óáûâàþùåé ïîñëåäîâàòåëüíîñòè ðåøåíèé (8), èëè äâèæåíèå â ïîðÿäêå
ëåêñèêîãðàôè÷åñêîãî âîçðàñòàíèÿ), â ðåçóëüòàòå êîòîðîãî ìîæíî äîñòè÷ü ðåøå-
íèÿ çàäà÷è (1)–(3). Âûáèðàÿ ðàçëè÷íûå ëåêñèêîãðàôè÷åñêèå ïîðÿäêè, ïîëó÷àåì
ðàçíûå íà÷àëüíûå òî÷êè, íà÷èíàÿ ñ êîòîðûõ ìîæíî îñóùåñòâèòü äâèæåíèå
ê îïòèìàëüíîìó ðåøåíèþ. Êàæäàÿ òàêàÿ òî÷êà ÿâëÿåòñÿ ëåêñèêîãðàôè÷åñêèì
ìàêñèìóìîì ìíîæåñòâà X D â âûáðàííîì ëåêñèêîãðàôè÷åñêîì ïîðÿäêå. Î÷åâèä-
íî, ÷òî ÷åì ëåêñèêîãðàôè÷åñêè áëèæå ïî îòíîøåíèþ ê îïòèìàëüíîìó ðåøåíèþ
ðàñïîëîæåíà íà÷àëüíàÿ òî÷êà, òåì áûñòðåå áóäåò ïîëó÷åíî ðåøåíèå çàäà÷è. Ïðåä-
ïîëîæèì, ÷òî âûáðàíî ÷åòûðå ðàçíûõ ëåêñèêîãðàôè÷åñêèõ ïîðÿäêà: order1, order2 ,
order3 , order4 è x X
order
L D1
1
� max , x X
order
L D2
2
� max , x X
order
L D3
3
� max ,
x X
order
L D4
4
� max — ñîîòâåòñòâóþùèå ëåêñèêîãðàôè÷åñêèå ìàêñèìóìû ìíî-
æåñòâà X D â íèõ, x * — îïòèìàëüíîå ðåøåíèå. Ïóñòü ïî îòíîøåíèþ ê x� ðå-
øåíèÿ x1, x 2 , x 3 , x 4 ñõåìàòè÷åñêè ðàçìåùåíû òàê, êàê ïîêàçàíî íà ðèñ. 2.
Øòðèõîâûìè ëèíèÿìè ïîêàçàíû íàïðàâëåíèÿ ëåêñèêîãðàôè÷åñêîãî óáûâàíèÿ
äëÿ êàæäîãî ïîðÿäêà. Íåòðóäíî çàìåòèòü, ÷òî â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå
order4 ðåøåíèå x 4 íàõîäèòñÿ áëèæå âñåãî ê x� ïî ñðàâíåíèþ ñ äðóãèìè ðåøå-
íèÿìè â ñîîòâåòñòâóþùèõ ëåêñèêîãðàôè÷åñêèõ ïîðÿäêàõ, ò.å. ( )*x x order
4
4
�
� �min ( ) , , , ,*L i
orderx x i
i
{ }1 2 3 4 . Òàêèì îáðàçîì, ýòî ðåøåíèå ñëåäóåò âûáðàòü
â êà÷åñòâå íà÷àëüíîé òî÷êè äëÿ àëãîðèòìà ëåêñèêîãðàôè÷åñêîãî ïîèñêà, êîòîðûé
áóäåò ïðîâîäèòüñÿ â ïîðÿäêå order4 .
Íà ðèñ 3. ïðèâåäåíû ãðàôèêè äâóõ ïðîöåññîâ ïîëó÷åíèÿ îïòèìàëüíîãî ðå-
øåíèÿ äëÿ îäíîé êîíêðåòíîé çàäà÷è î ìíîãîìåðíîì ðàíöå ñ áóëåâûìè ïåðåìåí-
íûìè, îñóùåñòâëåííûõ â äâóõ ðàçíûõ ëåêñèêîãðàôè÷åñêèõ ïîðÿäêàõ. Ïðè ýòîì
îïòèìàëüíîå ðåøåíèå â ïîðÿäêå order1 ïîëó÷åíî çà 0.002 ñ, äëÿ àíàëèçà âñåõ ïîä-
õîäÿùèõ ðåøåíèé ïîòðåáîâàëîñü 11.610 ñ; â ïîðÿäêå order2 îïòèìàëüíîå ðåøå-
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
íèå ïîëó÷åíî çà 93.693 ñ, àíà-
ëèç âñåõ ïîäõîäÿùèõ ðåøåíèé
çàíÿë 583.990 ñ. Ðàçíèöà â ýô-
ôåêòèâíîñòè î÷åâèäíà.
Îäíîé èç âîçìîæíîñòåé,
ïîçâîëÿùåé çíà÷èòåëüíî ïîâû-
ñèòü ýôôåêòèâíîñòü àëãîðèòìà
ëåêñèêîãðàôè÷åñêîãî ïîèñêà,
ÿâëÿåòñÿ óäà÷íûé âûáîð ëåêñè-
êîãðàôè÷åñêîãî ïîðÿäêà, â êî-
òîðîì áóäåò îñóùåñòâëÿòüñÿ
äâèæåíèå ê îïòèìàëüíîìó ðå-
øåíèþ. Åãî äåëàþò îäèí ðàç
â íà÷àëå àëãîðèòìà èëè ïîñòå-
ïåííî óòî÷íÿþò ëåêñèêîãðàôè-
÷åñêèé ïîðÿäîê â ïðîöåññå ïî-
èñêà ðåøåíèÿ çàäà÷è. Ýòî îäèí
èç âîçìîæíûõ ïóòåé ïîñòðîåíèÿ
ðàçëè÷íûõ ýôôåêòèâíûõ ìåòî-
äîâ ëåêñèêîãðàôè÷åñêîãî ïîèñ-
êà. Îí òðåáóåò îòäåëüíîãî èñ-
ñëåäîâàíèÿ. Âàæíûì ÿâëÿåòñÿ
òàêæå âîïðîñ îöåíêè áëèçîñòè
èìåþùåãîñÿ ëåêñèêîãðàôè÷åñ-
êîãî ìàêñèìóìà, ïîëó÷åííîãî
â äàííîì ëåêñèêîãðàôè÷åñêîì
ïîðÿäêå, ïî îòíîøåíèþ ê îïòè-
ìàëüíîìó ðåøåíèþ â ýòîì æå
ïîðÿäêå, êîòîðîå íåèçâåñòíî. Îò êîððåêòíîé îöåíêè çàâèñèò ýôôåêòèâíîñòü ìåòîäà
ïîèñêà, îñíîâàííîãî íà ëåêñèêîãðàôè÷åñêîì óïîðÿäî÷åíèè.
ÂÛÁÎÐ ÍÀÏÐÀÂËÅÍÈß ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÎÃÎ ÄÂÈÆÅÍÈß
Äîïîëíèòåëüíîãî èññëåäîâàíèÿ òðåáóþò âîïðîñû, êàêèì îáðàçîì îñóùåñòâëÿòü
ïîèñê â íîâîì ëåêñèêîãðàôè÷åñêîì ïîðÿäêå ïî ñðàâíåíèþ ñ ïðåäûäóùèìè è
êàêèì äîëæíî áûòü åãî íàïðàâëåíèå: äâèæåíèå â ïîðÿäêå ëåêñèêîãðàôè÷åñêî-
ãî óáûâàíèÿ èëè âîçðàñòàíèÿ. Ïðè ýòîì æåëàòåëüíî íå ïåðåñìàòðèâàòü ðåøå-
íèÿ, ïåðåñìîòðåííûå ïðè èñïîëüçîâàíèè ïðåäûäóùèõ ïîðÿäêîâ, ïðè÷åì äâè-
æåíèå ñëåäóåò îñóùåñòâëÿòü â ëåêñèêîãðàôè÷åñêîì íàïðàâëåíèè íàõîæäåíèÿ
îïòèìàëüíîãî ðåøåíèÿ. Åñëè çà íà÷àëüíóþ òî÷êó äâèæåíèÿ â íîâîì ëåêñèêî-
ãðàôè÷åñêîì ïîðÿäêå âûáðàòü ïîñëåäíþþ ïîäõîäÿùóþ òî÷êó, ïîëó÷åííóþ
â ðåçóëüòàòå ïîèñêà â ïðåäûäóùåì ïîðÿäêå, òî âîçíèêàåò íåêîòîðàÿ íåîïðåäå-
ëåííîñòü, ïîñêîëüêó íå èçâåñòíî, ñ êàêîé ñòîðîíû ðàñïîëîæåíà îïòèìàëüíàÿ
òî÷êà ïî îòíîøåíèþ ê òåêóùåé â íîâîì ëåêñèêîãðàôè÷åñêîì ïîðÿäêå: îíà
ìîæåò áûòü ëåêñèêîãðàôè÷åñêè ìåíüøå èëè áîëüøå òåêóùåé. Ìîæíî ïàðàë-
ëåëüíî äâèãàòüñÿ â îáîèõ ëåêñèêîãðàôè÷åñêèõ íàïðàâëåíèÿõ, íî ïðè ýòîì íà
ïîñëåäóþùèõ øàãàõ êîëè÷åñòâî îäíîâðåìåííûõ ïîèñêîâ â ðàçíûõ íàïðàâëå-
íèÿõ ìîæåò çíà÷èòåëüíî âîçðàñòè è â ðåçóëüòàòå ñóùåñòâåííî óõóäøèòü îá-
ùóþ ýôôåêòèâíîñòü ïîèñêà. Åñëè ïî îïðåäåëåííûì ïðàâèëàì âûáðàòü òîëüêî
îäíî èç íàïðàâëåíèé äâèæåíèÿ, òî âîçíèêàåò âåðîÿòíîñòü äâèæåíèÿ â ëîæíîì
íàïðàâëåíèè, ÷òî, âîçìîæíî, ñäåëàåò ïîèñê áåñïåðñïåêòèâíûì. Ïðèìåð òàêîé
ñèòóàöèè èëëþñòðèðóåòñÿ íà ðèñ. 4. Ïóñòü â ïðîöåññå ðàáîòû àëãîðèòìà ëåê-
ñèêîãðàôè÷åñêîãî ïîèñêà èñïîëüçóåòñÿ òðè ëåêñèêîãðàôè÷åñêèõ ïîðÿäêà:
order1, order2 , order3 è x
order1
0 , x
order2
0 , x
order3
0 — ñîîòâåòñòâóþùèå ëåêñèêîãðà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 47
x
1
x
4
x
3
x
2
X
D
order1
order3
order4
order2
x*
Ðèñ. 2. Ñõåìà ðàçìåùåíèÿ íà÷àëüíûõ òî÷åê â ðàçíûõ
ïîðÿäêàõ
15
20
25
30
0 20 40 60 80 100
t, ñ
f0 (x) �10
3
2
1
Ðèñ. 3. Ãðàôèêè ïîëó÷åíèÿ îïòèìàëüíîãî ðåøåíèÿ â ðàç-
íûõ ïîðÿäêàõ (1 — order1, 2 — order2)
ôè÷åñêèå ìàêñèìóìû ìíîæåñòâà X D â ýòèõ ïîðÿäêàõ. Ïîèñê íà÷èíàåòñÿ ñ ðå-
øåíèÿ x
order1
0 , äâèæåíèå îñóùåñòâëÿåòñÿ â íàïðàâëåíèè ëåêñèêîãðàôè÷åñêîãî
óáûâàíèÿ â òåêóùåì ïîðÿäêå è îïðåäåëÿåòñÿ ëó÷øåå ðåøåíèå x
order1
1
( ( ) ( ))f x f x
order order0
1
0
0
1 1
� . Ïåðåõîäèì ê ïîèñêó â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå
order2 . Ïðåîáðàçóåì ðåøåíèå x
order1
1 â x
order2
1 , ïðè ýòîì f x
order0
1
1
( ) �
� f x
order0
1
2
( ) . Îäíàêî âîçíèêàåò âîïðîñ, â êàêîì ëåêñèêîãðàôè÷åñêîì íàïðàâ-
ëåíèè äâèãàòüñÿ. Åñëè äàëüøå äâèãàòüñÿ, êàê íà ïðåäûäóùåì øàãå, òî ïîïàäåì
íà áåñïåðñïåêòèâíîå íàïðàâëåíèå, ïîñêîëüêó îïòèìàëüíîå ðåøåíèå â ïîðÿäêå
order2 ëåêñèêîãðàôè÷åñêè áîëüøå, ÷åì x
order2
1 , à äâèæåíèå îñóùåñòâëÿåòñÿ â íà-
ïðàâëåíèè ëåêñèêîãðàôè÷åñêîãî óáûâàíèÿ. Åñëè äâèãàòüñÿ â íàïðàâëåíèè ëåê-
ñèêîãðàôè÷åñêîãî âîçðàñòàíèÿ, òî â ðåçóëüòàòå ïîëó÷èì ëó÷øåå ïî çíà÷åíèþ
öåëåâîé ôóíêöèè ðåøåíèå x
order2
2 . Äàëåå ïåðåõîäèì ê ïîèñêó â ïîðÿäêå order3 ,
ïîëó÷àåì ðåøåíèå x
order3
2 è, äâèãàÿñü â íàïðàâëåíèè ëåêñèêîãðàôè÷åñêîãî
óáûâàíèÿ, ïîëó÷àåì îïòèìàëüíîå ðåøåíèå x� .
×òîáû èçáåæàòü òàêîé íåîïðåäåëåííîñòè, ò.å. ïðè ïðîèçâîëüíîì ëåêñèêîãðà-
ôè÷åñêîì ïîðÿäêå äâèãàòüñÿ âñåãäà â îäíîì íàïðàâëåíèè, ìîæíî â êà÷åñòâå íà-
÷àëüíîé òî÷êè äâèæåíèÿ âûáèðàòü íå ïîñëåäíþþ ïîëó÷åííóþ òî÷êó â ïðåäûäó-
ùåì ïîðÿäêå, à ïîñëåäíþþ äîïóñòèìóþ òî÷êó, ïîëó÷åííóþ â äàííîì ëåêñèêîãðà-
ôè÷åñêîì ïîðÿäêå. Âíà÷àëå, êîãäà äàííûé ëåêñèêîãðàôè÷åñêèé ïîðÿäîê åùå íå
èñïîëüçîâàëñÿ, òàêîé òî÷êîé ìîæåò áûòü ëåêñèêîãðàôè÷åñêèé ìàêñèìóì ìíîæåñò-
âà X D â ýòîì ïîðÿäêå. Íà ïîñëåäóþùèõ øàãàõ, êîãäà â ïðîöåññå ðàáîòû àëãî-
ðèòìà âåðíåìñÿ ê òåêóùåìó ïîðÿäêó, ýòî áóäåò ïîñëåäíÿÿ äîïóñòèìàÿ òî÷êà, ïî-
ëó÷åííàÿ â ðåçóëüòàòå ëåêñèêîãðàôè÷åñêîãî ïîèñêà â äàííîì ïîðÿäêå.
ÈÑÏÎËÜÇÎÂÀÍÈÅ ÏÐßÌÛÕ ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÈÕ ÎÃÐÀÍÈ×ÅÍÈÉ
Î÷åâèäíî, ÷òî ïðè òàêîì ïîäõîäå ìîæíî ïîëó÷èòü ðåøåíèÿ, óæå ïðîàíàëèçè-
ðîâàííûå â ïðåäûäóùèõ ëåêñèêîãðàôè÷åñêèõ ïîðÿäêàõ. Äëÿ òîãî ÷òîáû èçáå-
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
Áåñïåðñïåêòèâíîå íàïðàâëåíèå
Ðèñ. 4. Ñõåìà ïðîöåññà ïîèñêà â ðàçíûõ ëåêñèêîãðàôè÷åñêèõ ïîðÿäêàõ
X D xorder2
0
xorder3
0
xorder3
2
xorder2
2
xorder2
1
xorder1
0
xorder1
1
x�
æàòü ïîäîáíîé ñèòóàöèè, ìîæíî ñ ïîìîùüþ ïðÿìûõ ëåêñèêîãðàôè÷åñêèõ îã-
ðàíè÷åíèé èñêëþ÷àòü èç äàëüíåéøåãî ïðîñìîòðà ðåøåíèÿ, ïðîñìîòðåííûå íà
ïðåäûäóùèõ øàãàõ.  äàëüíåéøåì ëåêñèêîãðàôè÷åñêîå íåðàâåíñòâî x xL� �
( �x xL
, x xL� �, x xL� �) â äàííîì ëåêñèêîãðàôè÷åñêîì ïîðÿäêå, ãäå �x — ôèêñè-
ðîâàííûé âåêòîð, áóäåì íàçûâàòü ïðÿìûì ëåêñèêîãðàôè÷åñêèì îãðàíè÷åíèåì.
×òîáû óòî÷íèòü, â êàêîì èìåííî ëåêñèêîãðàôè÷åñêîì ïîðÿäêå îïðåäåëåíî
äàííîå ëåêñèêîãðàôè÷åñêîå îãðàíè÷åíèå, èñïîëüçóåì çàïèñü x x
order
L
k
� � (èëè
ñîêðàùåííî x x
k
L� �), ãäå orderk — ëåêñèêîãðàôè÷åñêèé ïîðÿäîê, â êîòîðîì
ïðîâîäèòñÿ ñðàâíåíèå âåêòîðîâ. Îáîçíà÷èì w
order
k
k
ïîñëåäíþþ äîïóñòèìóþ
òî÷êó, ïðîñìîòðåííóþ â ïîðÿäêå orderk íà øàãå k � 0 1, ,� Äëÿ òîãî ÷òîáû îò-
áðîñèòü ïðîñìîòðåííûå ðåøåíèÿ, íóæíî â ñòàíäàðòíûé äåòåðìèíèðîâàííûé
àëãîðèòì ëåêñèêîãðàôè÷åñêîãî ïîèñêà âíåñòè îïðåäåëåííûå èçìåíåíèÿ.
À èìåííî, â ñòðóêòóðó ìíîæåñòâà X x X x x f x xk D L k k� � �
� { | , ( ) }1
0 0
1 1 ,
íà êîòîðîì îñóùåñòâëÿåòñÿ ïîèñê ëåêñèêîãðàôè÷åñêîãî ìàêñèìóìà íà òåêó-
ùåì øàãå, äîáàâèòü ãðóïïó ïðÿìûõ ëåêñèêîãðàôè÷åñêèõ îãðàíè÷åíèé, îáåñïå-
÷èâàþùèõ îòñåâ ðåøåíèé, ïðîñìîòðåííûõ íà ïðåäûäóùèõ øàãàõ. Ïðåäïîëî-
æèì, ÷òî ïîèñê ëåêñèêîãðàôè÷åñêîãî ìàêñèìóìà ìíîæåñòâà X k ïðîâîäèòñÿ
â ïîðÿäêå orderk , à order j kj , , , ,� 0 1 1� , — ëåêñèêîãðàôè÷åñêèå ïîðÿäêè,
â êîòîðûõ óæå âûïîëíÿëñÿ ïîèñê. Òàêèì îáðàçîì, ìíîæåñòâî X k îïðåäåëèì
êàê X x X x x x w j k f xk D
k
L k
j
L
order
j
j
� � � � �
{ | , , , , , , ( ) �1
00 1 1� x0 1� }, ãäå
�x0 — äîñòèãíóòîå ðåêîðäíîå çíà÷åíèå öåëåâîé ôóíêöèè çàäà÷è.
ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÈÉ ÏÎÐßÄÎÊ È ÔÓÍÊÖÈÈ ÐÀÑÑÒÎßÍÈß
Âî ìíîãèõ ñîâðåìåííûõ àëãîðèòìàõ ïîèñêà îïòèìàëüíîãî ðåøåíèÿ çàäà÷
îïòèìèçàöèè èñïîëüçóþòñÿ ðàçëè÷íûå ôóíêöèè ðàññòîÿíèÿ d x y( , ) ìåæäó äâó-
ìÿ ðåøåíèÿìè: x è y. Âî-ïåðâûõ, òàêèå ôóíêöèè ïîçâîëÿþò ðàçáèòü íà÷àëü-
íóþ îáëàñòü ïîèñêà íà ìåíüøèå îáëàñòè, êîòîðûå, âîçìîæíî, íå ïåðåñåêàþò-
ñÿ, è ïðîâîäèòü ïîèñê îòäåëüíî â êàæäîé èç íèõ. Âî-âòîðûõ, èñïîëüçîâàíèå
ôóíêöèé ðàññòîÿíèÿ ïîçâîëÿåò íå äîïóñòèòü ïðîâåäåíèÿ ïîèñêà â òåõ îáëàñ-
òÿõ, êîòîðûå ïðè îïðåäåëåííûõ óñëîâèÿõ ñ÷èòàþòñÿ áåñïåðñïåêòèâíûìè èëè
óæå áûëè ïðîñìîòðåíû. Ïðè ýòîì, åñëè òî÷êà x — öåíòð îáëàñòè ðàäèóñà r,
òî òî÷êà y ïðèíàäëåæèò ýòîé îáëàñòè ïðè âûïîëíåíèè óñëîâèÿ d x y r( , ) � .
Ëåêñèêîãðàôè÷åñêèé ïîðÿäîê ïðè íåêîòîðûõ óñëîâèÿõ òàêæå äàåò âîçìîæ-
íîñòü îïðåäåëèòü ôóíêöèþ ðàññòîÿíèÿ. Íàïðèìåð, åñëè âåêòîðû x è y áóëåâû,
òî ðàññòîÿíèå ìåæäó íèìè â äàííîì ëåêñèêîãðàôè÷åñêîì ïîðÿäêå, ãäå êîîð-
äèíàòû îòñîðòèðîâàíû ïî âàæíîñòè â ïîðÿäêå èõ åñòåñòâåííîé íóìåðàöèè,
ìîæíî çàäàòü ôóíêöèåé d x y x yn j
j j
j
n
( , ) ( )�
�
�2
1
. Íî â áîëüøèíñòâå ñëó÷à-
åâ íå îáÿçàòåëüíî çíàòü òî÷íîå çíà÷åíèå ðàññòîÿíèÿ ìåæäó äâóìÿ ðåøåíèÿìè,
äîñòàòî÷íî óñòàíîâèòü, ïðèíàäëåæèò ëè íåêîòîðîå ðåøåíèå îïðåäåëåííîé îá-
ëàñòè èëè íåò. Äëÿ ýòîé öåëè óäîáíî èñïîëüçîâàòü ïðÿìûå ëåêñèêîãðàôè÷åñ-
êèå îãðàíè÷åíèÿ (îäíîñòîðîííèå èëè äâóñòîðîííèå).
ÑÂÎÉÑÒÂÀ ÏÐßÌÛÕ ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÈÕ ÎÃÐÀÍÈ×ÅÍÈÉ
Îïðåäåëèì íåêîòîðûå ñâîéñòâà, ñâÿçàííûå ñ ïðÿìûìè ëåêñèêîãðàôè÷åñêèìè
îãðàíè÷åíèÿìè.
Ñâîéñòâî 1. Ïóñòü X x D x x i tL i1
1
1� � � �{ | , , , }� è X x D x xL2
1
� � �{ }| ~ ,
ãäå ~ min , , ... ,x x x xL t� { }1 2 , çíàê �
1
L — ëåêñèêîãðàôè÷åñêîå îòíîøåíèå â ïîðÿä-
êå order1. Òîãäà X X1 2� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 49
Äîêàçàòåëüñòâî. Ñïðàâåäëèâîñòü ñâîéñòâà ñëåäóåò èç îïðåäåëåíèÿ ëåêñè-
êîãðàôè÷åñêîãî ìèíèìóìà ìíîæåñòâà è òîãî ôàêòà, ÷òî â ìíîæåñòâå X 1 âñå ïðÿ-
ìûå ëåêñèêîãðàôè÷åñêèå îãðàíè÷åíèÿ èñïîëüçóþò îäíî è òî æå ëåêñèêîãðàôè-
÷åñêîå îòíîøåíèå �
1
L.
Îòìåòèì, ÷òî îäèí ëåêñèêîãðàôè÷åñêèé ïîðÿäîê ìîæíî ïîëó÷èòü èç äðóãî-
ãî îïðåäåëåííîé ïåðåãðóïïèðîâêîé ïåðåìåííûõ çàäà÷è, êîòîðàÿ óñòàíîâèò íî-
âûå ïðèîðèòåòû äëÿ ïåðåìåííûõ. Ýòîãî ìîæíî äîñòè÷ü ñ ïîìîùüþ ìàòðèö ïåðå-
ñòàíîâîê. Ïóñòü P — ìàòðèöà ïåðåñòàíîâêè òàêàÿ, ÷òî ïîçâîëÿåò âåêòîð x, îïðå-
äåëåííûé â ïîðÿäêå order2 , ðàññìàòðèâàòü â ïîðÿäêå order1. Òîãäà P x( )
îáîçíà÷àåò òîò æå âåêòîð x, íî îïðåäåëåííûé â ïîðÿäêå order1.
Ñâîéñòâî 2. Ïóñòü X x D x xL1
1
1� � �{ }| � , X x D x xL2
2
2� � �{ }| � è X 12 �
� � � �{ | � , � }x D x x x xL L
1
1
2
2 . Òîãäà X X P X12 1 2� � ( ) , ãäå P X y D( ) |2 � �{
y P x x xL� �( ), �
2
2 } .
Äîêàçàòåëüñòâî. Ìíîæåñòâî P X( )2 ìîæíî ðàññìàòðèâàòü êàê îáðàç ìíî-
æåñòâà X 2 ïðè îòîáðàæåíèè P. Äðóãèìè ñëîâàìè, ìíîæåñòâî X 2 â ïîðÿäêå
order2 áóäåò ìíîæåñòâîì P X( )2 â ïîðÿäêå order1. Ïîñêîëüêó X X X12 1 2� � ,
â ïîðÿäêå order1 èìååì X X P X12 1 2� � ( ) .
Ïðîèëëþñòðèðóåì ïîñëåäíåå ñâîéñòâî íà ïðèìåðå. Ïóñòü ìíîæåñòâî D
ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî âñåõ áóëåâûõ âåêòîðîâ ðàçìåðíîñòè 4 (D B� 4).
Ëåêñèêîãðàôè÷åñêèé ïîðÿäîê order1 îïðåäåëÿåò ïðèîðèòåòû ïåðåìåííûõ êàê
{1, 2, 3, 4}, ïîðÿäîê order2 — {2, 4, 1, 3}. Ðàññìîòðèì äâà ïðÿìûõ ëåêñèêîãðàôè-
÷åñêèõ îãðàíè÷åíèÿ: x xL�
1
1, ãäå x1
1
0
0
0
�
�
�
�
�
�
�
�
�
�
�
�
�
; x xL�
2
2 , ãäå x 2
0
1
1
1
�
�
�
�
�
�
�
�
�
�
�
�
�
. Òîãäà
X x D x xL1
1
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
� � � �{ }| , , , , , , , ,
0
1
1
1
1
0
0
0
�
�
�
�
�
�
�
�
�
�
â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå
order1 è X x D x xL2
2
2
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
� � � �{ }| , , , , , , ,
0
1
1
1
�
�
�
�
�
�
�
�
�
�
â ïîðÿäêå order2 , íî
P X( ) , , , , , , ,2
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
1
0
1
�
�
�
�
�
�
�
�
�
�
�
â ïîðÿäêå order1. Òàêèì îáðàçîì, åñëè ñ÷èòàòü, ÷òî
â ðåçóëüòàòå ëåêñèêîãðàôè÷åñêîãî ïîèñêà â ïîðÿäêàõ order1 è order2 áûëè ïðî-
ñìîòðåíû ðåøåíèÿ, íå óäîâëåòâîðÿþùèå óêàçàííûì ïðÿìûì ëåêñèêîãðàôè÷åñ-
êèì îãðàíè÷åíèÿì, òî äàëüíåéøåìó ïðîñìîòðó â ïîðÿäêå order1 ïîäëåæàò òîëüêî
òî÷êè èç ìíîæåñòâà X P X1 2
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
� �
�
�
�
�
�
�
�
�
�
�
( ) , , , , .
ÎÁÎÁÙÅÍÍÛÉ ÀËÃÎÐÈÒÌ ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÎÃÎ ÏÎÈÑÊÀ
Ó÷èòûâàÿ ïðèâåäåííûå âûøå ðàññóæäåíèÿ, ìîæåì ïîñòðîèòü íîâûé îáîáùåííûé
àëãîðèòì ëåêñèêîãðàôè÷åñêîãî ïîèñêà ðåøåíèÿ çàäà÷è (1)–(3). Äëÿ ýòîãî íóæíî
îïðåäåëèòü: ïðàâèëî, ñîãëàñíî êîòîðîìó áóäåò îñóùåñòâëÿòüñÿ äâèæåíèå îò îä-
50 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
íîãî ðåøåíèÿ ê äðóãîìó â äàííîì
ëåêñèêîãðàôè÷åñêîì ïîðÿäêå; ïðàâè-
ëî ïîñòðîåíèÿ èëè âûáîðà íîâîãî
íàïðàâëåíèÿ äâèæåíèÿ (âûáîðà èëè
ïîñòðîåíèÿ íîâîãî ëåêñèêîãðàôè÷å-
ñêîãî ïîðÿäêà); óñëîâèÿ, îïðåäåëÿþ-
ùèå íåîáõîäèìîñòü èçìåíåíèÿ ëåê-
ñèêîãðàôè÷åñêîãî íàïðàâëåíèÿ äâè-
æåíèÿ è ïðåêðàùåíèÿ ïðîöåññà
âû÷èñëåíèé. Íà ðèñ. 5 ïðèâåäåíà
ñòðóêòóðíàÿ ñõåìà, â êîòîðîé èñ-
ïîëüçóþòñÿ ñëåäóþùèå îáîçíà÷åíèÿ:
y ALexMove x order� ( , ) — àëãîðèòì
ëåêñèêîãðàôè÷åñêîãî ïîèñêà, íà÷è-
íàþùèé ñâîþ ðàáîòó ñ ðåøåíèÿ x
â ïîðÿäêå order; y — äîïóñòèìîå
ðåøåíèå, ïîëó÷åííîå â ðåçóëüòàòå
ïîèñêà, ñ êîòîðîãî ïîèñê ìîæíî
ïðîäîëæàòü íà ñëåäóþùèõ øàãàõ;
order � GetOrder XSet OrderSet( , ) —
ïðàâèëî, ïî êîòîðîìó îïðåäåëÿåòñÿ
íîâûé ëåêñèêîãðàôè÷åñêèé ïîðÿäîê
order; x GetSolution XSet order� ( , ) —
ïðàâèëî, ïîçâîëÿþùåå ïîëó÷èòü ïî-
ñëåäíåå äîïóñòèìîå ðåøåíèå, ïðî-
ñìîòðåííîå ïðè ïîèñêå â ïîðÿäêå
order; OrderSet — ìíîæåñòâî ëåê-
ñèêîãðàôè÷åñêèõ ïîðÿäêîâ, èñïîëü-
çîâàííûõ íà ïðåäûäóùèõ øàãàõ; XSet — ìíîæåñòâî ðåøåíèé, íà êîòîðûõ çàêàí-
÷èâàëèñü ïðåäûäóùèå øàãè; CanFinished x( ) — óñëîâèå çàâåðøåíèÿ ïîèñêà;
CanOrderChanged x order( , ) — óñëîâèå ñìåíû ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà, åñëè
òåêóùåå ðåøåíèå — x , à òåêóùèé ïîðÿäîê — order; x� — ëó÷øåå ðåøåíèå èç
íàéäåííûõ íà äàííûé ìîìåíò; f f x� �� 0 ( ); k — íîìåð øàãà àëãîðèòìà;
max
k
L X — ëåêñèêîãðàôè÷åñêèé ìàêñèìóì ìíîæåñòâà X â ïîðÿäêå orderk .
Ïóñòü y ALexMove x order� ( , ) — ñòàíäàðòíûé äåòåðìèíèðîâàííûé àëãîðèòì
ëåêñèêîãðàôè÷åñêîãî ïîèñêà.  ïðîöåññå åãî ðàáîòû ñòðîèòñÿ ëåêñèêîãðàôè÷åñ-
êè óáûâàþùàÿ ïîñëåäîâàòåëüíîñòü âñåõ ïîäõîäÿùèõ ðåøåíèé. Èòàê, äëÿ ïðîèç-
âîëüíîãî ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà order ïîëó÷èì: x y
order
L
order
L� �� .
Èç òîãî, ÷òî äîïóñòèìîå ìíîæåñòâî äèñêðåòíî è îãðàíè÷åíî, ñëåäóåò, ÷òî äëÿ
êàæäîãî ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà order íåîáõîäèìî òîëüêî êîíå÷íîå
÷èñëî øàãîâ èñïîëüçîâàíèÿ äåòåðìèíèðîâàííîãî àëãîðèòìà AlexMove äëÿ ïðî-
ñìîòðà âñåõ ïîäõîäÿùèõ ðåøåíèé íà ëåêñèêîãðàôè÷åñêîì ïðîìåæóòêå
min max
order
L D
order
L
order
L
order
L DX x X� � , ñðåäè êîòîðûõ íàéäåòñÿ è îïòèìàëüíîå
ðåøåíèå. Äëÿ êàæäîãî íîâîãî ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà order ìîùíîñòü ìíî-
æåñòâà åùå íå ïðîñìîòðåííûõ ðåøåíèé êàæäûé ðàç óìåíüøàåòñÿ çà ñ÷åò âûáîðà íà-
÷àëüíîé òî÷êè x x X x x x XSet
order order
L D
t
L t t0 � � � �max |{ }. Íà îïðåäåëåííîì
øàãå ìîùíîñòü ìíîæåñòâà { }x X x x x XSetD
t
L t t� � �| óìåíüøèòñÿ íàñòîëüêî,
÷òî äëÿ ïðîñìîòðà âñåõ ðåøåíèé äîñòàòî÷íî îñóùåñòâèòü èõ ïîëíûé ïåðåáîð èëè
ïðèäåì ê ñèòóàöèè, êîãäà ýòî ìíîæåñòâî îêàæåòñÿ ïóñòûì. Îòñþäà ñëåäóåò, ÷òî êî-
ëè÷åñòâî èñïîëüçóåìûõ â àëãîðèòìå ðàçíûõ ëåêñèêîãðàôè÷åñêèõ ïîðÿäêîâ êîíå÷íî.
 òî æå âðåìÿ ìîæíî îáåñïå÷èòü êîíå÷íîñòü ÷èñëà ðàçíûõ ëåêñèêîãðàôè÷åñêèõ ïî-
ðÿäêîâ, èñïîëüçóþùèõñÿ â îáîáùåííîì àëãîðèòìå ëåêñèêîãðàôè÷åñêîãî ïîèñêà,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 51
k OrderSet order x X
f f x x x f
k
k
k
L D
k k k
� � �
� ��
0
0
; { }; max ;
( ); ; �
�
� � �
�
f XSet
CanFinished x
x AlexMove x
k
k k
; ;
(! ( )){
(
while
, );
( ( ) ){
; ;
}
(
order
f x f
x x f f
CanOrderCha
k
k
k k
if
if
0 �
� �
�
� �
nged x order
XSet XSet x
k k
order GetOr
k
k
k
k
( , )){
{ };
;
� !
� �
�
1
der XSet OrderSet
order OrderSet
x GetSolu
k
k
( , );
( ){if �
� tion XSet order
x x X x x x X
k
k
k
L D
t
L t t
( , );
}
{
max { | ,
else
� � � � Set
OrderSet OrderSet order
f f x
x
k
k k
};
{ };
}
( );
}
}
� !
�
�
0
opt x f f� ��; ;opt
Ðèñ. 5. Ñòðóêòóðíàÿ ñõåìà îáîáùåííîãî àëãîðèòìà
ëåêñèêîãðàôè÷åñêîãî ïîèñêà
åñëè ïðåäâàðèòåëüíî çàôèêñèðîâàòü èõ ìàêñèìàëüíîå êîëè÷åñòâî. Èç ïðèâåäåííûõ
âûøå ðàññóæäåíèé ñôîðìóëèðóåì ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 2. Åñëè ALexMove x order( , ) — äåòåðìèíèðîâàííûé àëãîðèòì ëåê-
ñèêîãðàôè÷åñêîãî ïîèñêà, ðåøåíèå x opt , ïîëó÷åííîå â ðåçóëüòàòå ïðèìåíåíèÿ
îáîáùåííîãî àëãîðèòìà ëåêñèêîãðàôè÷åñêîãî ïîèñêà, ÿâëÿåòñÿ ðåøåíèåì çàäà-
÷è (1)–(3).
ÂÎÇÌÎÆÍÎÑÒÈ ÑÒÎÕÀÑÒÈ×ÅÑÊÎÃÎ ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÎÃÎ ÏÎÈÑÊÀ
Âûáîð ðàçëè÷íûõ ñïîñîáîâ ïîñòðîåíèÿ íîâîãî ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà
è íà÷àëüíîé òî÷êè íà êàæäîì øàãå, à òàêæå ïðàâèë îïðåäåëåíèÿ ëåêñèêîãðà-
ôè÷åñêîãî íàïðàâëåíèÿ äâèæåíèÿ â äàííîì ïîðÿäêå ïîçâîëÿåò ñòðîèòü ðàçíî-
îáðàçíûå ìåòîäû ðàññìîòðåííîãî âûøå îáîáùåííîãî ïîèñêà. Áîëåå òîãî, åñëè
â àëãîðèòìå ALexMove îòêàçàòüñÿ îò ïîñòðîåíèÿ ëåêñèêîãðàôè÷åñêè ìîíîòîí-
íîé ïîñëåäîâàòåëüíîñòè ðåøåíèé, òî, õîòÿ íå áóäåò ãàðàíòèè ïðîñìîòðà âñåõ
ïîäõîäÿùèõ ðåøåíèé, ïîÿâèòñÿ âîçìîæíîñòü ñîçäàâàòü áîëåå ãèáêèå ñõåìû
ïåðåáîðà ðåøåíèé â çàäàííîì ëåêñèêîãðàôè÷åñêîì ïîðÿäêå. Ñ ó÷åòîì òîãî,
÷òî îïòèìàëüíîå ðåøåíèå â êàæäîì ëåêñèêîãðàôè÷åñêîì ïîðÿäêå order ñîäåð-
æèòñÿ ìåæäó ëåêñèêîãðàôè÷åñêèì ìèíèìóìîì è ìàêñèìóìîì ìíîæåñòâà X D ,
ò.å. min max
order
L D
order
L
order
L
order
L DX x X� �opt , ìîæíî, íàïðèìåð, îïðåäåëèòü
ñëåäóþùèå îáùèå ñõåìû ñòîõàñòè÷åñêîãî ëåêñèêîãðàôè÷åñêîãî ïîèñêà â äàí-
íîì ïîðÿäêå order.
1. Íàïîìíèì, ÷òî íà êàæäîì k-ì øàãå (k
1) äåòåðìèíèðîâàííîãî àëãîðèò-
ìà ëåêñèêîãðàôè÷åñêîãî ïîèñêà îñóùåñòâëÿåòñÿ ïîèñê ëåêñèêîãðàôè÷åñêîãî
ìàêñèìóìà ìíîæåñòâà X x X x x f x fk D L k� � �
{ }| , ( ) �1
0 . Â ðåçóëüòàòå ñòðî-
èòñÿ ïîñëåäîâàòåëüíîñòü ðåøåíèé (9), â êîòîðîé äëÿ êàæäîãî r � 0 1, ,� ìíîæåñ-
òâî { }x X y x yk r L L r� � ��| 1 â äàííîì ïîðÿäêå order ïóñòî. Ýòî, â ñâîþ î÷å-
ðåäü, ãàðàíòèðóåò, ÷òî íå áóäåò ïðîïóùåíî íè îäíîãî ïîäõîäÿùåãî ðåøåíèÿ. Íî
íà íåêîòîðûõ øàãàõ êîëè÷åñòâî ÷ëåíîâ ïîñëåäîâàòåëüíîñòè (9) ìîæåò áûòü
î÷åíü âåëèêî. Ïóñòü äëÿ îïðåäåëåííîãî ~y yr L r� åñòü âîçìîæíîñòü âû÷èñëÿòü
âåðîÿòíîñòü P y r(~ ) òîãî, ÷òî ìíîæåñòâî { }x X y x yk r L L r� � �| ~ â äàííîì ïî-
ðÿäêå order ïóñòî. Ýòî ïîçâîëÿåò ñòðîèòü íå âñþ ïîñëåäîâàòåëüíîñòü (9), à òîëü-
êî åå ÷àñòü, ÷òî ñóùåñòâåííî óìåíüøèò êîëè÷åñòâî åå ÷ëåíîâ, à ñëåäîâàòåëüíî, è
îáùåå âðåìÿ ïîëó÷åíèÿ îïòèìàëüíîãî ðåøåíèÿ çàäà÷è.
2. Ïðåäïîëîæèì, ÷òî ñ îïðåäåëåííîé âåðîÿòíîñòüþ ìîæíî âûÿñíèòü, ñ êà-
êîé ñòîðîíû îò îïòèìàëüíîãî â äàííîì ëåêñèêîãðàôè÷åñêîì ïîðÿäêå ðàñïîëîæå-
íî ðåøåíèå, ïîëó÷àåìîå íà î÷åðåäíîì øàãå. Òàêèì îáðàçîì, íà êàæäîì k-ì øàãå
îñóùåñòâëÿåòñÿ ïðîöåññ ñëó÷àéíîãî ïåðåáîðà äîïóñòèìûõ ðåøåíèé íà ëåêñè-
êîãðàôè÷åñêîì îòðåçêå x x xk
order
L
order
L k
min max� � . Ïî çàâåðøåíèè î÷åðåäíîãî
ïðîñìîòðà ïîëó÷àåì äîïóñòèìîå ðåøåíèå x k èç ýòîãî ïðîìåæóòêà. Îïðåäåëÿåì
âåðîÿòíîñòü P x orderk( , ) òîãî, ÷òî ïîëó÷åííîå ðåøåíèå x k ëåêñèêîãðàôè÷åñêè
áîëüøå, ÷åì îïòèìàëüíîå. Åñëè | ( , ) . |P x orderk �0 5 �, òî îòðåçîê íå èçìåíÿåòñÿ;
åñëè P x orderk( , ) .� �0 5 �, òî íà ñëåäóþùèõ øàãàõ ïîèñêà â ïîðÿäêå order èñ-
ïîëüçóåì ëåêñèêîãðàôè÷åñêèé ïðîìåæóòîê x x xk
order
L
order
L k
min
� � ; åñëè
P x orderk( , ) .� 0 5 �, òî â ïîðÿäêå order áóäåì èñïîëüçîâàòü ëåêñèêîãðàôè÷åñêèé
îòðåçîê x x xk
order
L
order
L k� � max .
3. Ïóñòü èçâåñòåí ìåõàíèçì, ïîçâîëÿþùèé ñ çàäàííîé âåðîÿòíîñòüþ
âûÿñíèòü, íàñêîëüêî áëèçêî â ëåêñèêîãðàôè÷åñêîì ñìûñëå íàõîäèòñÿ îïòèìàëü-
íîå ðåøåíèå ïî îòíîøåíèþ ê îïðåäåëåííîìó ëåêñèêîãðàôè÷åñêîìó ïðîìåæóòêó,
èëè, äðóãèìè ñëîâàìè, âû÷èñëèòü âåðîÿòíîñòü òîãî, ÷òî äàííûé ëåêñèêîãðàôè-
52 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
÷åñêèé ïðîìåæóòîê ñîäåðæèò îïòèìàëüíîå ðåøåíèå. Òîãäà ñëó÷àéíûì îáðàçîì
îïðåäåëÿþòñÿ ëåêñèêîãðàôè÷åñêèå ãðàíèöû ïîèñêà, îñóùåñòâëÿåòñÿ ïðîöåññ
ñëó÷àéíîãî ïåðåáîðà äîïóñòèìûõ ðåøåíèé â ýòèõ ïðåäåëàõ è ñ ïîìîùüþ óêàçàí-
íîãî ìåõàíèçìà âû÷èñëÿåòñÿ âåðîÿòíîñòü íàõîæäåíèÿ îïòèìàëüíîãî âàðèàíòà íà
ýòîì ïðîìåæóòêå. Â ðåçóëüòàòå ïðèíèìàåòñÿ ðåøåíèå î âîçìîæíîñòè
èñïîëüçîâàíèÿ äàííîãî ïðîìåæóòêà íà ñëåäóþùèõ øàãàõ èëè èñêëþ÷åíèÿ åãî èç
äàëüíåéøåãî ïîèñêà.
Îäíà èç ðåàëèçàöèé ïîñëåäíåé ðàññìîòðåííîé îáùåé ñõåìû çàêëþ÷àåòñÿ
â ñëåäóþùåì [3]. Íà êàæäîì øàãå ñîãëàñíî óêàçàííîìó ìåõàíèçìó ôèêñèðóåòñÿ
ðåøåíèå sk , êîòîðîå ÿâëÿåòñÿ íèæíåé ãðàíèöåé ïîèñêà, è ïðåäïðèíèìàåòñÿ ïî-
ïûòêà çà îïðåäåëåííîå ÷èñëî èñïûòàíèé íàéòè äîïóñòèìîå ðåøåíèå ìíîæåñòâà
{ }x X s x x f x f xD k L L k k� � � �| , ( ) ( )0 0 , ãäå x k — ëó÷øåå äîïóñòèìîå ðåøåíèå,
ïîëó÷åííîå íà ïðåäûäóùåì øàãå.  ïðîöåññå èñïûòàíèÿ t t�1 2, , , max� ñëó÷àé-
íûì îáðàçîì ñòðîèòñÿ ðåøåíèå z x B s x xt n k L L k� � � �{ | , f x f x k
0 0( ) ( )� }. Îíî
óòî÷íÿåòñÿ ïóòåì îòûñêàíèÿ äîïóñòèìîãî ðåøåíèÿ y x Xt L D� �max |{
s x zk L L t� � }.
Ïðîèëëþñòðèðóåì ýôôåêòèâíîñòü èñïîëüçîâàíèÿ òàêîé ñõåìû ñòîõàñòè÷åñ-
êîãî ëåêñèêîãðàôè÷åñêîãî ïîèñêà äëÿ àëãîðèòìà ALexMove ïî ñðàâíåíèþ ñî
ñòàíäàðòíûì äåòåðìèíèðîâàííûì àëãîðèòìîì ëåêñèêîãðàôè÷åñêîãî ïîèñêà. Ðå-
øàëàñü ïåðâàÿ òåñòîâàÿ çàäà÷à èç íàáîðà çàäà÷ î ìíîãîìåðíîì ðàíöå, ïðåäëîæåí-
íîãî Ô. Ãëîâåðîì, â êîòîðîé êîëè÷åñòâî îãðàíè÷åíèé — 15, ïåðåìåííûõ — 100,
ðåêîðäíîå çíà÷åíèå — 3766. Ïðîöåññ ðåøåíèÿ çàäà÷è àëãîðèòìîì ñòîõàñòè÷åñ-
êîãî ëåêñèêîãðàôè÷åñêîãî ïîèñêà èçîáðàæåí íà ðèñ. 6, ñòàíäàðòíûì äåòåðìèíè-
ðîâàííûì àëãîðèòìîì ëåêñèêîãðàôè÷åñêîãî ïîèñêà — íà ðèñ 7.
Èç ïðèâåäåííûõ ðåçóëüòàòîâ âèäíî, ÷òî îïòèìàëüíîå ðåøåíèå ìåòîäîì ñòî-
õàñòè÷åñêîãî ëåêñèêîãðàôè÷åñêîãî ïîèñêà, ïîñòðîåííîãî ïî îáîáùåííîìó àëãî-
ðèòìó, ïðåäñòàâëåííîìó íà ðèñ. 5, ïîëó÷åíî çà 12 ñ.  òî æå âðåìÿ ñòàíäàðòíûé
äåòåðìèíèðîâàííûé àëãîðèòì ëåêñèêîãðàôè÷åñêîãî ïîèñêà îñóùåñòâëÿëñÿ â îä-
íîì ôèêñèðîâàííîì ëåêñèêîãðàôè÷åñêîì ïîðÿäêå è áûë îñòàíîâëåí ïîñëå áîëåå
÷åì 12 ÷ ðàáîòû, òàê è íå äîñòèãíóâ îïòèìàëüíîãî ðåøåíèÿ. Ýòî ñâèäåòåëüñòâóåò
î çíà÷èòåëüíîì ïðåèìóùåñòâå, êîòîðîå ìîæíî ïîëó÷èòü, åñëè â ñòàíäàðòíûõ äå-
òåðìèíèðîâàííûõ ñõåìàõ ïðèìåíèòü ìåõàíèçìû ñëó÷àéíîãî ïîèñêà.
ÇÀÊËÞ×ÅÍÈÅ
Ëåêñèêîãðàôè÷åñêîå óïîðÿäî÷åíèå âàðèàíòîâ ïîçâîëÿåò îðãàíèçîâûâàòü èõ öå-
ëåíàïðàâëåííûé ïðîñìîòð. Îñóùåñòâëÿÿ ïîèñê â ðàçëè÷íûõ ëåêñèêîãðàôè÷åñ-
êèõ ïîðÿäêàõ è âûáèðàÿ ðàçíûå ñõåìû ëåêñèêîãðàôè÷åñêîãî ïåðåáîðà âàðèàí-
òîâ â çàäàííîì ïîðÿäêå ñ ó÷åòîì õàðàêòåðíûõ îñîáåííîñòåé çàäà÷è, ìîæíî
ñòðîèòü ýôôåêòèâíûå ìåòîäû ëåêñèêîãðàôè÷åñêîãî ïîèñêà äëÿ îòûñêàíèÿ
îïòèìàëüíûõ ðåøåíèé ñîâðåìåííûõ ïðèêëàäíûõ çàäà÷ îïòèìèçàöèè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4 53
Step=1 RecordF=3735 at 0:00:00.001
Step=1 RecordF=3749 at 0:00:00.036
Step=1 RecordF=3756 at 0:00:00.037
Step=4 RecordF=3759 at 0:00:01.743
Step=9 RecordF=3766 at 0:00:12.385
** Solve: Record=3766 and feasible.**
Ðèñ. 6. Ðåçóëüòàò ðàáîòû ñòîõàñòè÷å-
ñêîãî àëãîðèòìà ëåêñèêîãðàôè÷åñêîãî
ïîèñêà
Step=0 RecordF=3735 Etaps=0 at 0:00:00.000
Step=1 RecordF=3748 Etaps=1 at 0:00:00.002
Step=2 RecordF=3753 Etaps=89 at 0:00:00.003
Step=3 RecordF=3757 Etaps=1858 at 0:00:00.007
Step=4 RecordF=3761 Etaps=1082885 at 0:00:02.308
Step=5 RecordF=3761 Etaps=20334824735 at 12:12:16.305
Ðèñ. 7. Ðåçóëüòàò ðàáîòû äåòåðìèíèðîâàííîãî àëãîðèò-
ìà ëåêñèêîãðàôè÷åñêîãî ïîèñêà
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè. Ïðîáëåìû, ìåòîäû ðåøåíèÿ,
èññëåäîâàíèÿ. — Ê.: Íàóê. äóìêà, 2003. — 261 ñ.
2. × å ð â à ê Þ . Þ . Îïòèì³çàö³ÿ. Íåïîêðàùóâàíèé âèá³ð. — Óæãîðîä: Óæãîðîä. íàö. óí-ò, 2002. —
312 ñ.
3. × ó ï î â Ñ .  . Ñòîõàñòè÷íèé àëãîðèòì ëåêñèêîãðàô³÷íîãî ïîøóêó ðîçâ’ÿçêó áóëåâî¿ çàäà÷³ ïðî ðà-
íåöü // Ïðàö³ V²² ì³æíàð. øêîëè-ñåì³íàðó «Òåîð³ÿ ïðèéíÿòòÿ ð³øåíü» (29 âåðåñíÿ – 4 æîâòíÿ 2014 ð.,
ì. Óæãîðîä). — Óæãîðîä: Óæãîðîä. íàö. óí-ò, 2014. — Ñ. 263, 264.
4. × ó ï î â Ñ .  . Ñòðóêòóðí³ âëàñòèâîñò³ ìíîæèíè, çàäàíî¿ â ð³çíèõ ïîðÿäêàõ // Ïðàö³ IV ì³æíàð. øêî-
ëè-ñåì³íàðó «Òåîð³ÿ ïðèéíÿòòÿ ð³øåíü» (29 âåðåñíÿ – 4 æîâòíÿ 2008 ð., ì. Óæãîðîä). — Óæãîðîä:
Óæãîðîä. íàö. óí-ò, 2008. — Ñ. 162.
5. × ó ï î â Ñ .  . Ëåêñèêîãðàô³÷íèé ìàêñèìóì îïóêëèõ êîìïàêò³â òà àëãåáðà¿÷í³ îïåðàö³¿ íàä íèìè //
Ïðàö³ ì³æíàð. êîíô. «Ïðîãíîçóâàííÿ òà ïðèéíÿòòÿ ð³øåíü â óìîâàõ íåâèçíà÷åíîñò³» (PDMU – 2001)
(11–14 âåðåñíÿ 2001 ð., Êè¿â). — Ê.: Âèä.-ïîë³ãðàô. öåíòð «Êè¿âñüêèé óí³âåðñèòåò», 2001. —
Ñ. 138, 139.
6. × ó ï î â Ñ .  . Àëãîðèòì ïîøóêó ö³ëî÷èñëîâîãî ëåêñèêîãðàô³÷íîãî ìàêñèìóìó ìíîæèíè // Íàóê.
â³ñíèê Óæãîðîä. äåðæ. óí-òó: Ñåð. Ìàòåìàòèêà. — Óæãîðîä, 1997. — Âèï. 2. — Ñ. 122, 123.
7. × å ð â à ê Þ . Þ . , à ð å í ä æ à  . ² . , × ó ï î â Ñ .  . Ëåêñèêîãðàô³÷íà îïòèì³çàö³ÿ â äèñêðåòíîìó
ïðîãðàìóâàíí³ // ̳æíàð. êîíô. «Ïèòàííÿ îïòèì³çàö³¿ îá÷èñëåíü» (Êè¿â, 6–9 æîâòíÿ 1997 ð.): Ïðàö³
ÍÀÍ Óêðà¿íè. — Êè¿â: ²í-ò ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà, 1997. — Ñ. 317–319.
Íàä³éøëà äî ðåäàêö³¿ 10.11.2015
Ñ.Â. ×óïîâ
Íβ ϲÄÕÎÄÈ ÄÎ ÐÎÇÂ’ßÇÀÍÍß ÇÀÄÀ× ÄÈÑÊÐÅÒÍÎÃÎ ÏÐÎÃÐÀÌÓÂÀÍÍß
ÍÀ ÎÑÍβ ËÅÊÑÈÊÎÃÐÀÔ²×ÍÎÃÎ ÏÎØÓÊÓ
Àíîòàö³ÿ. Çàïðîïîíîâàíî íîâ³ ï³äõîäè äî ðîçâ’ÿçàííÿ çàäà÷ äèñêðåòíîãî
ïðîãðàìóâàííÿ íà îñíîâ³ ïîøóêó ëåêñèêîãðàô³÷íîãî âïîðÿäêóâàííÿ âåêòîð³â,
ïðè ÿêîìó îïòèìàëüíèé ðîçâ’ÿçîê çàäà÷³ àáî çá³ãàºòüñÿ ç ëåêñèêîãðàô³÷íèì
åêñòðåìóìîì ìíîæèíè äîïóñòèìèõ ðîçâ’ÿçê³â çàäà÷³, àáî çíàõîäèòüñÿ äîñòàò-
íüî áëèçüêî â³ä íüîãî â ëåêñèêîãðàô³÷íîìó ñåíñ³. Îïèñàíî óçàãàëüíåíó ñõå-
ìó òàêîãî ëåêñèêîãðàô³÷íîãî ïîøóêó òà ìîæëèâîñò³ äëÿ ¿¿ ìîäèô³êàö³¿. Ïðî-
³ëþñòðîâàíî çíà÷í³ ïåðåâàãè â åôåêòèâíîñò³ ðîáîòè öüîãî ï³äõîäó â ïîð³â-
íÿíí³ ç ñòàíäàðòíèì àëãîðèòìîì ëåêñèêîãðàô³÷íîãî ïîøóêó.
Êëþ÷îâ³ ñëîâà: ëåêñèêîãðàô³÷íèé ïîðÿäîê, ëåêñèêîãðàô³÷íèé ìàêñèìóì,
çàäà÷à äèñêðåòíîãî ïðîãðàìóâàííÿ, àëãîðèòì ëåêñèêîãðàô³÷íîãî ïîøóêó.
S.V. Chupov
NEW APPROACHES TO SOLVING DISCRETE PROGRAMMING PROBLEMS BASED
ON LEXICOGRAPHIC SEARCH
Abstract. The author proposes new approaches to solving discrete programming
problems based on the search for lexicographical ordering of vectors, such that
the optimal problem solution either coincides with the lexicographic extremum
of the feasible set of problem solutions or is close enough to it in the
lexicographic sense. The general scheme of such lexicographic search and the
possibilities for its modification are described. Significant advantages in the
efficiency of this approach compared with the the standard lexicographic search
algorithm are illustrated.
Keywords: lexicographical ordering, lexicographic maximum, discrete programming
problem, lexicographic search algorithm.
×óïîâ Ñåðãåé Âèêòîðîâè÷,
êàíäèäàò ôèç.-ìàò. íàóê, äîöåíò Óæãîðîäñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà,
e-mail: sergey.chupov@gmail.com.
54 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 4
|