Модификация метода Литтла для решения кольцевой задачи о сельском почтальоне
В статье приведена формулировка и дан анализ обобщения гамильтоновой задачи о сельском почтальоне. Предлагается точный метод её решения, развивающий классический алгоритм Литтла....
Saved in:
| Date: | 2010 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Series: | Штучний інтелект |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/56182 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Модификация метода Литтла для решения кольцевой задачи о сельском почтальоне / А.В. Морозов, А.В. Панишев, В.А. Скачков // Штучний інтелект. — 2010. — № 3. — С. 103-115. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-56182 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-561822025-02-10T00:15:38Z Модификация метода Литтла для решения кольцевой задачи о сельском почтальоне Модифікація методу Літтла для розв’язання кільцевої задачі про сільського листоношу Modification of Little’s Method for Solving the Circular Rural Postman Problem Морозов, А.В. Панишев, А.В. Скачков, В.А. Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем В статье приведена формулировка и дан анализ обобщения гамильтоновой задачи о сельском почтальоне. Предлагается точный метод её решения, развивающий классический алгоритм Литтла. У статті приведено формулювання і аналіз узагальнення гамільтонової задачі про сільського листоношу. Пропонується точний метод її розв’язання, який розвиває класичний алгоритм Літтла. In this paper the formulation and analysis of the generalization of the Hamiltonian Travelling Salesman Problem is described. The exact method of its solving developing classical Little's algorithm is offered. 2010 Article Модификация метода Литтла для решения кольцевой задачи о сельском почтальоне / А.В. Морозов, А.В. Панишев, В.А. Скачков // Штучний інтелект. — 2010. — № 3. — С. 103-115. — Бібліогр.: 3 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/56182 519.161 ru Штучний інтелект application/pdf Інститут проблем штучного інтелекту МОН України та НАН України |
| 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 |
2010 |
| topic_facet |
Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/56182 |
| citation_txt |
Модификация метода Литтла для решения кольцевой задачи о сельском почтальоне / А.В. Морозов, А.В. Панишев, В.А. Скачков // Штучний інтелект. — 2010. — № 3. — С. 103-115. — Бібліогр.: 3 назв. — рос. |
| series |
Штучний інтелект |
| work_keys_str_mv |
AT morozovav modifikaciâmetodalittladlârešeniâkolʹcevoizadačioselʹskompočtalʹone AT paniševav modifikaciâmetodalittladlârešeniâkolʹcevoizadačioselʹskompočtalʹone AT skačkovva modifikaciâmetodalittladlârešeniâkolʹcevoizadačioselʹskompočtalʹone AT morozovav modifíkacíâmetodulíttladlârozvâzannâkílʹcevoízadačíprosílʹsʹkogolistonošu AT paniševav modifíkacíâmetodulíttladlârozvâzannâkílʹcevoízadačíprosílʹsʹkogolistonošu AT skačkovva modifíkacíâmetodulíttladlârozvâzannâkílʹcevoízadačíprosílʹsʹkogolistonošu AT morozovav modificationoflittlesmethodforsolvingthecircularruralpostmanproblem AT paniševav modificationoflittlesmethodforsolvingthecircularruralpostmanproblem AT skačkovva modificationoflittlesmethodforsolvingthecircularruralpostmanproblem |
| first_indexed |
2025-12-02T02:46:29Z |
| last_indexed |
2025-12-02T02:46:29Z |
| _version_ |
1850362919818100736 |
| fulltext |
«Штучний інтелект» 3’2010 103
2М
УДК 519.161
А.В. Морозов, А.В. Панишев, В.А. Скачков
Житомирский государственный технологический университет, Украина
morozov.andriy@gmail.com
Модификация метода Литтла для решения
кольцевой задачи о сельском почтальоне
В статье приведена формулировка и дан анализ обобщения гамильтоновой задачи о сельском почтальоне.
Предлагается точный метод её решения, развивающий классический алгоритм Литтла.
Введение
Далеко не для каждой задачи оптимизации на транспортной сети разработаны
алгоритмы поиска решений, пригодные в реальных ситуациях. Одной из таких задач
является задача о сельском почтальоне, ограниченная версия которой рассматри-
вается в данной статье. Эту версию можно рассматривать как гамильтонову задачу
коммивояжера (ГЗК) с условием, сужающим пространство её решений.
Постановка задачи. Задан связный взвешенный граф ( ),H V U= с множеством
вершин V, |V| = n и множеством рёбер U. Каждому ребру {i, j}∈U приписан вес
0ijd Z +∈ , i j≠ , , 1, i j n= , 0Z + – множество неотрицательных целых чисел. Граф H
полностью определяется симметричной матрицей стоимостей ij n
d , где 0ijd Z +∈ ,
если {i, j}∈U и ijd = ∞ , иначе i j≠ , , 1, i j n= , iid = ∞ , 1, i n= . На множестве U
задано непустое подмножество рёбер R U⊂ .
Требуется найти в графе H простой цикл, включающий каждое ребро R и
имеющий минимальную сумму весов всех рёбер.
В рассматриваемой задаче в отличие от задачи о сельском почтальоне (ЗСП)
искомый цикл должен быть простым. Поставленную задачу назовём кольцевой зада-
чей о сельском почтальоне (КЗСП).
Пусть ( )y R – простой цикл графа H, содержащий все рёбра заданного мно-
жества R. Тогда КЗСП состоит в нахождении простого цикла ( )y R∗ , доставляющего
минимум функционалу
( )( )
{ } ( ),
kl
k l y R
C y R d
∈
= ∑ . (1)
Основная идея метода
Ясно, что КЗСП NP-полна, и только её очень ограниченные частные случаи
эффективно разрешимы.
Из NP-полноты КЗСП следует, что она не поддается эффективным точным ме-
тодам решения, а из того, что множество простых циклов графа, включающих все
рёбра R, может оказаться пустым, вытекает неприменимость эффективных прибли-
женных алгоритмов минимизации (1). Таким образом, единственной приемлемой
Морозов А.В., Панишев А.В., Скачков В.А.
«Искусственный интеллект» 3’2010 104
2М
схемой поиска решения КЗСП является схема сокращения перебора, организованная
по методу ветвей и границ, который остаётся универсальным и мощным инструмен-
том комбинаторной оптимизации.
В представленном здесь методе поиска цикла ( )y R∗ алгоритму ветвей и гра-
ниц предшествует стадия эффективной проверки известных достаточных условий
неразрешимости КЗСП. К ней относится процедура вершинно-рёберного преобразо-
вания (ВРП) исходного графа H в граф со структурными характеристиками, вызы-
вающими выполнение переборного алгоритма [1].
Переборный алгоритм, выполняемый на второй стадии решения КЗСП, пред-
ставляет собой модификацию классического метода Литтла [2], адаптированного для
нахождения цикла ( )y R∗ связного подграфа H = (V, U) исходного подграфа, в кото-
ром: а) степень каждой вершины i V∈ больше 2, б) множество R образует паросоче-
тание, в) нет точек сочленения.
В рассматриваемой модификации, как и в алгоритме Литтла для решения сим-
метричной задачи коммивояжера (ЗК), дерево ветвлений развивается из представ-
ления матрицы стоимостей ij n
d ориентированным графом G = (V, E), полученным
в данном случае из графа H заменой каждого ребра {i, j}∈U парой дуг (i, j) E∈ и
(j, i) E∈ . Решением КЗСП является простой контур минимальной стоимости. Следо-
вательно, модификация алгоритма применима для нахождения решения КЗСП, сфор-
мулированной в терминах ориентированных графов.
В методе решения поставленной задачи корневой вершине X0 дерева перебора
ставится в соответствие матрица стоимостей ij n
D d = исходного графа H, матрица
длин кратчайших путей M и матрица маршрутизации W. После их преобразования
находятся вершины, порождённые на шаге ветвления. Для определения матриц M и
W на каждом шаге ветвления применяется модификация алгоритма Флойда-Уор-
шелла. В совокупности, матрицы D, M и W позволяют выполнять в условиях постав-
ленной задачи все действия, включенные в классический метод Литтла. В приве-
денной версии метода выбор очередной вершины ветвления выполняется по схеме,
изображенной на рис. 1.
Из матриц M и W, формируемых модифицированным алгоритмом Флойда-
Уоршелла для текущих параметров матрицы D, определяется дуга (p, q) или путь из
вершины p в вершину q, инициирующие ветвление.
Условия рассматриваемой задачи требуют формирования множества Q запре-
щенных дуг, т.е. дуг, которые приводят к появлению подконтуров в искомом реше-
нии ( )y R∗ .
В множество 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 .
Модификация метода Литтла для решения кольцевой задачи…
«Штучний інтелект» 3’2010 105
2М
Рисунок 1 − Схема ветвления в методе решения КЗСП
При формировании первого подмножества требуется проверка следующих усло-
вий. Если множество 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:
− для корня X0 дерева перебора Q =∅ ;
− все элементы множества Q при вершине ветвления передаются её порожден-
ной вершине;
− если в любое решение при вершине, порожденной на шаге ветвления, вклю-
чается дуга (k, l), то к множеству Q при этой вершине добавляется дуга (l, k);
− вес каждой дуги в Q принимается равным бесконечности.
Если ветвление вызывает путь из вершины k в вершину l, включающий не ме-
нее двух дуг, то для разбиения множества допустимых решений на непересекающи-
еся подмножества используется правило, которое отличается от правила, применяе-
мого для формирования множества Q. В этом случае результатом разбиения является
множество вершин V(L), представляющее расширение множества активных вершин,
порожденных на предыдущих шагах ветвления.
В корневой вершине и вершине ветвления, для которой процесс разбиения ини-
циирует дуга, V(L) = ∅ . Множество вершин V(R)∪V(L) определяет рабочую под-
матрицу матрицы M. Рабочая матрица не содержит строк и столбцов, соответству-
ющих вершинам множества V\(V(R)∪ V(L)). В результате приведения рабочей матрицы
находится рабочая приведенная матрица MRL.
D – матрица стоимостей
М – матрица длин
кратчайших путей
W – матрица
маршрутизации
МRL – рабочая матрица
Модифицированный алгоритм Флойда-Уоршелла
Выбор дуги или пути,
инициирующего ветвление
Процедура
ветвления
Морозов А.В., Панишев А.В., Скачков В.А.
«Искусственный интеллект» 3’2010 106
2М
Пусть ветвление инициирует путь, содержащий несколько дуг. Тогда началь-
ная и конечная вершины пути принадлежат множеству V(R)∪V(L), а его промежу-
точные вершины – множеству V\(V(R)∪V(L)). Действительно, начальная вершина
соответствует строке рабочей матрицы, конечная вершина – столбцу, а рабочая
матрица построена на вершинах множества V(R)∪V(L). Промежуточная вершина
, 2, 1jlv l k= − пути ( 1jv , 2jv , …, 1jkv
−
, )jkv требует включения соответствующей ей
строки и столбца в рабочую матрицу. В дереве перебора вершине jlv соответствует
множество решений, содержащих эту вершину. Каждое такое множество можно рас-
сматривать как разбиение на два подмножества, одно из которых содержит дугу
( )1j jl lv ,v
+
, а другое не включает её. В дереве перебора путь ( )1 2, , , j j jkv v ... v порож-
дает k висячих вершин 1 2 11 2 1, , , , j j j k jk kX X ... X X−−
, исходящих из вершины 1jX . При
вершинах 11jX и jkX расширение совпадает с расширением V(L) для 1jX , а при вер-
шине , 2, 1j llX l k= − – оно равно V(L) { }jlv∪ .
Матрицы D при висячих вершинах формируются из матрицы D при вершине
ветвления 1jX следующим образом:
1. В матрице D для вершины , , 1j iiX i i k= − элемент ( )1, i ij j + принимается рав-
ным ∞ .
2. Чтобы получить матрицу D для вершины jkX , из матрицы для 1jX исключа-
ются те строки и столбцы, по которым строится путь ( )1 2, , , j j jkv v ... v .
3. Матрица D при вершине , 2, 1j llX l k= − содержит строку, соответствующую
вершине jlv , и не содержит строк и столбцов, определяющих путь ( )1 2, , , j j jlv v ... v .
Множество 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 не включают
этого пути.
Модификация алгоритма Флойда-Уоршелла
Платформой, на которую опираются полученные правила ветвления, служит
модификация известного алгоритма Флойда-Уоршелла, определяющего в ориенти-
рованном графе кратчайшие пути между всеми парами вершин [3]. Модификация
формирует матрицы M и W в каждой точке ветвления в результате выполнения сле-
дующих действий.
Модификация метода Литтла для решения кольцевой задачи…
«Штучний інтелект» 3’2010 107
2М
Вход. D – матрица стоимостей dij подграфа G(Q) ориентированного графа G =
= (V, E), i, j∈{1, 2, …, n}; G(Q) = G в корневой вершине дерева перебора;
R – множество рёбер, образующих паросочетание исходного графа H;
Q – множество запрещённых дуг в вершине ветвления, Q =∅ в случае G(Q) = G;
V(R) – множество вершин, инцидентных рёбрам паросочетания R;
V(L) – расширение множества вершин в точке ветвления; V(L) = ∅ в корне де-
рева перебора;
Irow, Icol – множество индексов соответственно строк и столбцов матрицы D по-
рядка | Irow | = | Icol |, n – порядок матрицы D в корневой вершине;
Выход. M – матрица длин mij кратчайших путей (i, k, …, l, j), i, j∈V(R), k, l∉V(R),
{i, j}∉R;
W – матрица кратчайших путей wij, соответствующая М.
Подготовительный этап:
01 . for all i∈Irow do
02 . for all j∈Icol do
03 . begin
04 .
, если или ,
, если и
ij
ij
ij
i j m
w
j i j m .
∞ = = ∞= ≠ < ∞
05 . mij = dij
06 . end
Этап нахождения элементов матриц M и W:
1. for all k∈Icol do
2. if k∉V(R)∪V(L) then
3. for all i∈Irow do
4. for all j∈Icol 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 mij > mik + mkj then
9. begin
10. mij = mik + mkj
11. wij = k
12. end
13. end
На каждом шаге ветвления множеству Q запрещенных дуг ставится в соответ-
ствие подграф G(Q) ориентированного графа G = (V, E) и его матрица стоимостей D.
В строке 2 алгоритма содержится условие, исключающее возможность прохож-
дения путей через вершины множества V(R)∪V(L), для которого формируется рабо-
чая матрица MRL. Так как в корне дерева перебора V(L)=∅ , то в этом случае MRL яв-
ляется квадратной матрицей порядка |V(R)|.
Строка 6 для каждого ребра {i, j}∈R запрещает построение кратчайшего пути
между вершинами i и j и сохраняет веса дуг (i, j) и (j, i) в матрице D.
Дуги множества Q, запрещенные в процессе ветвления для устранения недо-
пустимых контуров, должны быть запрещены и при формировании матриц M и W.
Морозов А.В., Панишев А.В., Скачков В.А.
«Искусственный интеллект» 3’2010 108
2М
Как и алгоритм Флойда-Уоршелла, предложенная модификация имеет времен-
ную сложность, оцениваемую полиномом третьей степени от размерности входной
матрицы D.
Нижние границы стоимости кольцевых маршрутов
Нижняя оценка стоимости любого решения в данной точке ветвления опреде-
ляется из подматрицы MRL рабочей матрицы M. В матрицу M, полученную из мат-
рицы D модифицированным алгоритмом Флойда-Уоршелла, включены все строки с
индексами множества Irow и все столбцы с индексами множества Icol, | Irow | = | Icol |,
Irow, Icol ⊆ {1, 2, …, n}. Матрица MRL состоит из тех элементов, которые принадлежат
строкам Irow∩ (V(R)∪V(L)) и столбцам Icol∩ (V(R)∪V(L)).
Для нахождения нижней оценки выполняется приведение матрицы MRL, вклю-
чающее такие действия:
1) найти в каждой строке минимальный элемент gi и вычесть его из каждого эле-
мента этой строки;
2) исключить из рассмотрения все строки, соответствующие вершинам множества
V(L), в каждом столбце полученной подматрицы найти минимальный элемент hj и
вычесть его из каждого элемента этого столбца;
3) в полученной матрице найти те элементы (i, j) и (j, i), {i, j}∈R, для которых
{ }Д min , ij ij jim m′ ′= , и положить
Д , если ij ij ij ijm m m′ ′ ′= − ≠ ∞ , Д , если ji ji ij jim m m′ ′ ′= − ≠ ∞ .
Пусть Et – совокупность всех дуг любого решения из подмножества решений,
представленного точкой ветвления t. Оценка снизу в точке t определяется по формуле:
( ) ( )( ) ( ) { }
( )
( )
( )
t i j ij ij
i I V R V L j I V R i, j R i, j Erow col t
i , j Et
j ,i Et
g h dϕ ∆
∈ ∩ ∪ ∈ ∩ ∈ ∈
∉
∉
= + + +∑ ∑ ∑ ∑ . (2)
Первые два слагаемых в формуле (2) позволяют оценить стоимость маршрутов
так, как и в методе Литтла. Третье слагаемое увеличивает нижнюю границу, исходя из
того, что искомое решение должно содержать какую-либо одну из дуг (i, j) или (j, i),
{i, j} R∈ , не включенную в Et.
Если подмножество решений, определяемое точкой ветвления t, пусто, то оцен-
ка tϕ равна ∞ . В этом случае хотя бы один из элементов gi или hj также равен ∞ .
Метод поиска оптимального решения задачи
Алгоритм поиска ( )y R∗ строит оптимальное решение КЗСП на непустом мно-
жестве её допустимых решений или устанавливает, что для данного графа H не сущест-
вует простых циклов, проходящих по всем рёбрам множества R, |R|>1. При |R| = 1
КЗСП упрощается до задачи нахождения в графе H кратчайшей цепи (p, …, q),
соединяющей вершины {p, q}∈R. Искомым решением задачи является цикл (p, …, q, p)
стоимостью Lpq + dpq, где Lpq – длина кратчайшей цепи (p, …, q). Известно, что её
можно построить за время O(n2) [3].
Модификация метода Литтла для решения кольцевой задачи…
«Штучний інтелект» 3’2010 109
2М
При изложении алгоритма поиска ( )y R∗ предполагается, что удаление строки
(столбца) в исходной или сформированной матрице состоит в присвоении ∞ каж-
дому элементу этой строки (столбца).
S0. ij n
d – матрица стоимостей орграфа G = (V, E), |V| = n, 4n ≥ , построен-
ного из связного графа H = (V, U), |E| = 2|U|; если {i, j}∈U, то (i, j), (j, i)∈E; граф H не
содержит мостов и точек сочленения, и степени всех его вершин больше 2; 0ijd Z +∈ ,
если (i, j)∈E, иначе dij=∞ , 0Z + – множество целых неотрицательных чисел;
R – непустое множество зафиксированных рёбер, образующих в H паросочета-
ние, |R| > 1;
V(R) – множество вершин, инцидентных рёбрам R;
Q – множество дуг, запрещающих образование циклов, которые не являются допус-
тимыми решениями y(R), Q =∅ ;
V(L) – расширение множества вершин V(R), V(L) = ∅ ;
положить ij n
D d = ; в дереве перебора матрице D соответствует корневая вершина;
положить Rec = ∞ ;
S1. Для матрицы D выполнить модифицированный алгоритм Флойда-Уоршелла и
получить в результате матрицу длин кратчайших путей M и матрицу маршрутизации W.
S2. Из матрицы M выделить рабочую подматрицу и преобразовать её в приве-
денную рабочую матрицу MRL, которая включает элементы матрицы M, принадлежа-
щие строкам с индексами вершин из множества Irow∩ (V(R)∪V(L)) и столбцами с ин-
дексами вершин из множества Icol∩V(R); Irow, Icol – множества индексов соответственно
строк и столбцов матрицы M.
S3. В приведенной рабочей матрице MRL для всех элементов 0pqm′ = , p, q∈
∈V(R)∪V(L) найти оценку
( ), min minpi jqi q j p
p q m mγ
≠ ≠
′ ′= + , i, j ( ) ( )V R V L∈ ∪ , (3)
и определить максимальную из них
( ) ( ){ }, max , 0pqГ p q p q mγ ′= = ;
по матрице маршрутизации W установить кратчайший путь (k, l) из вершины k
в вершину l.
S4. Если {k, l}∈R, то множество решений разбивается на два подмножества:
первое подмножество включает маршруты, проходящие по дуге (k, l), а второе –
маршруты, проходящие по дуге (l, k); в дереве ветвления разбиение порождает две
висячие вершины;
получить из матрицы D две матрицы D′ и D′′ : первую исключением строки k и
столбца l, а вторую – исключением строки l и столбца k;
положить D D′= и D D′′= соответственно для первого и второго подмножест-
ва разбиения;
применить для каждого подмножества разбиения правила формирования запре-
щенных дуг Q;
в матрице D при каждом подмножестве положить равными ∞ все элементы,
соответствующие запрещённым в нём дугам;
выполнить шаги S1 и S2 для полученных матриц;
Морозов А.В., Панишев А.В., Скачков В.А.
«Искусственный интеллект» 3’2010 110
2М
в подмножествах разбиения оценить стоимости решений по формуле (2);
для обоих подмножеств выполнить проверку: если размерность матрицы MRL
меньше 3 и оценка меньше 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) определить нижнюю границу стоимости решений, входящих в
первое подмножество;
если размерность матрицы MRL первого подмножества меньше 3 и его оценка
меньше Rec, то обновить значение Rec и запомнить соответствующее решение как
претендент на оптимальное, в противном случае, добавить висячую вершину к дере-
ву перебора;
применить для второго подмножества правило формирования запрещенных дуг; в
матрице D′′ запретить значения элементов, соответствующих запрещенным дугам на ∞ ;
положить D D′′= и выполнить шаги S1 и S2;
по формуле (2) найти нижнюю оценку стоимости решений второго подмножества;
если оценка меньше Rec, то присоединить висячую вершину к дереву перебора;
перейти к шагу S7 ;
S6. (k, l) = (k, v1,v2, …, vs-1, vs, …, vr-1, vr, l) – кратчайший путь из вершины k в
вершину l;
построить путь ( )( )1 s r, k ,v ,...,v ,...,v ,l ,α β , где
( ) { }если и
иначе,
xkx,k , x,k R d ,
,
α
∈ ≠ ∞=
∅
( ) { }если и
иначе;
lyl , y , l , y R d ,
,
β
∈ ≠ ∞=
∅
множество решений является разбиением на r + 2 подмножеств, в котором
первое подмножество содержит маршруты, не включающие дуги ( )1k ,v пути
( )( )1 s r, k ,v ,...,v ,...,v ,l ,α β ; каждый маршрут s-го подмножества проходит по пути ( ,α
( ))1 1sk ,v ,...,v − и не проходит по дуге ( )1s sv ,v− , в ( )2r + -е подмножество входят марш-
руты, включающие путь ( )( )1 s r, k ,v ,...,v ,...,v ,l ,α β ; в дереве перебора добавляется r + 2
висячих вершин;
применить для каждого подмножества разбиения правило формирования
запрещенных дуг Q;
Модификация метода Литтла для решения кольцевой задачи…
«Штучний інтелект» 3’2010 111
2М
применить правило формирования множества V(L) и получить в результате для
каждого s-го подмножества расширение ( ) { }1sV L v −∪ , 2 1s ,r= + , где ( )V L – рас-
ширение в первом, и (r + 2)-м подмножестве разбиения;
для каждого полученного подмножества найти матрицы 1D , 2rD + , sD ,
2 1s ,r= + , l = r + 1; 1) чтобы получить матрицу 1D , элемент ( )1k ,v матрицы D при
вершине ветвления полагается равным ∞ ; 2) матрица 2rD + определяется удалением
из D строк и столбцов, соответствующих промежуточным вершинам пути
( )( )1 s r, k ,v ,...,v ,...,v ,l ,α β ; 3) матрица sD , 2 1s ,r= + , l = r + 1 находится так: а) в мат-
рице D элемент (vs-1, vs) принимается равным ∞ , б) из D удаляются строки и столбцы,
соответствующие промежуточным вершинам пути ( )( )1 1s, k ,v ,...,vα − ;
для всех полученных подмножеств выполнить проверку: если размерность мат-
рицы MRL меньше 3 и оценка меньше Rec, то обновить значение Rec и запомнить соот-
ветствующее решение как претендент на оптимальное, иначе присоединить висячую
вершину к дереву ветвлений;
перейти к шагу S7;
S7. Если была обновлена граница Rec, то просмотреть все висячие вершины дере-
ва ветвлений и удалить те из них, оценка которых больше или равна Rec;
если дерево ветвлений не содержит висячих вершин, то процесс решения завер-
шен, переход к шагу S8, иначе выбрать висячую вершину, имеющую наименьшую
оценку и перейти к шагу S3;
S8. Если Rec равно ∞ , то множество решений исходной задачи пусто, иначе опти-
мальным решением задачи является решение со стоимостью Rec.
Пример
Для связного графа ( )H V ,U= и матрицы весов его рёбер ij n
d , представ-
ленных на рис. 2, требуется построить простой цикл y*(R) минимальной стоимости,
проходящий по рёбрам множества R={{1,2},{3,4}}, или установить, что множество
маршрутов y(R) пусто.
8ijd =
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 ∞
Рисунок 2 − Граф H КЗСП и матрица его стоимостей
Граф H не содержит точек сочленения, мостов и вершин, степени которых
меньше 3. Имеем V(R)={1,2,3,4}, Q =∅ , V(L) =∅ . В корне дерева перебора X0 пола-
гаем
8ijD d = , Rec = ∞ .
1
2
3
4
5
6
7
8
Морозов А.В., Панишев А.В., Скачков В.А.
«Искусственный интеллект» 3’2010 112
2М
Для матрицы D модифицированный алгоритм Флойда-Уоршелла находит матри-
цу кратчайших путей M и матрицу маршрутизации W:
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) ∞
Из матрицы M удалим строки и столбцы, соответствующие вершинам мно-
жества V\(V(R)∪V(L)). В результате получим рабочую подматрицу [ ]4rsm , которая
после приведения по строкам и столбцам преобразуется в приведенную рабочую
матрицу [ ]4RL rsM m′= :
[ ]4rsm =
1 2 3 4
1 ∞ 9 6 7
2 9 ∞ 7 7
3 6 7 ∞ 3
4 7 7 3 ∞
, RLM =
1 2 3 4
1 ∞ 0 0 1
2 0 ∞ 0 0
3 1 1 ∞ 0
4 2 1 0 ∞
.
По формуле (2) вычислим оценку 0Xϕ . Сумма первых двух слагаемых равна 24, тре-
тье слагаемое представлено суммой { }12 12 21Д min 0m ,m′ ′= = и 34Д = { 34min ,m′ }43 0m′ = ,
а четвёртое равно 0, поскольку tE =∅ . Следовательно 0 25Xϕ = .
В приведенной рабочей матрице MRL по формуле (3) находим для каждого элемента
0pqm′ = величину ( )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 , 0 1pqp q | mγ ′= = = и со-
ответствующую ей дугу (1,2) орграфа ( )G V ,E= , {1,2}∈R.
Так как дуге (1,2) соответствует в графе H ребро из R, то выполняются дейст-
вия шага S4. Множество решений задачи разбивается на подмножество маршрутов,
включающих дугу (1,2), и подмножество маршрутов, проходящих по дуге (2,1). В де-
реве перебора разбиение означает появление двух висячих вершин X1, X2 и двух
матриц
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 ∞
, D′′ =
2 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′ при вершине X1 1X Q = {(2,1)}, поэтому элемент (2,1) принима-
ет значение ∞ ; V(R)={1,2,3,4}, V(L)=∅ .
Модифицированный алгоритм Флойда-Уоршелла, входом которого является
матрица D D′= , строит матрицы M и W
Модификация метода Литтла для решения кольцевой задачи…
«Штучний інтелект» 3’2010 113
2М
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 при вершине X1 Irow={2,3,4,5,6,7,8}, Icol={1,3,4,5,6,7,8}. Рабочая
подматрица матрицы M состоит из элементов строк с индексами вершин множества
Irow∩ (V(R)∪V(L))={2,3,4} и столбцов с индексами вершин множества Icol∩V(R)={1,3,4}.
После её приведения по строкам и столбцам получим матрицу
MRL=
1 3 4
2 ∞ 0 0
3 0 ∞ 0
4 1 0 ∞
, [ ]3rsm =
1 3 4
2 ∞ 7 7
3 6 ∞ 3
4 7 3 ∞
.
Найдём оценку 1Xϕ , вычисляемую по формуле (2). Сумма первых двух слага-
емых в 1Xϕ равна 16, третье слагаемое { }34 34 43min m ,m∆ ′ ′= даёт 0, а четвёртое – вес
12 9d = для дуги (1,2). Следовательно 1 25Xϕ = .
По матрице D′′ при вершине X2, для которой Q={(1,2)}, V(R)={1,2,3,4}, V(L)=∅ ,
находим матрицы
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) ∞
.
Поскольку Irow∩ (V(R)∪V(L))={1,3,4}, Icol∩V(R)={2,3,4}, то
[ ]3rsm =
2 3 4
1 ∞ 6 7
3 7 ∞ 3
4 7 3 ∞
, MRL=
2 3 4
1 ∞ 0 1
3 0 ∞ 0
4 0 0 ∞
, 122 12 4 0 16 9 25X dϕ = + + + = + = .
Выберем вершину X1 точкой ветвления. В соответствующей ей матрице MRL
оценки γ (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), который вызывает разбиение множест-
ва решений, представленного вершиной X1 на три подмножества X3, X4, X5. Каждый
маршрут в X3 не проходит по дуге (3,5), в X4 содержатся все маршруты, включающие
дуги (4,3),(3,5), а в X5 включены маршруты, проходящие по дугам (4,3),(3,5),(5,1). В де-
рево перебора добавляются три вершины, исходящие из точки ветвления 1X (рис. 3).
Для множества маршрутов X3, не включающих дугу (3,5) Q={(2,1)}, V(R) =
= {1,2,3,4}, V(L)=∅ , d35=∞ , d21=∞ ,
Морозов А.В., Панишев А.В., Скачков В.А.
«Искусственный интеллект» 3’2010 114
2М
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 ∞
, M=
1 3 4 5 6 7 8
2 ∞ 7 7 5 3 5 7
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 ∞
,
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,6,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) ∞
, MRL=
1 3 4
2 ∞ 0 0
3 0 ∞ 0
4 0 0 ∞
, 3 26Xϕ = .
Множество маршрутов X4, проходящих по дугам (4,3),(3,5) и не включающих
дугу (5,1), формирует Q={(2,1),(5,4)}, V(R)={1,2,3,4}, V(L)={5}, d21=∞ , d54=∞ , d51=∞ ,
D=
1 4 6 7 8
2 ∞ 7 3 ∞ 7
5 ∞ ∞ 9 2 9
6 6 ∞ ∞ 2 ∞
7 3 9 2 ∞ 8
8 3 7 ∞ 8 ∞
, M=
1 4 6 7 8
2 ∞ 7 3 5 7
5 5 ∞ 4 2 9
6 5 11 ∞ 2 10
7 3 9 2 ∞ 8
8 3 7 10 8 ∞
,W=
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)
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) ∞
, [ ]2rsm =
1 4
2 ∞ 7
5 5 ∞
.
После приведения матрицы [ ]2rsm получим матрицу
MRL=
1 4
2 ∞ 0
5 0 ∞
и оценку 12 43 354 7 5 26X d d dϕ = + + + + = .
Для множества маршрутов X5, проходящих по дугам (4,3),(3,5),(5,1), Q={(2,1)},
V(R)={1,2,3,4}, V(L)=∅ , d24=∞ ,
D=
4 6 7 8
2 7 3 ∞ 7
6 ∞ ∞ 2 ∞
7 9 2 ∞ 8
8 7 ∞ 8 ∞
, M=
4 6 7 8
2 7 3 5 7
6 5 ∞ 2 10
7 9 2 ∞ 8
8 7 10 8 ∞
, W=
4 6 7 8
2 (2,4) (2,6) (2,6,7) (2,8)
6 (6,7,4) ∞ (6,7) (6,7,8)
7 (7,4) (7,6) ∞ (7,8)
8 (8,4) (8,7,6) (8,7) ∞
, MRL=
4
2 0 .
Рабочая подматрица MRL состоит из одного элемента (2,4), отсюда следует,
что получено допустимое решение задачи. В матрице W элемент (2,4) представлен
дугой (2,4) стоимостью d24 = 7. Стоимость решения, содержащего дуги (1,2), (2,4),
(4,3), (3,5), (5,1), равна нижней границе 5Xϕ = d12 + d43 + d35 + d51 + d24 = 9 + 3 + 2 +
+ 4 + 7 = 25. Поскольку значение Rec > 5Xϕ , то 5 25XRec ϕ= = . Оценка 5Xϕ является
наименьшей из всех оценок висячих вершин дерева перебора. Следовательно y*(R)=
= (1,2,4,3,5,1), C(y*(R))=25.
Модификация метода Литтла для решения кольцевой задачи…
«Штучний інтелект» 3’2010 115
2М
Рисунок 3 − Дерево перебора, построенное для данных примера
Выводы
В статье сформулирована ограниченная версия известной задачи о сельском
почтальоне – кольцевая задача о сельском почтальоне. Предложен метод её решения,
развивающий классический алгоритм ветвей и границ для решения задачи ком-
мивояжера (алгоритм Литтла). Разработанный метод также может быть применён
для решения гамильтоновой задачи о сельском почтальоне и гамильтоновой задачи
коммивояжера.
Литература
1. Морозов А.В. Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне /
А.В. Морозов, А.В. Панишев // Искусственный интеллект. – 2009. – № 3. – С. 138-143.
2. Яблонский А.А. Минимизация кольцевых маршрутов доставки продукции потребителям / А.А. Яблон-
ский // Экономика и математические методы. – 2006. – Том 43, № 3. – С. 124-131.
3. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М. : МЦНМО,
2001. – 960 с.
А.В. Морозов, А.В. Панишев, В.О. Скачков
Модифікація методу Літтла для розв’язання кільцевої задачі про сільського листоношу
У статті приведено формулювання і аналіз узагальнення гамільтонової задачі про сільського листоношу.
Пропонується точний метод її розв’язання, який розвиває класичний алгоритм Літтла.
A.V. Morozov, A.V. Panishev, V.O. Skachkov
Modification of Little’s Method for Solving the Circular Rural Postman Problem
In this paper the formulation and analysis of the generalization of the Hamiltonian Travelling Salesman
Problem is described. The exact method of its solving developing classical Little's algorithm is offered.
Статья поступила в редакцию 02.06.2010.
0X
( )1, 2
1X 2X
3X 4X
5X
( )2,1
( ),Q V L= ∅ = ∅
0 24Xϕ =
2 25Xϕ =
( ){ } ( )1, 2 ,Q V L= = ∅
1 25Xϕ =
( ){ } ( )2,1 ,Q V L= = ∅
( )3,5
( ) ( ) ( )4,3 , 3,5 , 5,1 ( ) ( ) ( )4,3 , 3,5 , 5,1 3 26Xϕ =
( ){ } ( )2,1 ,Q V L= = ∅
4 26Xϕ =
( ) ( ){ } ( ) { }2,1 , 5, 4 , 5Q V L= =
5 25Xϕ =
( ){ } ( )2,1 ,Q V L= =∅
|