Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута
Побудовано математичну модель прикладної задачі оптимізації замкнених маршрутів — кільцевої задачі про сільського листоношу. Запропоновано двоетапний метод типу гілок та меж, який знаходить розв’язок або встановлює факт нерозв’язності задачі. Перший етап методу включає перевірку достатніх умов нероз...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2013 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/86276 |
| 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: | Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута / А.О. Овезгельдыев, А.В. Морозов // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 112-123. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859773436673392640 |
|---|---|
| author | Овезгельдыев, А.О. Морозов, А.В. |
| author_facet | Овезгельдыев, А.О. Морозов, А.В. |
| citation_txt | Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута / А.О. Овезгельдыев, А.В. Морозов // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 112-123. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Побудовано математичну модель прикладної задачі оптимізації замкнених маршрутів — кільцевої задачі про сільського листоношу. Запропоновано двоетапний метод типу гілок та меж, який знаходить розв’язок або встановлює факт нерозв’язності задачі. Перший етап методу включає перевірку достатніх умов нерозв’язності і процедуру вершинно-реберного перетворення. Це дає можливість скоротити час пошуку розв’язку на другому етапі методу за допомогою запропонованої модифікації методу Літтла. У ній вперше застосовано спосіб розбиття множини розв’язків на підмножини, що не перетинаються, за допомогою трьох правил розгалуження і обчисленням відповідних нижніх оцінок вартості оптимального розв’язку. Запропонований метод коректно виконує пошук оптимального розв’язку гамільтонової задачі про сільського листоношу, загальної і гамільтонової задачі комівояжера.
A mathematical model of the applied problem of optimization of closed routes, i.e., the rural postman problem, is constructed. A two-stage method of the type of the branch-and-bound one is proposed that finds a solution or establishes the fact of the unsolvability of the problem. The first stage of the method includes the test of sufficient unsolvability conditions and a vertex-edge transformation procedure. This makes it possible to decrease the time of searching for a solution at the second stage of the method with the help of a proposed modification of the Little method. This procedure uses (for the first time) a partition of a solution set into disjoint subsets with the help of three rules of branching and computation of corresponding lower assessed values of an optimal solution. The proposed method correctly searches for an optimal solution of the Hamiltonian rural postman problem and general and Hamiltonian traveling salesman problems.
|
| first_indexed | 2025-12-02T07:26:53Z |
| format | Article |
| fulltext |
ÓÄÊ 519.161
À.Î. ÎÂÅÇÃÅËÜÄÛÅÂ, À.Â. ÌÎÐÎÇÎÂ
ÐÀÇÂÈÒÈÅ ÌÅÒÎÄÀ ÂÅÒÂÅÉ È ÃÐÀÍÈÖ Â ÇÀÄÀ×Å ÏÎÈÑÊÀ
ÎÏÒÈÌÀËÜÍÎÃÎ ÊÎËÜÖÅÂÎÃÎ ÌÀÐØÐÓÒÀ
Êëþ÷åâûå ñëîâà: ìåòîä âåòâåé è ãðàíèö, çàäà÷à êîììèâîÿæåðà, çàäà÷à
î ïî÷òàëüîíå.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ìíîãî÷èñëåííûå ðåçóëüòàòû, íàêîïëåííûå â èçó÷åíèè ïðîáëåìû êîììèâîÿæå-
ðà, íåïðåðûâíî ðàçâèâàþòñÿ, âûäâèãàÿ àêòóàëüíûå âîïðîñû ðàçðàáîòêè è ñîâåð-
øåíñòâîâàíèÿ ìåòîäîâ êîìáèíàòîðíîé îïòèìèçàöèè è èõ ïðèìåíåíèÿ â ïðàêòè-
÷åñêîé è íàó÷íîé äåÿòåëüíîñòè. Äàëåêî íå äëÿ êàæäîé çàäà÷è îïòèìèçàöèè íà
òðàíñïîðòíîé ñåòè ðàçðàáîòàíû àëãîðèòìû ïîèñêà ðåøåíèé, ïðèãîäíûå â ðåàëü-
íûõ ñèòóàöèÿõ. Îäíîé èç òàêèõ çàäà÷ ÿâëÿåòñÿ çàäà÷à î ñåëüñêîì ïî÷òàëü-
îíå (ÇÑÏ), îãðàíè÷åííàÿ âåðñèÿ êîòîðîé ðàññìàòðèâàåòñÿ â äàííîé ñòàòüå.
Çàäàí ñâÿçíûé âçâåøåííûé ãðàô H V U� ( , ) ñ ìíîæåñòâîì âåðøèíV , | |V n� ,
è ìíîæåñòâîì ðåáåð U . Êàæäîìó ðåáðó { , }i j U� ïðèïèñàí âåñ d Zij � �
0
, i j� ,
i j n, ,�1 ; Z
0
� — ìíîæåñòâî íåîòðèöàòåëüíûõ öåëûõ ÷èñåë. Ãðàô H ïîëíîñòüþ
îïðåäåëÿåòñÿ ñèììåòðè÷íîé ìàòðèöåé ñòîèìîñòåé [ ]dij n , ãäå d Zij � �
0
, åñëè
{ }i j U, � , è dij � � â ïðîòèâíîì ñëó÷àå, i j� , i j n, ,�1 , dii � �, i n�1, . Íà ìíî-
æåñòâå U çàäàíî íåïóñòîå ïîäìíîæåñòâî ðåáåð R U� . Òðåáóåòñÿ íàéòè â ãðàôå
H ïðîñòîé öèêë, âêëþ÷àþùèé êàæäîå ðåáðî èç ìíîæåñòâà R è èìåþùèé ìèíè-
ìàëüíóþ ñóììó âåñîâ ðåáåð.
 ðàññìàòðèâàåìîé çàäà÷å, â îòëè÷èå îò ÇÑÏ, èñêîìûé öèêë äîëæåí áûòü
ïðîñòûì. Ïîñòàâëåííóþ çàäà÷ó íàçîâåì êîëüöåâîé çàäà÷åé î ñåëüñêîì
ïî÷òàëüîíå (ÊÇÑÏ).
ÎÑÍÎÂÍÀß ÈÄÅß ÌÅÒÎÄÀ ÐÅØÅÍÈß ÇÀÄÀ×È
ÊÇÑÏ NP-ïîëíà, è òîëüêî åå îãðàíè÷åííûå ÷àñòíûå ñëó÷àè ýôôåêòèâíî ðàçðå-
øèìû. Èç NP-ïîëíîòû ÊÇÑÏ ñëåäóåò, ÷òî îíà íå ïîääàåòñÿ ýôôåêòèâíûì
òî÷íûì ìåòîäàì ðåøåíèÿ. Ïîñêîëüêó ìíîæåñòâî ïðîñòûõ öèêëîâ ãðàôà, âêëþ-
÷àþùèõ âñå ðåáðà R, ìîæåò îêàçàòüñÿ ïóñòûì, âûòåêàåò íåïðèìåíèìîñòü ýô-
ôåêòèâíûõ ïðèáëèæåííûõ àëãîðèòìîâ. Ïîýòîìó åäèíñòâåííîé ïðèåìëåìîé
ñõåìîé ïîèñêà ðåøåíèÿ ÊÇÑÏ ÿâëÿåòñÿ ñõåìà ñîêðàùåíèÿ ïåðåáîðà, îðãàíèçî-
âàííàÿ ïî ìåòîäó âåòâåé è ãðàíèö, êîòîðûé îñòàåòñÿ óíèâåðñàëüíûì è ìîù-
íûì èíñòðóìåíòîì êîìáèíàòîðíîé îïòèìèçàöèè.
 ðàññìàòðèâàåìîì ìåòîäå ïîèñêà òî÷íîãî ðåøåíèÿ ÊÇÑÏ àëãîðèòìó âåòâåé
è ãðàíèö ïðåäøåñòâóåò ñòàäèÿ ýôôåêòèâíîé ïðîâåðêè èçâåñòíûõ äîñòàòî÷íûõ
óñëîâèé íåðàçðåøèìîñòè ÊÇÑÏ. Ê íåé îòíîñèòñÿ ïðîöåäóðà âåðøèííî-ðåáåðíî-
ãî ïðåîáðàçîâàíèÿ (ÂÐÏ) èñõîäíîãî ãðàôà H â ãðàô ñî ñòðóêòóðíûìè õàðàêòå-
ðèñòèêàìè, âûçûâàþùèìè âûïîëíåíèå ïåðåáîðíîãî àëãîðèòìà [1]. Ïåðåáîðíûé
àëãîðèòì, âûïîëíÿåìûé íà âòîðîé ñòàäèè ðåøåíèÿ ÊÇÑÏ, ïðåäñòàâëÿåò ñîáîé
ìîäèôèêàöèþ êëàññè÷åñêîãî ìåòîäà Ëèòòëà [2], àäàïòèðîâàííîãî äëÿ ïîèñêà ðå-
øåíèÿ ÊÇÑÏ íà ïðåîáðàçîâàííîì ãðàôå, â êîòîðîì ñòåïåíü êàæäîé âåðøèíû
i V� áîëüøå äâóõ, ìíîæåñòâî R îáðàçóåò ïàðîñî÷åòàíèå è â ãðàôå îòñóòñòâóþò
òî÷êè ñî÷ëåíåíèÿ.
112 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5
© À.Î. Îâåçãåëüäûåâ, À.Â. Ìîðîçîâ, 2013
 ïðåäëàãàåìîé ìîäèôèêàöèè, êàê è â àëãîðèòìå Ëèòòëà, äëÿ ðåøåíèÿ ñèì-
ìåòðè÷íîé çàäà÷è êîììèâîÿæåðà äåðåâî ðåøåíèé ðàçâèâàåòñÿ èç ïðåäñòàâëåíèÿ
ìàòðèöû ñòîèìîñòåé [ ]dij n îðèåíòèðîâàííûì ãðàôîì G V E( , )� , ïîëó÷åííûì
â äàííîì ñëó÷àå èç ãðàôà H çàìåíîé êàæäîãî ðåáðà { , }i j U� ïàðîé äóã: ( , )i j E�
è ( , )j i E� . Ðåøåíèå ÊÇÑÏ ïðåäñòàâëÿåò ïðîñòîé öèêë ìèíèìàëüíîé ñòîèìîñòè.
Ñëåäîâàòåëüíî, ìîäèôèêàöèÿ àëãîðèòìà ïðèìåíèìà äëÿ íàõîæäåíèÿ ðåøåíèÿ
ÊÇÑÏ, ñôîðìóëèðîâàííîé â òåðìèíàõ îðèåíòèðîâàííûõ ãðàôîâ.
 ìåòîäå ðåøåíèÿ ÊÇÑÏ êîðíåâîé âåðøèíå X 0 äåðåâà ïåðåáîðà ñòàâèòñÿ â ñî-
îòâåòñòâèå ìàòðèöà ñòîèìîñòåé D dij n� [ ] èñõîäíîãî ãðàôà H , ìàòðèöà äëèí êðàò-
÷àéøèõ ïóòåé M è ìàòðèöà ìàðøðóòèçàöèè W.  ðåçóëüòàòå èõ ïðåîáðàçîâàíèÿ íà-
õîäÿòñÿ âåðøèíû, ïîðîæäåííûå íà øàãå âåòâëåíèÿ. Äëÿ îïðåäåëåíèÿ ìàòðèö M è W
íà êàæäîì øàãå âåòâëåíèÿ ïðèìåíÿåòñÿ ìîäèôèêàöèÿ àëãîðèòìà Ôëîéäà–Óîðøåë-
ëà. Â ñîâîêóïíîñòè ìàòðèöû D, M è W ïîçâîëÿþò âûïîëíÿòü â óñëîâèÿõ ïîñòàâëåí-
íîé çàäà÷è âñå äåéñòâèÿ, âêëþ÷åííûå â êëàññè÷åñêèé ìåòîä Ëèòòëà.
Èç ìàòðèö M è W, ôîðìèðóåìûõ ìîäèôèöèðîâàííûì àëãîðèòìîì Ôëîé-
äà–Óîðøåëëà äëÿ òåêóùèõ ïàðàìåòðîâ ìàòðèöû D, îïðåäåëÿåòñÿ äóãà ( , )p q èëè
ïóòü èç âåðøèíû p â âåðøèíó q, èíèöèèðóþùèå âåòâëåíèå. Óñëîâèÿ ðàññìàòðè-
âàåìîé çàäà÷è òðåáóþò ôîðìèðîâàíèÿ ìíîæåñòâà çàïðåùåííûõ äóã Q, ò.å. äóã,
êîòîðûå ïðèâîäÿò ê ïîÿâëåíèþ ïîäêîíòóðîâ â èñêîìîì ðåøåíèè. Â ìíîæåñòâî Q
âêëþ÷àþòñÿ äóãè â çàâèñèìîñòè îò ñïîñîáà ðàçáèåíèÿ ìíîæåñòâà äîïóñòèìûõ
ðåøåíèé íà ïîäìíîæåñòâà. Åñëè âåòâëåíèå èíèöèèðóåò äóãà ( , )k l , ñîîòâåòñòâó-
þùàÿ ðåáðó { }k l R, � , òî ìíîæåñòâî äîïóñòèìûõ ðåøåíèé çàäà÷è ðàçáèâàåòñÿ íà
äâà ïîäìíîæåñòâà. Ïåðâîå ïîäìíîæåñòâî ñîñòîèò èç âñåõ öèêëîâ, âêëþ÷àþùèõ
äóãó ( , )k l , à âòîðîå — èç âñåõ öèêëîâ, ñîäåðæàùèõ äóãó ( , )l k .
Ïóñòü âåòâëåíèå èíèöèèðóåò äóãà ( , )k l , {k l, }�R , èëè ïóòü èç âåðøèíû k â
âåðøèíó l . Ïðè ôîðìèðîâàíèè ìíîæåñòâà Q ïóòü ðàññìàòðèâàåòñÿ êàê äóãà
( , )k l .  ýòîì ñëó÷àå ìíîæåñòâî äîïóñòèìûõ ðåøåíèé ðàçáèâàåòñÿ íà äâà ïîä-
ìíîæåñòâà. Ïåðâîå ïîäìíîæåñòâî âêëþ÷àåò âñå öèêëû, ñîäåðæàùèå ( , )k l , à âòî-
ðîå — öèêëû, íå ñîäåðæàùèå ( , )k l , ò.å. ( , )k l .
Ïðè ôîðìèðîâàíèè ïåðâîãî ïîäìíîæåñòâà òðåáóåòñÿ ïðîâåðêà ñëåäóþùèõ
óñëîâèé. Åñëè ìíîæåñòâî R ñîäåðæèò ðåáðî {x k, }, òî â èñêîìûé êîíòóð âìåñòå ñ
äóãîé ( , )k l âêëþ÷àåòñÿ äóãà ( , )x k . Àíàëîãè÷íî åñëè ìíîæåñòâî R ñîäåðæèò ðåá-
ðî { y l, }, òî ê äóãå ( , )k l ïðèñîåäèíÿåòñÿ äóãà ( , )l y . Âêëþ÷åíèå äóãè ( , )x k èëè
( , )l y â ïîäìíîæåñòâî ðåøåíèé îçíà÷àåò, ÷òî îïðåäåëÿþùàÿ åãî ìàòðèöà D íå ñî-
äåðæèò íå òîëüêî ñòðîêè k è ñòîëáöà l , íî è òîé ñòðîêè è ñòîëáöà, íîìåðà êîòî-
ðûõ ÿâëÿþòñÿ íà÷àëîì è êîíöîì ïðèñîåäèíåííîé äóãè.  ñëó÷àå {x k, }, { y l, }�R
ê äóãå ( , )k l ïðèñîåäèíÿþòñÿ äóãè ( , )x k è ( , )l y , à â ñîîòâåòñòâóþùåé ìàòðèöå D ,
îïðåäåëÿþùåé ýòî ìíîæåñòâî, èñêëþ÷àþòñÿ ñòðîêè x k l, , è ñòîëáöû k l y, , .
Ñôîðìóëèðóåì ïðàâèëà îïðåäåëåíèÿ ìíîæåñòâà Q :
• äëÿ êîðíÿ X 0 äåðåâà ïåðåáîðà ïîëàãàåì Q � ;
• âñå ýëåìåíòû ìíîæåñòâà Q ïðè âåðøèíå âåòâëåíèÿ ïåðåäàþòñÿ åå ïîðîæ-
äåííîé âåðøèíå;
• åñëè â ëþáîå ðåøåíèå ïðè âåðøèíå, ïîðîæäåííîé íà øàãå âåòâëåíèÿ,
âêëþ÷àåòñÿ äóãà ( , )k l , òî ê ìíîæåñòâó Q ïðè ýòîé âåðøèíå äîáàâëÿåòñÿ äóãà ( , )l k ;
• âåñ êàæäîé äóãè â Q ïðèíèìàåòñÿ ðàâíûì áåñêîíå÷íîñòè.
Åñëè âåòâëåíèå èíèöèèðóåò ïóòü èç âåðøèíû k â âåðøèíó l, âêëþ÷àþùèé íå
ìåíåå äâóõ äóã, òî äëÿ ðàçáèåíèÿ ìíîæåñòâà äîïóñòèìûõ ðåøåíèé íà íåïåðåñå-
êàþùèåñÿ ïîäìíîæåñòâà èñïîëüçóåòñÿ ïðàâèëî, êîòîðîå îòëè÷àåòñÿ îò ïðàâèëà,
ïðèìåíÿåìîãî äëÿ ôîðìèðîâàíèÿ ìíîæåñòâà Q.  ýòîì ñëó÷àå ðåçóëüòàòîì ðàç-
áèåíèÿ ÿâëÿåòñÿ ìíîæåñòâî âåðøèí V L( ), ïðåäñòàâëÿþùåå ðàñøèðåííîå ìíî-
æåñòâî àêòèâíûõ âåðøèí, ïîðîæäåííûõ íà ïðåäûäóùèõ øàãàõ âåòâëåíèÿ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 113
 êîðíåâîé âåðøèíå è âåðøèíå âåòâëåíèÿ, äëÿ êîòîðîé ïðîöåññ ðàçáèåíèÿ
èíèöèèðóåò äóãà, V L( ) � . Ìíîæåñòâî âåðøèí V R V L( ) ( )
îïðåäåëÿåò ðàáî-
÷óþ ïîäìàòðèöó ìàòðèöû M . Ðàáî÷àÿ ìàòðèöà íå ñîäåðæèò ñòðîê è ñòîëáöîâ,
ñîîòâåòñòâóþùèõ âåðøèíàì ìíîæåñòâà V V R V L\ ( ( ) ( ))
. Â ðåçóëüòàòå ïðèâå-
äåíèÿ ðàáî÷åé ìàòðèöû íàõîäèòñÿ ðàáî÷àÿ ïðèâåäåííàÿ ìàòðèöà M RL .
Ïóñòü âåòâëåíèå èíèöèèðóåò ïóòü, ñîäåðæàùèé íåñêîëüêî äóã. Òîãäà íà-
÷àëüíàÿ è êîíå÷íàÿ âåðøèíû ïóòè ïðèíàäëåæàò ìíîæåñòâó V R V L( ) ( )
, à åãî
ïðîìåæóòî÷íûå âåðøèíû — ìíîæåñòâó V V R V L\ ( ( ) ( ))
. Äåéñòâèòåëüíî, íà-
÷àëüíàÿ âåðøèíà ñîîòâåòñòâóåò ñòðîêå ðàáî÷åé ìàòðèöû, êîíå÷íàÿ âåðøèíà —
ñòîëáöó, à ðàáî÷àÿ ìàòðèöà ïîñòðîåíà íà âåðøèíàõ ìíîæåñòâà V R V L( ) ( )
.
Ïðîìåæóòî÷íàÿ âåðøèíà � jl
l k, ,� �2 1 , ïóòè (� j1
, � j2
, …, � jk�1
, � jk
) òðåáóåò
âêëþ÷åíèÿ ñîîòâåòñòâóþùåé åé ñòðîêè è ñòîëáöà â ðàáî÷óþ ìàòðèöó.  äåðåâå
ïåðåáîðà âåðøèíå � jl
ñîîòâåòñòâóåò ìíîæåñòâî ðåøåíèé, ñîäåðæàùèõ ýòó âåð-
øèíó. Êàæäîå òàêîå ìíîæåñòâî ìîæíî ðàññìàòðèâàòü êàê ðàçáèåíèå íà äâà ïîä-
ìíîæåñòâà, îäíî èç êîòîðûõ ñîäåðæèò äóãó ( , )� �j jl l� 1
. Â äåðåâå ïåðåáîðà ïóòü
( , , ..., )� � �j j jk1 2
ïîðîæäàåò k âèñÿ÷èõ âåðøèí X X X Xj j j k jk k1 2 11 2 1, , ..., ,
� � , èñ-
õîäÿùèõ èç âåðøèíû X j1
. Ïðè âåðøèíàõ X j11 è X jk
ðàñøèðåíèå ñîâïàäàåò
ñ ðàñøèðåíèåì V L( ) äëÿ X j1
, à ïðè âåðøèíå X l kj ll
, ,� �2 1 , îíî ðàâíî
V L jl
( )
{ }� .
Ìàòðèöû D ïðè âèñÿ÷èõ âåðøèíàõ ôîðìèðóþòñÿ èç ìàòðèöû D ïðè âåðøè-
íå âåòâëåíèÿ X j1
ñëåäóþùèì îáðàçîì:
1) â ìàòðèöå D äëÿ âåðøèíû X i i kj ii
, ,� �1 , ýëåìåíò ( , )j ji i�1 ïðèíèìàåòñÿ
ðàâíûì áåñêîíå÷íîñòè ;
2) ÷òîáû ïîëó÷èòü ìàòðèöó D ïðè âåðøèíå X jk
, èç ìàòðèöû äëÿ X j1
èñ-
êëþ÷àþòñÿ òå ñòðîêè è ñòîëáöû, ïî êîòîðûì ñòðîèòñÿ ïóòü ( , , ..., )� � �j j jk1 2
;
3) ìàòðèöà D ïðè âåðøèíå X l kj ll
, ,� �2 1 , ñîäåðæèò ñòðîêó, ñîîòâåòñòâóþ-
ùóþ âåðøèíå � jl
, è íå ñîäåðæèò ñòðîê è ñòîëáöîâ, îïðåäåëÿþùèõ ïóòü
( , , ..., )� � �j j jl1 2
.
Ìíîæåñòâî V L( ) ôîðìèðóåòñÿ ñîãëàñíî ñëåäóþùåìó ïðàâèëó:
• â êîðíåâîé âåðøèíå ïîëàãàåì V L( ) � ;
• âñå ýëåìåíòû ìíîæåñòâà V L( ) ïåðåäàþòñÿ âåðøèíå, ïîðîæäåííîé âåðøè-
íîé âåòâëåíèÿ;
• åñëè âåòâëåíèå âûçûâàåò ïóòü ( , , , , )s p t� � , âêëþ÷àþùèé k ïðîìå-
æóòî÷íûõ âåðøèí, òî ñîîòâåòñòâóþùåå åìó ìíîæåñòâî ðåøåíèé ñ ðàñøè-
ðåíèåì V L( ) ðàçáèâàåòñÿ íà ïîñëåäîâàòåëüíîñòü èç k �2 ïîäìíîæåñòâ
( , , , , )S P T� � ñ ðàñøèðåíèåì V L( )
{ p} äëÿ ïîäìíîæåñòâà P p s t, ,� ;
â ëþáîì ðåøåíèè ïîäìíîæåñòâà P ñîäåðæèòñÿ ÷àñòü ïóòè ( , , , , )s p t� � èç
âåðøèíû s â âåðøèíó p; êàæäîå ðåøåíèå ïîäìíîæåñòâà T âêëþ÷àåò ïóòü
( , , , , )s p t� � ; âñå ðåøåíèÿ ïîäìíîæåñòâà S íå âêëþ÷àþò ýòîãî ïóòè.
ÏÎÑÒÐÎÅÍÈÅ ÌÀÒÐÈÖÛ ÊÐÀÒ×ÀÉØÈÕ ÏÓÒÅÉ
Äëÿ ïîëó÷åíèÿ ìàòðèöû M äëèí êðàò÷àéøèõ ïóòåé è ìàòðèöû W ìàðøðóòè-
çàöèè èñïîëüçóåòñÿ ìîäèôèêàöèÿ èçâåñòíîãî àëãîðèòìà Ôëîéäà–Óîðøåëëà,
îïðåäåëÿþùåãî â îðèåíòèðîâàííîì ãðàôå êðàò÷àéøèå ïóòè ìåæäó âñåìè ïàðà-
ìè âåðøèí [3].
Âõîä. D — ìàòðèöà ñòîèìîñòåé dij ïîäãðàôà G Q( ) îðèåíòèðîâàííîãî ãðà-
ôà G V E� ( , ) , i j, �{1, 2, …, n}; G Q G( ) � â êîðíåâîé âåðøèíå äåðåâà ïåðåáî-
ðà; R — ìíîæåñòâî ðåáåð, îáðàçóþùèõ ïàðîñî÷åòàíèå èñõîäíîãî ãðàôà H ;
114 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5
Q — ìíîæåñòâî çàïðåùåííûõ äóã â âåðøèíå âåòâëåíèÿ, Q � , ïîñêîëüêó
G Q G( ) � ; V R( ) — ìíîæåñòâî âåðøèí, èíöèäåíòíûõ ðåáðàì ïàðîñî÷åòàíèÿ R;
V L( ) — ðàñøèðåíèå ìíîæåñòâà âåðøèí â òî÷êå âåòâëåíèÿ,V L( ) � â êîðíå äåðå-
âà ïåðåáîðà; I row, I col — ìíîæåñòâî èíäåêñîâ ñîîòâåòñòâåííî ñòðîê è ñòîëáöîâ
ìàòðèöû D ïîðÿäêà | | | |I Irow col� , n — ïîðÿäîê ìàòðèöû D â êîðíåâîé âåðøèíå.
Âûõîä. M — ìàòðèöà äëèí mij êðàò÷àéøèõ ïóòåé ( , , , , )i k l j� , i, j V R� ( ),
k, l V R� ( ) , {i j, }�R ;
W — ìàòðèöà êðàò÷àéøèõ ïóòåé wij , ñîîòâåòñòâóþùàÿ Ì .
Ïîäãîòîâèòåëüíûé ýòàï:
10 . for all i I row� do
20 . for all j I col� do
30 . begin
40 . w
i j m
j i j mij
ij
ij
�
� � � �
�
�
�
�
�
, åñëè èëè
, åñëè è
,
50 . m dij ij�
60 . end
Ýòàï íàõîæäåíèÿ ýëåìåíòîâ ìàòðèö M è W :
1. for all k I col� do
2. if k V R V L�
( ) ( ) then
3. for all i I row� do
4. for all j I col� do
5. if i j� and i k� and j k� then begin
6. if {i j, } �R then continue
7. if (i j, ) �Q then continue
8. if m m mij ik kj� � then
9. begin
10. m m mij ik kj� �
11. w kij �
12. end
13. end
ÍÈÆÍÈÅ ÃÐÀÍÈÖÛ ÑÒÎÈÌÎÑÒÈ ÊÎËÜÖÅÂÛÕ ÌÀÐØÐÓÒÎÂ
Íèæíÿÿ îöåíêà ñòîèìîñòè ðåøåíèé îïðåäåëÿåòñÿ èç ïîäìàòðèöû M RL ðàáî-
÷åé ìàòðèöû M .  ìàòðèöó M , ïîëó÷åííóþ èç ìàòðèöû D ìîäèôèöèðîâàí-
íûì àëãîðèòìîì Ôëîéäà–Óîðøåëëà, âêëþ÷åíû âñå ñòðîêè ñ èíäåêñàìè
ìíîæåñòâà I row è âñå ñòîëáöû ñ èíäåêñàìè ìíîæåñòâà I col , | | | |I Irow col� ,
I row, I col � {1, 2, …, n}. Ìàòðèöà M RL ñîñòîèò èç òåõ ýëåìåíòîâ, êîòîðûå
ïðèíàäëåæàò ñòðîêàì I V R V Lrow �
( ( ) ( )) è ñòîëáöàì I V R V Lcol �
( ( ) ( )) .
Äëÿ íàõîæäåíèÿ íèæíåé îöåíêè âûïîëíÿåòñÿ ïðèâåäåíèå ìàòðèöû M RL,
âêëþ÷àþùåå òàêèå äåéñòâèÿ:
1) íàéòè â êàæäîé ñòðîêå ìèíèìàëüíûé ýëåìåíò gi è âû÷åñòü åãî èç êàæäîãî
ýëåìåíòà ýòîé ñòðîêè;
2) èñêëþ÷èòü èç ðàññìîòðåíèÿ âñå ñòðîêè, ñîîòâåòñòâóþùèå âåðøèíàì ìíî-
æåñòâà V L( ) , â êàæäîì ñòîëáöå ïîëó÷åííîé ïîäìàòðèöû íàéòè ìèíèìàëüíûé
ýëåìåíò h j è âû÷åñòü åãî èç êàæäîãî ýëåìåíòà ýòîãî ñòîëáöà;
3) â ïîëó÷åííîé ìàòðèöå äëÿ ýëåìåíòîâ ( , )i j è ( , )j i , {i j, }�R , îïðåäå-
ëèòü îöåíêó � ij ij jim m� � �min { }, è ïîëîæèòü
� � � �m mij ij ij� , åñëè � � �mij , è � � � �m mji ji ij� , åñëè � � �m ji .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 115
Ïóñòü Et — ñîâîêóïíîñòü âñåõ äóã ëþáîãî ðåøåíèÿ èç ïîäìíîæåñòâà ðåøå-
íèé, ïðåäñòàâëåííîãî òî÷êîé âåòâëåíèÿ t . Îöåíêà ñíèçó â òî÷êå t îïðåäåëÿåòñÿ
ïî ôîðìóëå
� t i
i I V R V L
j
j I V R
ij
i j R
g h
row col
� � �
� �
� � �
� �
( ( ) ( )) ( ) ,
�
{ }
( , )
( , )
( , )
i j E
j i E
ij
i j E
t
t
t
d
�
�
�
� �� . (1)
Ïåðâûå äâà ñëàãàåìûõ â ôîðìóëå (1) ïîçâîëÿþò îöåíèòü ñòîèìîñòü ìàðøðó-
òîâ àíàëîãè÷íî, êàê è â ìåòîäå Ëèòòëà. Òðåòüå ñëàãàåìîå óâåëè÷èâàåò íè-
æíþþ ãðàíèöó, èñõîäÿ èç èñêîìîãî ðåøåíèÿ, êîòîðîå äîëæíî ñîäåðæàòü îäíó
èç äóã: ( , )i j èëè ( , )j i , {i j, } �R, íå âêëþ÷åííóþ â Et .
Åñëè ïîäìíîæåñòâî ðåøåíèé, îïðåäåëÿåìîå òî÷êîé âåòâëåíèÿ t, ïóñòî, òî
îöåíêà � t ðàâíà áåñêîíå÷íîñòè.  ýòîì ñëó÷àå õîòÿ áû îäèí èç ýëåìåíòîâ gi èëè
h j òàêæå ðàâåí áåñêîíå÷íîñòè.
ÀËÃÎÐÈÒÌ ÏÎÈÑÊÀ ÎÏÒÈÌÀËÜÍÎÃÎ ÐÅØÅÍÈß ÇÀÄÀ×È
Àëãîðèòì ïîèñêà ðåøåíèÿ ÊÇÑÏ ñòðîèò îïòèìàëüíîå ðåøåíèå íà íåïóñòîì
ìíîæåñòâå åå äîïóñòèìûõ ðåøåíèé èëè óòâåðæäàåò, ÷òî äëÿ äàííîãî ãðàôà H
íå ñóùåñòâóåò ïðîñòûõ öèêëîâ, ïðîõîäÿùèõ ïî âñåì ðåáðàì ìíîæåñòâà R,
| |R �1. Ïðè | |R �1 ÊÇÑÏ óïðîùàåòñÿ äî çàäà÷è íàõîæäåíèÿ â ãðàôå H êðàò÷àé-
øåé öåïè ( p , …, q), ñîåäèíÿþùeé âåðøèíû { p , q} �R . Èñêîìûì ðåøåíèåì çà-
äà÷è ÿâëÿåòñÿ öèêë ( p , …, q , p) ñòîèìîñòüþ Lpq + d pq , ãäå Lpq — äëèíà êðàò-
÷àéøåé öåïè ( p , …, q). Èçâåñòíî, ÷òî åå ìîæíî ïîñòðîèòü çà âðåìÿ O n( )2 [3].
Ïðè èçëîæåíèè àëãîðèòìà ïîèñêà y R* ( ) ïðåäïîëàãàåòñÿ, ÷òî óäàëåíèå ñòðî-
êè (ñòîëáöà) â èñõîäíîé èëè ñôîðìèðîâàííîé ìàòðèöå ñîñòîèò â ïðèñâîåíèè
áåñêîíå÷íîñòè êàæäîìó ýëåìåíòó ýòîé ñòðîêè (ñòîëáöà). Èçëîæèì ýòî.
S0. Ìàòðèöà ñòîèìîñòåé [ ]dij n èìååò îðãðàô G = (V , E), | |V n� , n � 4, ïîñòðî-
åííûé èç ñâÿçíîãî ãðàôà H = (V , U ), E U� | |2 ; åñëè {i , j} �U , òî (i , j), ( j , i) �E ;
ãðàô H íå ñîäåðæèò ìîñòîâ è òî÷åê ñî÷ëåíåíèÿ è ñòåïåíè âñåõ åãî âåðøèí áîëü-
øå äâóõ; d Zij � �
0
, åñëè (i , j) �E , èíà÷å dij = � ; Z
0
� — ìíîæåñòâî öåëûõ íåîòðè-
öàòåëüíûõ ÷èñåë;
— R ïðåäñòàâëÿåò íåïóñòîå ìíîæåñòâî çàôèêñèðîâàííûõ ðåáåð, îáðàçóþ-
ùèõ â H ïàðîñî÷åòàíèå, | |R �1;
— V (R) åñòü ìíîæåñòâî âåðøèí, èíöèäåíòíûõ ðåáðàì R ;
— Q ÿâëÿåòñÿ ìíîæåñòâîì äóã, çàïðåùàþùèõ îáðàçîâàíèå öèêëîâ, êîòîðûå
íå ÿâëÿþòñÿ äîïóñòèìûìè ðåøåíèÿìè y(R), Q = ;
— V (L) ïðåäñòàâëÿåò ðàñøèðåííîå ìíîæåñòâî âåðøèí V (R), V (L) = ;
— ïîëîæèòü D dij n� [ ] ; â äåðåâå ïåðåáîðà ìàòðèöå D ñîîòâåòñòâóåò êîðíå-
âàÿ âåðøèíà;
— ïîëîæèòü Rec = � .
S1. Äëÿ ìàòðèöû D âûïîëíèòü ìîäèôèöèðîâàííûé àëãîðèòì Ôëîéäà–Óîð-
øåëëà è â ðåçóëüòàòå ïîëó÷èòü ìàòðèöó äëèí êðàò÷àéøèõ ïóòåé M è ìàòðèöó
ìàðøðóòèçàöèè W.
S2. Èç ìàòðèöû M âûäåëèòü ðàáî÷óþ ïîäìàòðèöó è ïðåîáðàçîâàòü åå â ïðè-
âåäåííóþ ðàáî÷óþ ìàòðèöó M RL, êîòîðàÿ âêëþ÷àåò ýëåìåíòû ìàòðèöû M , ïðè-
íàäëåæàùèå ñòðîêàì ñ èíäåêñàìè âåðøèí èç ìíîæåñòâà I row � (V (R)
V (L)) è
ñòîëáöàì ñ èíäåêñàìè âåðøèí èç ìíîæåñòâà I col �V (R); I row, I col — ìíîæåñòâà
èíäåêñîâ ñîîòâåòñòâåííî ñòðîê è ñòîëáöîâ ìàòðèöû M .
S3.  ïðèâåäåííîé ðàáî÷åé ìàòðèöå M RL äëÿ âñåõ ýëåìåíòîâ � �mpq 0, p , q �
V (R)
V (L), íàéòè îöåíêó
� ( , )p q m m
i q
pi
j p
jq� � � �
� �
min min , i, j �
V R V L( ) ( ) (2)
è îïðåäåëèòü ìàêñèìàëüíóþ âåëè÷èíó èç íèõ �( , ) max ( , )|p q p q mpq� � �{ }� 0 ;
116 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5
— ïî ìàòðèöå ìàðøðóòèçàöèè W óñòàíîâèòü êðàò÷àéøèé ïóòü (k , l) èç âåð-
øèíû k â âåðøèíó l .
S4. Åñëè {k , l} �R, òî ìíîæåñòâî ðåøåíèé ðàçáèâàåòñÿ íà äâà ïîäìíîæåñ-
òâà: ïåðâîå ïîäìíîæåñòâî âêëþ÷àåò ìàðøðóòû, ïðîõîäÿùèå ïî äóãå (k , l), à âòî-
ðîå — ìàðøðóòû, ïðîõîäÿùèå ïî äóãå (l , k); â äåðåâå âåòâëåíèÿ ðàçáèåíèå ïî-
ðîæäàåò äâå âèñÿ÷èå âåðøèíû;
— ïîëó÷èòü èç ìàòðèöû D äâå ïîäìàòðèöû: D� — èñêëþ÷åíèåì ñòðîêè k è
ñòîëáöà l ; ��D — èñêëþ÷åíèåì ñòðîêè l è ñòîëáöà k ;
— ïîëîæèòü D D� � è D D� �� ñîîòâåòñòâåííî äëÿ ïåðâîãî è âòîðîãî ïîä-
ìíîæåñòâà ðàçáèåíèÿ;
— ïðèìåíèòü äëÿ êàæäîãî ïîäìíîæåñòâà ðàçáèåíèÿ ïðàâèëà ôîðìèðîâàíèÿ
çàïðåùåííûõ äóã Q ;
— â ìàòðèöå D ïðè êàæäîì ïîäìíîæåñòâå ïîëîæèòü ðàâíûìè áåñêîíå÷íî-
ñòè âñå ýëåìåíòû, ñîîòâåòñòâóþùèå çàïðåùåííûì â íåì äóãàì;
— âûïîëíèòü øàãè S1 è S2 äëÿ ïîëó÷åííûõ ìàòðèö;
— â ïîäìíîæåñòâàõ ðàçáèåíèÿ îöåíèòü ñòîèìîñòè ðåøåíèé ïî ôîðìóëå (2);
— äëÿ îáîèõ ïîäìíîæåñòâ âûïîëíèòü ïðîâåðêó: åñëè ðàçìåðíîñòü ìàòðèöû
M RL ìåíüøå òðåõ è îöåíêà ìåíüøå Rec , òî îáíîâèòü çíà÷åíèå Rec è çàïîìíèòü
ñîîòâåòñòâóþùåå ðåøåíèå, ïðåòåíäóþùåå íà îïòèìàëüíîå; â ïðîòèâíîì ñëó÷àå
äîáàâèòü âèñÿ÷óþ âåðøèíó ê äåðåâó âåòâëåíèé;
— ïåðåéòè ê øàãó S7.
S5. Åñëè (k , l) �E , {k , l} �R , òî ìíîæåñòâî ðåøåíèé âêëþ÷àåò ïîäìíîæåñòâî
ìàðøðóòîâ, ñîäåðæàùèõ äóãó (k , l), è ïîäìíîæåñòâî, â êîòîðîì ýòà äóãà îòñóòñòâóåò;
— îïðåäåëèòü äëÿ ïåðâîãî ïîäìíîæåñòâà ìàòðèöó D� ñëåäóþùèì îáðàçîì:
åñëè ñóùåñòâóåò ðåáðî {x , k} �R, à â ìàòðèöå D ïðè âåðøèíå âåòâëåíèÿ ýëåìåíò
(x , k) íå ðàâåí áåñêîíå÷íîñòè, òî ïîëó÷èòü ïóòü (x, k, l) è óäàëèòü èç D ñòðîêó x ,
ñòîëáåö l , ñòðîêó è ñòîëáåö k ; åñëè ñóùåñòâóåò ðåáðî {l, y} �R è â ìàòðèöå D
ýëåìåíò (l , y) íå ðàâåí áåñêîíå÷íîñòè, òî ïîëó÷èòü ïóòü (k, l , y) è óäàëèòü èç D
ñòðîêó k, ñòîëáåö y, ñòðîêó l è ñòîëáåö l , åñëè îí íå áûë óäàëåí ðàíåå; óäàëèòü
èç D ñòðîêó k è ñòîëáåö l , åñëè {x , k}, {l , y} �R;
— îïðåäåëèòü äëÿ âòîðîãî ïîäìíîæåñòâà ìàòðèöó ��D , ïîëîæèâ â ìàòðèöå D
ýëåìåíò (k, l) , ðàâíûì áåñêîíå÷íîñòè;
— ïðèìåíèòü äëÿ ïåðâîãî ïîäìíîæåñòâà ïðàâèëî ôîðìèðîâàíèÿ çàïðåùåí-
íûõ äóã, â ìàòðèöå D� ïîëîæèòü ðàâíûìè áåñêîíå÷íîñòè ýëåìåíòû, ñîîòâåòñòâó-
þùèå çàïðåùåííûì äóãàì Q;
— ïîëîæèòü D D� � è âûïîëíèòü øàãè S1 è S2;
— ïî ôîðìóëå (2) îïðåäåëèòü íèæíþþ ãðàíèöó ñòîèìîñòè ðåøåíèé, âõîäÿ-
ùèõ â ïåðâîå ïîäìíîæåñòâî;
— åñëè ðàçìåðíîñòü ìàòðèöû M RL ïåðâîãî ïîäìíîæåñòâà ìåíüøå òðåõ è
åãî îöåíêà ìåíüøå Rec , òî îáíîâèòü çíà÷åíèå Rec è çàïîìíèòü ñîîòâåòñòâóþùåå
ðåøåíèå, ïðåòåíäóþùåå íà îïòèìàëüíîå, â ïðîòèâíîì ñëó÷àå äîáàâèòü âèñÿ÷óþ
âåðøèíó ê äåðåâó ïåðåáîðà;
— ïðèìåíèòü äëÿ âòîðîãî ïîäìíîæåñòâà ïðàâèëî ôîðìèðîâàíèÿ çàïðåùåííûõ
äóã; â ìàòðèöå ��D çàïðåòèòü ïåðåõîäû, ñîîòâåòñòâóþùèå çàïðåùåííûì äóãàì;
— ïîëîæèòü D D� �� è âûïîëíèòü øàãè S1 è S2;
— ïî ôîðìóëå (2) íàéòè íèæíþþ îöåíêó ñòîèìîñòè ðåøåíèé âòîðîãî ïîä-
ìíîæåñòâà;
— åñëè îöåíêà ìåíüøå Rec , òî ïðèñîåäèíèòü âèñÿ÷óþ âåðøèíó ê äåðåâó ïå-
ðåáîðà;
— ïåðåéòè ê øàãó S7.
S6. (k , l) = (k , �1 , � 2 , …, � s�1 , � s , …, � r�1 , � r , l) — êðàò÷àéøèé ïóòü èç
âåðøèíû k â âåðøèíó l ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 117
— ïîñòðîèòü ïóòü ( , ( , , ), )� � � � �k ls r1� � � �� � , ãäå
� �
� � �
�
�
�
��
( , ), , ,x k x k R dxkåñëè{ } è
� �
� � �
�
�
�
( , ), , ,l y l y R dlyåñëè{ } è
— ìíîæåñòâî ðåøåíèé ÿâëÿåòñÿ ðàçáèåíèåì íà r �2 ïîäìíîæåñòâà, â êîòî-
ðîì ïåðâîå ïîäìíîæåñòâî ñîäåðæèò ìàðøðóòû, íå âêëþ÷àþùèå äóãè ( , )k �1
ïóòè ( , ( , , ), )� � � � �k ls r1� � � �� � ; êàæäûé ìàðøðóò s-ãî ïîäìíîæåñòâà ïðîõî-
äèò ïî ïóòè ( ,� ( , ))k s� �1 1� � �� è íå ïðîõîäèò ïî äóãå ( , )� �s s�1 ; â ( )r �2 -å ïîä-
ìíîæåñòâî âõîäÿò ìàðøðóòû, âêëþ÷àþùèå ïóòü ( , ( , , ), )� � � � �k ls r1� � � �� � ;
â äåðåâå ïåðåáîðà äîáàâëÿåòñÿ r �2 âèñÿ÷èõ âåðøèí;
— ïðèìåíèòü äëÿ êàæäîãî ïîäìíîæåñòâà ðàçáèåíèÿ ïðàâèëî ôîðìèðîâàíèÿ
çàïðåùåííûõ äóã Q ;
— ïðèìåíèòü ïðàâèëî ôîðìèðîâàíèÿ ìíîæåñòâà V (L) è ïîëó÷èòü â ðåçóëü-
òàòå äëÿ êàæäîãî s-ãî ïîäìíîæåñòâà ðàñøèðåíèå V L s( )
�{ }� 1 , s r� �2 1, , ãäå
V L( ) — ðàñøèðåíèå â ïåðâîì è (r �2)-ì ïîäìíîæåñòâå ðàçáèåíèÿ;
— äëÿ êàæäîãî ïîëó÷åííîãî ïîäìíîæåñòâà íàéòè ìàòðèöû D1, Dr� 2 , Ds,
s r� �2 1, , l = r + 1; ÷òîáû ïîëó÷èòü ìàòðèöó D1, ýëåìåíò ( , )k �1 ìàòðèöû D ïðè
âåðøèíå âåòâëåíèÿ ïîëàãàåòñÿ ðàâíûì áåñêîíå÷íîñòè ; ìàòðèöà Dr� 2 îïðåäåëÿ-
åòñÿ óäàëåíèåì èç D ñòðîê è ñòîëáöîâ, ñîîòâåòñòâóþùèõ ïðîìåæóòî÷íûì âåð-
øèíàì ïóòè ( , ( , , ), )� � � � �k ls r1� � � �� � ; äëÿ íàõîæäåíèÿ ìàòðèöû Ds,
s r� �2 1, , l = r + 1, íåîáõîäèìî, ÷òîáû â ìàòðèöå D ýëåìåíò (� s�1, � s) ïðèíèìàë-
ñÿ ðàâíûì áåñêîíå÷íîñòè è èç D óäàëÿëèñü ñòðîêè è ñòîëáöû, ñîîòâåòñòâóþùèå
ïðîìåæóòî÷íûì âåðøèíàì ïóòè ( , ( , ))� � �k s1 1� � �� ;
— äëÿ âñåõ ïîëó÷åííûõ ïîäìíîæåñòâ âûïîëíèòü ïðîâåðêó: åñëè ðàçìåð-
íîñòü ìàòðèöû M RL ìåíüøå òðåõ è îöåíêà ìåíüøå Rec , òî îáíîâèòü çíà÷åíèå
Rec è çàïîìíèòü ñîîòâåòñòâóþùåå ðåøåíèå, ïðåòåíäóþùåå íà îïòèìàëüíîå, èíà-
÷å ïðèñîåäèíèòü âèñÿ÷óþ âåðøèíó ê äåðåâó âåòâëåíèé;
— ïåðåéòè ê øàãó S7.
S7. Åñëè ãðàíèöà Rec îáíîâëåíà, òî ïðîñìîòðåòü âñå âèñÿ÷èå âåðøèíû äåðå-
âà âåòâëåíèé è óäàëèòü òå èç íèõ, îöåíêà êîòîðûõ áîëüøå èëè ðàâíà Rec ;
— åñëè äåðåâî âåòâëåíèé íå ñîäåðæèò âèñÿ÷èõ âåðøèí, òî ïðîöåññ ðåøåíèÿ
çàâåðøåí è ïåðåõîä ê øàãó S8, èíà÷å âûáðàòü âèñÿ÷óþ âåðøèíó, èìåþùóþ íàè-
ìåíüøóþ îöåíêó, è ïåðåéòè ê øàãó S3;
S8. Åñëè Rec ðàâíî áåñêîíå÷íîñòè, òî ìíîæåñòâî ðåøåíèé èñõîäíîé çàäà÷è
ïóñòî, èíà÷å îïòèìàëüíûì ðåøåíèåì çàäà÷è ÿâëÿåòñÿ ðåøåíèå ñî ñòîèìîñòüþ Rec .
ÏÐÈÌÅÐ ÐÅØÅÍÈß ÇÀÄÀ×È
Äëÿ ñâÿçíîãî ãðàôà H V U� ( , ) ÊÇÑÏ è ìàòðèöû âåñîâ åãî ðåáåð [ ]dij n , ïðåäñòàâ-
ëåííûõ íà ðèñ. 1, òðåáóåòñÿ ïîñòðîèòü ïðîñòîé öèêë y*(R) ìèíèìàëüíîé ñòîèìîñòè,
ïðîõîäÿùèé ïî ðåáðàì ìíîæåñòâà R={{1,2}, {3,4}}, èëè óñòàíîâèòü, ÷òî ìíîæåñòâî
ìàðøðóòîâ y R( ) ïóñòî. Æèðíîé ëèíèåé ïîêàçàíû îáÿçàòåëüíûå ðåáðà äëÿ ïîñåùåíèÿ.
118 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5
èíà÷å; èíà÷å;
Ðèñ. 1. Ãðàô H è ìàòðèöà åãî ñòîèìîñòåé
[ ]dij 8 �
1 2 3 4 5 6 7 8
1 � 9 7 7 4 6 3 3
2 9 � 7 7 5 3 � 7
3 7 7 � 3 2 5 � 5
4 7 7 3 � 9 � 9 7
5 4 5 2 9 � 9 2 9
6 6 3 5 � 9 � 2 �
7 3 � � 9 2 2 � 8
8 3 7 5 7 9 � 8 �
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 119
Ãðàô H íå ñîäåðæèò òî÷åê ñî÷ëåíåíèÿ, ìîñòîâ è âåðøèí, ñòåïåíè êîòîðûõ
ìåíüøå òðåõ. Èìååì V (R) = {1, 2, 3, 4}, Q = , V L( ) � . Â êîðíå äåðåâà ïåðå-
áîðà X 0 ïîëàãàåì D dij� [ ]8 , Rec � �. Äëÿ ìàòðèöû D ìîäèôèöèðîâàííûé àëãî-
ðèòì Ôëîéäà–Óîðøåëëà íàõîäèò ìàòðèöó êðàò÷àéøèõ ïóòåé M è ìàòðèöó
ìàðøðóòèçàöèè W :
Èç ìàòðèöû M óäàëèì ñòðîêè è ñòîëáöû, ñîîòâåòñòâóþùèå âåðøèíàì ìíî-
æåñòâà V \(V (R)
V (L)).  ðåçóëüòàòå ïîëó÷èì ðàáî÷óþ ïîäìàòðèöó [ ]mrs 4 :
êîòîðàÿ ïîñëå ïðèâåäåíèÿ ïî ñòðîêàì è ñòîëáöàì ïðåîáðàçóåòñÿ â ïðèâåäåí-
íóþ ðàáî÷óþ ìàòðèöó M mRL rs� �[ ]4 :
Ïî ôîðìóëå (1) âû÷èñëèì îöåíêó � X 0
. Ñóììà ïåðâûõ äâóõ ñëàãàåìûõ â ôîð-
ìóëå ðàâíà 24, òðåòüå ñëàãàåìîå ïðåäñòàâëåíî ñóììîé � 12 12 21 0� � � �min { }m m, è
� 34 � min ,{ �m34 � �m43 0} , à ÷åòâåðòîå ðàâíî íóëþ, ïîñêîëüêó Et � . Ñëåäîâàòåëü-
íî, � X 0
25� .
 ïðèâåäåííîé ðàáî÷åé ìàòðèöå M RL ïî ôîðìóëå (2) íàõîäèì äëÿ êàæäîãî
ýëåìåíòà � �mpq 0 âåëè÷èíó � ( , )p q .  ðåçóëüòàòå ïîëó÷èì � ( , )1 2 1� , � ( , )1 3 0� ,
� ( , )2 1 1� , � ( , )2 3 0� , � ( , )2 4 0� , � ( , )3 4 1� , �(4,3)=1. Îïðåäåëèì îöåíêó �� � � �k l
� � � �max { }� ( , ) |p q mpq 0 1 è ñîîòâåòñòâóþùóþ åé äóãó (1,2) îðãðàôà G V E� ( , ),
{1, 2} �R .
M �
1 2 3 4 5 6 7 8
1 � 9 6 7 4 5 3 3
2 9 � 7 7 5 3 5 7
3 6 7 � 3 2 5 4 5
4 7 7 3 � 9 11 9 7 ,
5 4 5 2 9 � 4 2 9
6 5 3 5 11 4 � 2 10
7 3 5 4 9 2 2 � 8
8 3 7 5 7 9 10 8 �
W �
1 2 3 4 5 6 7 8
1 � (1,2) (1,5,3) (1,4) (1,5) (1,7,6) (1,7) (1,8)
2 (2,1) � (2,3) (2,4) (2,5) (2,6) (2,6,7) (2,8)
3 (3,5,1) (3,2) � (3,4) (3,5) (3,6) (3,5,7) (3,8)
4 (4,1) (4,2) (4,3) � (4,5) (4,7,6) (4,7) (4,8) .
5 (5,1) (5,2) (5,3) (5,4) � (5,7,6) (5,7) (5,8)
6 (6,7,1) (6,2) (6,3) (6,7,4) (6,7,5) � (6,7) (6,7,8)
7 (7,1) (7,6,2) (7,5,3) (7,4) (7,5) (7,6) � (7,8)
8 (8,1) (8,2) (8,3) (8,4) (8,5) (8,7,6) (8,7) �
[ ]mrs 4 �
1 2 3 4
1 � 9 6 7
2 9 � 7 7 ,
3 6 7 � 3
4 7 7 3 �
M RL �
1 2 3 4
1 � 0 0 1
2 0 � 0 0 .
3 1 1 � 0
4 2 1 0 �
Òàê êàê äóãå (1,2) ñîîòâåòñòâóåò â ãðàôå H ðåáðî èç ìíîæåñòâà R , òî âûïîë-
íÿþòñÿ äåéñòâèÿ øàãà S4. Ìíîæåñòâî ðåøåíèé çàäà÷è ðàçáèâàåòñÿ íà ïîäìíî-
æåñòâî ìàðøðóòîâ, âêëþ÷àþùèõ äóãó (1,2), è ïîäìíîæåñòâî ìàðøðóòîâ, ïðîõî-
äÿùèõ ïî äóãå (2,1). Â äåðåâå ïåðåáîðà ðàçáèåíèå îáóñëîâëèâàåò ïîÿâëåíèå äâóõ
âèñÿ÷èõ âåðøèí: X 1, X 2 è ìàòðèö D� è ��D :
Äëÿ ìàòðèöû D� ïðè âåðøèíå X 1 èìååì Q = {(2, 1)}, ïîýòîìó ýëåìåíò (2, 1)
ïðèíèìàåò çíà÷åíèå áåñêîíå÷íîñòè; V (R) = {1, 2, 3, 4}, V (L) = .
Ìîäèôèöèðîâàííûé àëãîðèòì Ôëîéäà–Óîðøåëëà, âõîäîì êîòîðîãî ÿâëÿåò-
ñÿ ìàòðèöà D D� �, ñòðîèò ìàòðèöû M è W :
M �
1 3 4 5 6 7 8
2 � 7 7 5 3 5 7
3 6 � 3 2 5 4 5
4 7 3 � 9 11 9 7
5 4 2 9 � 4 2 9 ,
6 5 5 11 4 � 2 10
7 3 4 9 2 2 � 8
8 3 5 7 9 10 8 �
W �
1 3 4 5 6 7 8
2 � (2,3) (2,4) (2,5) (2,6) (2,6,7) (2,8)
3 (3,5,1) � (3,4) (3,5) (3,6) (3,5,7) (3,8)
4 (4,1) (4,3) � (4,5) (4,7,6) (4,7) (4,8)
5 (5,1) (5,3) (5,4) � (5,7,6) (5,7) (5,8) .
6 (6,7,1) (6,3) (6,7,4) (6,7,5) � (6,7) (6,7,8)
7 (7,1) (7,5,3) (7,4) (7,5) (7,6) � (7,8)
8 (8,1) (8,3) (8,4) (8,5) (8,7,6) (8,7) �
 ìàòðèöå M ïðè âåðøèíå X 1 èìååì I row= {2, 3, 4, 5, 6, 7, 8}, I col = {1, 3, 4,
5, 6, 7, 8}. Ðàáî÷àÿ ïîäìàòðèöà ìàòðèöû M ñîñòîèò èç ýëåìåíòîâ ñòðîê ñ èíäåê-
ñàìè âåðøèí ìíîæåñòâà I row � (V (R)
V (L)) = {2, 3, 4} è ñòîëáöîâ ñ èíäåêñàìè
âåðøèí ìíîæåñòâà I col �V (R) = {1, 3, 4}. Ïîñëå åå ïðèâåäåíèÿ ïî ñòðîêàì è
ñòîëáöàì ïîëó÷èì ìàòðèöó M RL è ïîäìàòðèöó [ ]mrs 3 :
120 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5
�� �D
1 3 4 5 6 7 8
1 � 7 7 4 6 3 3
3 7 � 3 2 5 � 5
4 7 3 � 9 � 9 7
5 5 2 9 � 9 2 9 .
6 3 5 � 9 � 2 �
7 � � 9 2 2 � 8
8 7 5 7 9 � 8 �
D � �
1 3 4 5 6 7 8
2 � 7 7 5 3 � 7
3 7 � 3 2 5 � 5
4 7 3 � 9 � 9 7
5 4 2 9 � 9 2 9 ,
6 6 5 � 9 � 2 �
7 3 � 9 2 2 � 8
8 3 5 7 9 � 8 �
1 3 4 1 3 4
2 � 0 0 2 � 7 7
M RL= 3 1 � 0 , [ ]mrs 3 � 3 6 � 3 .
4 1 0 � 4 7 3 �
Íàéäåì îöåíêó � X 1
, âû÷èñëÿåìóþ ïî ôîðìóëå (1). Ñóììà ïåðâûõ äâóõ ñëà-
ãàåìûõ â � X 1
ðàâíà 16, òðåòüå ñëàãàåìîå � 34 34 43� � �min ,{ }m m äàåò íóëü, à ÷åò-
âåðòîå ñëàãàåìîå — âåñ d12 9� äëÿ äóãè (1, 2). Ñëåäîâàòåëüíî, � X 1
25� .
Ïî ìàòðèöå ��D ïðè âåðøèíå X 2 , äëÿ êîòîðîé Q �{(1, 2)}, V (R) = {1, 2, 3, 4},
V (L) = , íàõîäèì ìàòðèöû M è W :
M �
2 3 4 5 6 7 8
1 � 6 7 4 5 3 3
3 7 � 3 2 5 4 5
4 7 3 � 9 11 9 7
5 5 2 9 � 4 2 9 ,
6 3 5 11 4 � 2 10
7 5 4 9 2 2 � 8
8 7 5 7 9 10 8 �
W �
2 3 4 5 6 7 8
1 � (1,5,3) (1,4) (1,5) (1,7,6) (1,7) (1,8)
3 (3,2) � (3,4) (3,5) (3,6) (3,5,7) (3,8)
4 (4,2) (4,3) � (4,5) (4,7,6) (4,7) (4,8)
5 (5,2) (5,3) (5,4) � (5,7,6) (5,7) (5,8) .
6 (6,2) (6,3) (6,7,4) (6,7,5) � (6,7) (6,7,8)
7 (7,6,2) (7,5,3) (7,4) (7,5) (7,6) � (7,8)
8 (8,2) (8,3) (8,4) (8,5) (8,7,6) (8,7) �
Ïîñêîëüêó I row � (V (R)
V (L)) = {1, 3, 4}, I col �V (R) = {2, 3, 4}, òî
2 3 4 2 3 4
1 � 6 7 1 � 0 1
[ ]mrs 3 = 3 7 � 3 , M RL � 3 0 � 0 , � X d
2
12 4 0 16 9 2512� � � � � � � .
4 7 3 � 4 0 0 �
Âûáåðåì âåðøèíó X 1 òî÷êîé âåòâëåíèÿ.  ñîîòâåòñòâóþùåé åé ìàòðèöå
M RL èìååì îöåíêè � ( , )2 3 0� , � ( , )2 4 0� , � ( , )3 1 1� , � ( , )3 4 0� , � ( , )4 3 1� ,
�( , )3 1 1� . Âåòâëåíèå èíèöèèðóåò ýëåìåíò (3,1), êîòîðûé â ìàòðèöå ìàðøðóòèçà-
öèè W ïðåäñòàâëÿåò ïóòü (3,5,1). Ïîýòîìó âûïîëíÿþòñÿ äåéñòâèÿ øàãà S6.
Òàê êàê {3, 4} �R , d43� � , òî � = (4, 3), îäíàêî � � , ïîñêîëüêó ðåáðî
{1, 2} �R èìååò â ìàòðèöå D� âåñ d12 � � . Ïîëó÷åí ïóòü (4, 3, 5, 1), êîòîðûé âû-
çûâàåò ðàçáèåíèå ìíîæåñòâà ðåøåíèé, ïðåäñòàâëåííîãî âåðøèíîé X 1, íà òðè
ïîäìíîæåñòâà: X 3 , X 4 , X 5 . Âñå ìàðøðóòû â X 3 íå âêëþ÷àþò äóãè (3, 5), â X 4
âñå ìàðøðóòû âêëþ÷àþò äóãè (4, 3), (3, 5), à â X 5 âêëþ÷åíû ìàðøðóòû, ïðîõîäÿ-
ùèå ïî äóãàì (4, 3), (3, 5), (5, 1). Íà ðèñ. 2 ïîêàçàíî äåðåâî ïåðåáîðà, â êîòîðîå
äîáàâëÿþòñÿ òðè âåðøèíû, èñõîäÿùèå èç òî÷êè âåòâëåíèÿ X 1. Æèðíîé ëèíèåé èçî-
áðàæåí ïóòü èç êîðíÿ äåðåâà ê ìíîæåñòâó, ïðåäñòàâëÿþùåìó îïòèìàëüíîå ðåøåíèå
çàäà÷è. ×åðòà íàä äóãàìè îçíà÷àåò çàïðåò ïåðåõîäà ïî ñîîòâåòñòâóþùåé äóãå.
Äëÿ ìíîæåñòâà ìàðøðóòîâ X 3 , íå âêëþ÷àþùèõ äóãè (3,5), èìååì ìíîæåñò-
âî Q = {(2,1)}, V (R) = {1, 2, 3, 4}, V ( L) = , ýëåìåíòû d35 � �, d21 � �, à òàêæå
ìàòðèöû D, M , W, M RL:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 121
M �
1 3 4 5 6 7 8
2 � 7 7 5 3 5 3
3 7 � 3 9 5 7 5
4 7 3 � 9 11 9 7
5 4 2 9 � 4 2 9 ,
6 5 5 11 4 � 2 10
7 3 4 9 2 2 � 8
8 3 5 7 9 10 8 �
D �
1 3 4 5 6 7 8
2 � 7 7 5 3 � 7
3 7 � 3 � 5 � 5
4 7 3 � 9 � 9 7
5 4 2 9 � 9 2 9 ,
6 6 5 � 9 � 2 �
7 3 � 9 2 2 � 8
8 3 5 7 9 � 8 �
è îöåíêó � X 3
26� .
Ìíîæåñòâî ìàðøðóòîâ X 4 , ïðîõîäÿùèõ ïî äóãàì (4,3), (3,5) è íå âêëþ÷àþ-
ùèõ äóãè (5,1), ôîðìèðóåò Q = {(2,1), (5,4)}, V (R) = {1, 2, 3, 4}, V (L) = {5},
d21 � �, d54 � � , d51 � � , à òàêæå
1 4 6 7 8 1 4 6 7 8
D =
2 � 7 3 � 7 2 � 7 3 5 7
5 � � 9 2 9 5 5 � 4 2 9
6 6 � � 2 � , M= 6 5 11 � 2 10 ,
7 3 9 2 � 8 7 3 9 2 � 8
8 3 7 � 8 � 8 3 7 10 8 �
Ïîñëå ïðèâåäåíèÿ ïîäìàòðèöû [ ]mrs 2 ïîëó÷èì ìàòðèöó
è îöåíêó � X d d d
4
7 5 2612 43 35� � � � � � .
122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5
Ðèñ. 2. Äåðåâî ïåðåáîðà
1 4
MRL =
2 � 0
5 0 �
1 4 6 7 8
2 � (2,4) (2,6) (2,6,7) (2,8)
,
5 (5,7,1) (5,4) (5,7,6) (5,7) (5,8)
W= 6 (6,7,1) (6,7,4) � (6,7) (6,7,8)
7 (7,1) (7,4) (7,6) � (7,8)
8 (8,1) (8,4) (8,7,6) (8,7) �
1 4
[ ]mrs 2 �
2 � 7
.
5 5 �
W �
1 3 4 5 6 7 8
2 � (2,3) (2,4) (2,5) (2,6) (2,6,7) (2,8)
,
3 (3,1) � (3,4) (3,6,7,5) (3,6) (3,5,7) (3,8)
4 (4,1) (4,3) � (4,5) (4,7,6) (4,7) (4,8)
5 (5,1) (5,3) (5,4) � (5,7,6) (5,7) (5,8)
6 (6,7,1) (6,3) (6,7,4) (6,7,5) � (6,7) (6,7,8)
7 (7,1) (7,5,3) (7,4) (7,5) (7,6) � (7,8)
8 (8,1) (8,3) (8,4) (8,5) (8,7,6) (8,7) �
1 3 4
2 � 0 0
M RL= 3 0 � 0
4 0 0 �
,
Äëÿ ìíîæåñòâà ìàðøðóòîâ X 5 , ïðîõîäÿùèõ ïî äóãàì (4, 3), (3, 5), (5, 1),
èìååì Q = {(2,1)}, V (R) ={1, 2, 3, 4}, V (L) = , d24 = � ,
4 6 7 8 4 6 7 8 4 6 7 8
2 7 3 � 7 2 7 3 5 7 2 (2,4) (2,6) (2,6,7) (2,8) 4
D = 6 � � 2 � , M= 6 1 � 2 10 , W= 6 (6,7,4) � (6,7) (6,7,8) , MRL = 2 0 .
7 9 2 � 8 7 9 2 � 8 7 (7,4) (7,6) � (7,8)
8 7 � 8 � 8 7 10 8 � 8 (8,4) (8,7,6) (8,7) �
Ðàáî÷àÿ ïîäìàòðèöà M RL ñîñòîèò èç îäíîãî ýëåìåíòà: (2,4). Oòñþäà ñëåäó-
åò, ÷òî ïîëó÷åíî äîïóñòèìîå ðåøåíèå çàäà÷è.  ìàòðèöå W ýëåìåíò (2,4) ïðåä-
ñòàâëåí äóãîé (2,4) ñòîèìîñòüþ d24 7� . Ñòîèìîñòü ðåøåíèÿ, ñîäåðæàùåãî äóãè
(1,2), (2,4), (4,3), (3,5), (5,1), ðàâíà íèæíåé ãðàíèöå � X 5
� d d d d12 43 35 51� � � �
� �d24 9 + 3 + 2 + 4 + 7 = 25. Ïîñêîëüêó çíà÷åíèå Rec X� �
5
, òî Rec X� ��
5
25.
Îöåíêà � X 5
ÿâëÿåòñÿ íàèìåíüøåé èç âñåõ îöåíîê âèñÿ÷èõ âåðøèí äåðåâà ïåðå-
áîðà. Ñëåäîâàòåëüíî, y*(R) = (1, 2, 4, 3, 5, 1), C( y*(R)) = 25.
Òàêèì îáðàçîì, â ñòàòüå ñôîðìóëèðîâàíà îãðàíè÷åííàÿ âåðñèÿ èçâåñòíîé çà-
äà÷è (êîëüöåâîé çàäà÷è) î ñåëüñêîì ïî÷òàëüîíå. Ïðåäëîæåí ìåòîä åå ðåøåíèÿ,
ðàçâèâàþùèé êëàññè÷åñêèé àëãîðèòì âåòâåé è ãðàíèö äëÿ ðåøåíèÿ çàäà÷è êîì-
ìèâîÿæåðà (àëãîðèòì Ëèòòëà). Ðàçðàáîòàííûé ìåòîä ìîæåò áûòü òàêæå ïðèìå-
íåí äëÿ ðåøåíèÿ ãàìèëüòîíîâîé çàäà÷è î ñåëüñêîì ïî÷òàëüîíå è ãàìèëüòîíîâîé
çàäà÷è êîììèâîÿæåðà.
Àâòîðû âûðàæàþò áëàãîäàðíîñòü ïðîôåññîðó Àíàòîëèþ Âàñèëüåâè÷ó Ïàíè-
øåâó çà öåííûå çàìå÷àíèÿ è ïîìîùü â ðàáîòå.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ì î ð î ç î â À .  . , Ï à í è ø å â À .  . Âåðøèííî-ðåáåðíîå ïðåîáðàçîâàíèå â ãàìèëüòîíîâîé çàäà÷å
î ñåëüñêîì ïî÷òàëüîíå // Èñêóññòâåí. èíòåëëåêò. — 2009. — Âûï. 3. — Ñ. 138–143.
2. ß á ë î í ñ ê è é À . À . Ìèíèìèçàöèÿ êîëüöåâûõ ìàðøðóòîâ äîñòàâêè ïðîäóêöèè ïîòðåáèòåëÿì // Ýêî-
íîìèêà è ìàò. ìåòîäû. — 2006. — 43, ¹ 3. — C. 124–131.
3. Ê î ñ ò ³ ê î â à Ì .  . , Ï à í ³ ø å â À .  . , Ï ë å ÷ è ñ ò è é Ä . Ä . Âóçëîâ³ ïèòàííÿ çàäà÷³ êîì³âîÿæå-
ðà. 2 // ³ñíèê Æèòîìèð. äåðæ. òåõíîëîã³÷. óí-òó. Òåõí. íàóêè. — 2004. — ¹ 30. — Ñ. 99–108.
4. Ê î ð ì å í Ò . , Ë å é ç å ð ñ î í × . , Ð è â å ñ ò Ð . Àëãîðèòìû: ïîñòðîåíèå è àíàëèç. — Ì.: ÌÖÍÌÎ,
2001. — 960 ñ.
Ïîñòóïèëà 29.01.2013
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 123
|
| id | nasplib_isofts_kiev_ua-123456789-86276 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-02T07:26:53Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Овезгельдыев, А.О. Морозов, А.В. 2015-09-11T20:10:42Z 2015-09-11T20:10:42Z 2013 Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута / А.О. Овезгельдыев, А.В. Морозов // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 112-123. — Бібліогр.: 4 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86276 519.161 Побудовано математичну модель прикладної задачі оптимізації замкнених маршрутів — кільцевої задачі про сільського листоношу. Запропоновано двоетапний метод типу гілок та меж, який знаходить розв’язок або встановлює факт нерозв’язності задачі. Перший етап методу включає перевірку достатніх умов нерозв’язності і процедуру вершинно-реберного перетворення. Це дає можливість скоротити час пошуку розв’язку на другому етапі методу за допомогою запропонованої модифікації методу Літтла. У ній вперше застосовано спосіб розбиття множини розв’язків на підмножини, що не перетинаються, за допомогою трьох правил розгалуження і обчисленням відповідних нижніх оцінок вартості оптимального розв’язку. Запропонований метод коректно виконує пошук оптимального розв’язку гамільтонової задачі про сільського листоношу, загальної і гамільтонової задачі комівояжера. A mathematical model of the applied problem of optimization of closed routes, i.e., the rural postman problem, is constructed. A two-stage method of the type of the branch-and-bound one is proposed that finds a solution or establishes the fact of the unsolvability of the problem. The first stage of the method includes the test of sufficient unsolvability conditions and a vertex-edge transformation procedure. This makes it possible to decrease the time of searching for a solution at the second stage of the method with the help of a proposed modification of the Little method. This procedure uses (for the first time) a partition of a solution set into disjoint subsets with the help of three rules of branching and computation of corresponding lower assessed values of an optimal solution. The proposed method correctly searches for an optimal solution of the Hamiltonian rural postman problem and general and Hamiltonian traveling salesman problems. Авторы выражают благодарность профессору Анатолию Васильевичу Панишеву за ценные замечания и помощь в работе. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута Розвиток методу гілок та меж у задачі пошуку оптимального кільцевого маршруту Developing the branch-and-bound method in the problem of searching for an optimal circular route (the Cyclic Rural Postman Problem) Article published earlier |
| spellingShingle | Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута Овезгельдыев, А.О. Морозов, А.В. Системный анализ |
| title | Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| title_alt | Розвиток методу гілок та меж у задачі пошуку оптимального кільцевого маршруту Developing the branch-and-bound method in the problem of searching for an optimal circular route (the Cyclic Rural Postman Problem) |
| title_full | Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| title_fullStr | Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| title_full_unstemmed | Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| title_short | Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| title_sort | развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86276 |
| work_keys_str_mv | AT ovezgelʹdyevao razvitiemetodavetveiigranicvzadačepoiskaoptimalʹnogokolʹcevogomaršruta AT morozovav razvitiemetodavetveiigranicvzadačepoiskaoptimalʹnogokolʹcevogomaršruta AT ovezgelʹdyevao rozvitokmetodugíloktamežuzadačípošukuoptimalʹnogokílʹcevogomaršrutu AT morozovav rozvitokmetodugíloktamežuzadačípošukuoptimalʹnogokílʹcevogomaršrutu AT ovezgelʹdyevao developingthebranchandboundmethodintheproblemofsearchingforanoptimalcircularroutethecyclicruralpostmanproblem AT morozovav developingthebranchandboundmethodintheproblemofsearchingforanoptimalcircularroutethecyclicruralpostmanproblem |