Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера
Поиск решений задач класса коммивояжера в бинарной схеме ветвлений метода ветвей и границ можно значительно ускорить за счет обращении к быстрому алгоритму решения одного из вариантов задачи о назначениях (ЗН), применяемой для вычисления нижних оценок стоимости гамильтоновых маршрутов. Оптимальное р...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2012 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/60701 |
| 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: | Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2012. — № 2. — С. 95-110. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859665348549148672 |
|---|---|
| author | Левченко, А.Ю. Морозов, А.В. Панишев, А.В. |
| author_facet | Левченко, А.Ю. Морозов, А.В. Панишев, А.В. |
| citation_txt | Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2012. — № 2. — С. 95-110. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Поиск решений задач класса коммивояжера в бинарной схеме ветвлений метода ветвей и границ можно значительно ускорить за счет обращении к быстрому алгоритму решения одного из вариантов задачи о назначениях (ЗН), применяемой для вычисления нижних оценок стоимости гамильтоновых маршрутов. Оптимальное решение ЗН для полученной матрицы можно найти за время O(n²). Предложен алгоритм по схеме ветвей и границ, использующий быстрый алгоритм решения ЗН в качестве нижней оценки стоимости решения.
Пошук розв’язків задач класу комівояжера в бінарній схемі розгалуження метода гілок та меж можна суттєво прискорити за рахунок звернення до швидкого алгоритму розв’язку одного з варіантів задачі про призначення, яка використовується для обчислення нижніх оцінок вартості гамільтонових маршрутів. Оптимальний розв’язок задачі про призначення для отриманої матриці можна знайти за час O(n²). Запропоновано алгоритм за схемою гілок та меж, який використовує швидкий алгоритм розв’язку задачі про призначення в якості нижньої оцінки вартості розв’язку.
Solutions’ search for Traveling Salesman task’s class in the binary branching scheme of branch-and-bound method can be noticeable accelerated by referring to a fast algorithm for solving a variant of the assignment problem, used to compute lower bounds for the Hamiltonian routes’ cost. Optimal solution for assignment problem for resulting matrix can be found in time O(n²). The algorithm of the branch and bound scheme that uses a fast algorithm for solving the assignment problem as a lower bound of the solution’s cost is proposed.
|
| first_indexed | 2025-11-30T10:55:07Z |
| format | Article |
| fulltext |
«Штучний інтелект» 2’2012 95
5Л
УДК 519.161
А.Ю. Левченко, А.В. Морозов, А.В. Панишев
Житомирский государственный технологический университет, Украина
Украина, 10005, г. Житомир, ул. Черняховского, 103
Механизм ускорения вычислений в методе Литтла
для решения задач класса коммивояжера
A.Yu. Levchenko, A.V. Morozov, А.V. Panishev
Zhitomir state technological university, Ukraine
Ukraine, 10005, г. Zhitomir, Chernyakhovsky str., 103
Mechanism of Computations Acceleration in Little’s Method
for Solving Traveling Salesman Class Tasks
А.Ю. Левченко, А.В. Морозов, А.В. Панішев
Житомирський державний технологічний університет, Україна
Україна, 10005, м. Житомир, ул. Черняховського, 103
Механізм прискорення обчислень в методі Литтла
для розв’язку задач класу комівояжера
Поиск решений задач класса коммивояжера в бинарной схеме ветвлений метода ветвей и границ можно
значительно ускорить за счет обращении к быстрому алгоритму решения одного из вариантов задачи
о назначениях (ЗН), применяемой для вычисления нижних оценок стоимости гамильтоновых маршрутов.
Оптимальное решение ЗН для полученной матрицы можно найти за время 2O n . Предложен алгоритм по
схеме ветвей и границ, использующий быстрый алгоритм решения ЗН в качестве нижней оценки стоимости
решения.
Ключевые слова: задача коммивояжера, точный метод, модификация метода Литтла.
Solutions’ search for Traveling Salesman task’s class in the binary branching scheme of branch-and-bound method
can be noticeable accelerated by referring to a fast algorithm for solving a variant of the assignment problem, used
to compute lower bounds for the Hamiltonian routes’ cost. Optimal solution for assignment problem for resulting
matrix can be found in time 2O n . The algorithm of the branch and bound scheme that uses a fast algorithm for
solving the assignment problem as a lower bound of the solution’s cost is proposed.
Key words: Traveling Salesman Problem, exact method, modification of the Little’s method’s.
Пошук розв’язків задач класу комівояжера в бінарній схемі розгалуження метода гілок та меж можна
суттєво прискорити за рахунок звернення до швидкого алгоритму розв’язку одного з варіантів задачі про
призначення, яка використовується для обчислення нижніх оцінок вартості гамільтонових маршрутів.
Оптимальний розв’язок задачі про призначення для отриманої матриці можна знайти за час 2O n .
Запропоновано алгоритм за схемою гілок та меж, який використовує швидкий алгоритм розв’язку задачі
про призначення в якості нижньої оцінки вартості розв’язку.
Ключові слова: задача комівояжера, точний метод, модифікація метода Литтла.
Введение
Рассмотрим следующую формулировку задачи о назначениях (ЗН). Задана матрица
стоимостей ij n
C c , где ijc при i j и 0ijc Z или ijc при i j , , 1,i j n ,
А.Ю. Левченко, А.В. Морозов, А.В. Панишев
«Искусственный интеллект» 2’201296
5-З
0Z – множество неотрицательных целых чисел. Требуется найти оптимальную пере-
становку 1 , 2 ,..., n стоимостью C
1
,
n
i
i
min c
где 1 , 2 ,..., n –
перестановка n столбцов матрицы, ic , 1,i n . ЗН может не иметь решения если С
содержит элементы ijc , i j .
В статье [1] предложена процедура SIW, позволяющая по перестановке для
матрицы C , найти за время, пропорциональное 2O n оптимальное решение xy
для матрицы xyC , полученной из C , заменой значения xyc на бесконечность.
Статья посвящена модификации метода Литтла, использующей ускоренную про-
цедуру вычисления нижней границы стоимости оптимальных решений для ключе-
вых задач класса коммивояжера.
Ускоренная процедура вычисления
нижней границы стоимости
Рассмотрим следующий вариант ЗН: известно решение 1 , 2 ,..., n для
матрицы стоимостей ij n
C c , по заданной перестановке надо найти решение ЗН
,ab x y , содержащее элемент xyc , и не содержащее элемент , ,ab xyc c 1 2, ,...,abc c c
nc .
Д вудольны й граф , ,X Y U в котором элем ент ijc м атрицы С является
ребром ,i j , i j , содерж ит реш ение ЗН для C , как соверш енное паросочетание с
м иним альны м сум м арн ы м весом реб ер. Р еш ение ,ab x y для м атрицы ,abC x y ,
если оно сущ еств ует , такж е представлено, как соверш енное паросочетание в дву-
дольном граф е , ,X Y U , ,x yU U U a b , xyU – м нож ество всех ребер , инци-
дентных верш инам x и y . Задача нахождения перестановки ,ab x y реш ается за время
2O n методом поиска кратчайш его увеличиваю щ его пути из верш ины a в верш ину b
в двудольном граф е , ,X Y U . С пособ построения перестановки xy , не вклю -
чаю щ ей элем ент ,x y и перестановки ,x y , с о д е р ж а щ е й ,x y д л я в ы ч и с -
л е н и я н и ж н и х г р а н и ц в с х е м е в е т в л е н и я а л г о р и т м а Л и т т л а я в л я е т с я б а з о в о й к о м п о -
н е н т о й м е т о д а , о б е с п е ч и в а ю щ е го п о и с к т о ч н ы х р е ш е н и й з а д а ч к л а с с а к о м м и в о я ж е р а .
Э т о т к л а с с о б р а з у ю т з а д а ч а к о м м и в о я ж е р а (З К ) , о б щ а я З К (О З К ) и г а м и л ь т о н о в а З К
(Г З К ) [ 2 ] .
П у с т ь i j n
C c – м а т р и ц а с т о и м о с т е й , г д е i j i jc D в О З К , i j i jc d в З К и
Г З К , 1 , 2 , . . . ,q q q q n , g – с о о т в е т с т в е н н о о б х о д и е г о с т о и м о с т ь в л ю б о й
и з э т и х з а д а ч .
Н и ж н я я г р а н и ц а 0 в к о р н е д е р е в а п е р е б о р а р а в н а м и н и м у м у C ц е л е в о й
ф у н к ц и и З Н д л я н е к о т о р о й м а т р и ц ы C . Е е м о ж н о п р и б л и з и т ь к с т о и м о с т и *g
Механизм ускорения вычислений в методе Литлла для решения задач класса...
«Штучний інтелект» 2’2012 97
5Л
оптимального обхода *g следующим образом. Вначале матрица C приводится по
строкам, а полученный результат по столбцам. Затем матрица C приводится по
столбцам, а полученный результат – по строкам. Из них выбирается наименьшая
сумма 0 1 2,min (в общем случае 1 2 ), и соответствующая ей матрица 0C ,
по которой находится решение ЗН 0 . За нижнюю границу стоимости любого обхо-
да, порождаемого матрицей C , принимается величина
0 0 0 0 0 1 1, ,C min (1)
Временные затраты на вычисление 0 оцениваются величиной 3O n . Для про-
стоты положим в корне дерева перебора 0C C , 0 , 0 , 0 C .
Наибольшей неопределенностью, замедляющей процесс вычислений в методах
типа ветвей и границ, характеризуется этап выбора наиболее подходящего для включения
в оптимальное решение элемента из исходных данных, причем число кандидатов не
меньше порядка n матрицы C . Покажем, что в рассматриваемой модификации ме-
тода Литтла предпочтительный элемент, выбирается только из n элементов решения
ЗН.
Перестановку в корне дерева перебора представим цикловым разложением
1,vZ v K , 2K n . При 1K – циклическая перестановка, называемая в
терминах задач класса коммивояжера обходом. Чем меньше K , тем лучше структур-
ные свойства ЗН, применяемой в качестве релаксации для построения замкнутых
маршрутов в графовых моделях.
Рассмотрим взвешенный граф ,V U с множеством вершин V и множеством
дуг U , в котором пара вершин ,i jv v является дугой весом 0i jv vc R , если в мат-
рице C ijc . Цикловое разложение перестановки разбивает множество U на
подмножества 1U , содержащее все дуги циклового разложения, и 2U , к которому
отнесем все остальные дуги. Если удаляется дуга 1,x y U , то, очевидно, xy ,
xyC C . Добавление этой дуги к 1U либо приводит к образованию переста-
новки ,x y , ,C x y C , либо вообще исключает ее построение (рис. 1, в).
Поскольку ,x yC C x y д л я 1,x y U , т о и з д в у х а к т и в н ы х в е р ш и н ,x y
и ,x y , п о р о ж д е н н ы х к о р н е м , в е р ш и н о й в е т в л е н и я д о л ж н а б ы т ь ,x y .
Т а к и м о б р а з о м , к о р н ю и в е р ш и н е ,x y с о о т в е т с т в у е т о д н а п е р е с т а н о в к а ,
п о с л е п о с т р о е н и я к о т о р о й б ы л а в ы б р а н а д у г а 2,x y U . П о э т о м у д у г у ,x y , и н и -
ц и и р у ю щ у ю в е т в л е н и е , с л е д у е т в ы б и р а т ь и з п о д м н о ж е с т в а 1U .
Р а с с м о т р и м , к а к в п р е д л а г а е м о й м о д и ф и к а ц и и м е т о д а Л и т т л а с т р о и т с я д е р е в о п е р е -
б о р а и в ы ч и с л я ю т с я н и ж н и е г р а н и ц ы с т о и м о с т и р е ш е н и й g в е г о в е р ш и н а х . Е с л и д л я
м а т р и ц ы с т о и м о с т е й Г З К З Н н е и м е е т р е ш е н и я , т о Г З К т а к ж е н е р а з р е ш и м а . В о б щ е м
с л у ч а е п р о ц е с с в е т в л е н и я н а ч и н а е т с я с п о с т р о е н и я п е р е с т а н о в к и , ц и к л о в о е р а з л о ж е н и е
к о т о р о й о б р а з у ю т K к о н т у р о в , 2K , в ы ч и с л е н и я C и н и ж н е й г р а н и ц ы
*g C в к о р н е д е р е в а п е р е б о р а .
А.Ю. Левченко, А.В. Морозов, А.В. Панишев
«Искусственный интеллект» 2’201298
5-З
а) б) в)
Рисунок 1 – а), б) множество циклов, построенное путем добавления к цикловому
разложению перестановки дуги 2,x y U ; в) добавление дуги ,x y ,
не содержащейся в цикловом разложении перестановки , исключает построение
вообще какой-либо перестановки. Добавленная дуга ,x y изображена утолщенной
линией, тонкими линиями представлены дуги, порождающие множество циклов из дуги
,x y и циклового разложения перестановки ; пунктирными линиями обозначены
дуги, исключенные из циклового разложения перестановки
При исключении из решения ЗН элемента ,x y , инициализирующего ветв-
ление, степень его влияния на стоимость оптимального обхода определяется оценкой
,x y . Чтобы определить ,x y , каждую дугу ,k l , удаленную из циклового раз-
ложения перестановки оценим величиной
, kj il kl
j l i k
k l min c min c c
(2)
Решение ГЗК , матрица стоимостей которой содержит ijc , i j , может
включать элементы ,k l с оценками , lk . Такие же элементы могут быть в
решениях ЗН, полученных при вершинах ветвления в процессе построения обхода
*g ЗК или оптимального маршрута ОЗК. Очевидно, если ,k l , то обход, соответ-
ствующий решению ЗН, включает ,k l , а ,x y . Нетрудно заметить, что не
существует обхода, для которого построено решение ЗН, если в цикловом разложе-
нии этого решения все дуги какого-либо из контуров имеют оценку или число r
дуг ,k l с оценкой больше n K .
Список элементов с оценкой в решении ЗН и элемент ,x y с оценкой
,x y , если он существует, находится процедурой LANG .
Вход процедуры представлен матрицей стоимостей ij n
C c с элементами
iic , 1,i n , 0ijc R , или ijc , i j , решением ЗН , 1 ,k l k n
1, 2,...,l n , klc для матрицы C , числом контуров K в цикловом разложе-
нии перестановки и пустым списком , ,R k l k l , r R .
В п р о ц е с с е п о и с к а э л е м е н т а ,x y , и н и ц и и р у ю щ е г о в е т в л е н и е , п р о ц е д у р а
в о з в р а щ а е т с п и с о к R э л е м е н т о в , н е с о д е р ж а щ и х ,x y , ф о р м и р у е т ц и к л о в о е
2Z
1Z
x y
y
1Z
2Zx
y
x
1Z
2Z
Механизм ускорения вычислений в методе Литлла для решения задач класса...
«Штучний інтелект» 2’2012 99
5Л
разложение перестановки на контуры wZ , 1,w K , определяет их мощности и
выбирает наименьшую среди них minK . Искомый элемент ,x y существует и при-
нимает максимальное действительное значение оценки, определяемое из (2), если
minr K или r n K . Процедура LANG включает такие действия
begin
:R ; : 0r ; : 0;M
: 1k
while k n do
begin
: m in k jc k c j l ;
: m in i lc l c i k ;
, : k lk l c k c l c ;
i f , 0k l th e n
b e g in
: , ; : 1;R R k l r r
i f c k th e n
fo r a l l 1, 2 , . . . , 1, 1, . . . ,j l l n d o
: ;k jc
i f c l th e n
fo r a l l 1, 2 , . . . , 1, 1, . . . ,i k k n d o
: ;ikc
e n d
if ,k l M th e n : , ;M k l
: 1;k k
e n d
if r n K th e n : ;M
п р е о б р а з о в ы в а т ь п е р е с т а н о в к у в ц и к л о в о е р а з л о ж е н и е 1,wZ w K
и н а й т и m in m in 1,wK Z w K ;
i f m inK r th e n
b e g in
: 1;w
w h ile w K d o
b e g in
: ;w wZ Z R G
i f wZ th e n : ;M e ls e : 1;w w
e n d
e n d
А.Ю. Левченко, А.В. Морозов, А.В. Панишев
«Искусственный интеллект» 2’2012100
5-З
if M then
begin
, : , ;x y k l
сохранить все элементы и их оценки в контуре qZ , содержащем
,x y
end
end
Процедура LANG за время 2O n преобразует входную матрицу C в матрицу
C того же порядка, что и C , и в зависимости от мощности списка R устанав-
ливает, является ли элемент ,k l с максимальным действительным значением M ,
определяемым из (2), искомым элементом ,x y с оценкой
, m a x , ,x y k l i k l R .
Е с л и в х о д н а я м а т р и ц а с о д е р ж и т э л е м е н т ,x y , и н и ц и и р ую щ и й в е т в л е н и е , т о
в м е с т е с м атри ц ей C и сп и ск ом R п роц ед ур а зап о м и н ает в се эл ем ен ты п о д м н о -
ж еств а qZ , к отор ом у п ри н ад л еж и т ,x y . В ер ш и н а в етв л ен и я , п р ед став л ен н ая к ор н е м
д ер ев а п ер еб о р а, п ор ож д ает в ер ш и н ы ,x y , ,x y и сп и сок Q эл ем ен то в м ат -
ри ц ы C , и зм ен яю щ и х св ои д ей стви тел ьн ы е зн ач ен и я н а . В к орн е д ерев а Q .
Н а й д е м в в е р ш и н е ,x y н и ж н ю ю г р а н и ц у ,x y с т о и м о с т и л ю б о го
о б х о д а , н е с о д е р ж а щ е г о э л е м е н т ,x y R . О ч е в и д н о , и с к о м а я г р а н и ц а о п -
р е д е л я е т с я в р е з у л ь т а т е п р е о б р а з о в а н и я р е ш е н и я З Н в р е ш е н и е З Н x y д л я м а -
три ц ы 1C , п ол уч ен н ой и з C зам ен ой 0x yc R н а . В ы п ол н и м п роц ед ур у н ах о ж д ен и я
x y S IW . Т о г д а
1
x y, е с л и п о с т р о е н а п е р е с т а н о в к а ;
,
и н а ч е .
x yC
x y
Я с н о , ч т о в е р ш и н а ,x y н е п о д л е ж и т в е т в л е н и ю , е с л и ,x y и л и
п о с т р о е н н а я п е р е с т а н о в к а x y ц и к л и ч е с к а я . Е с л и п е р е с т а н о в к а x y н е ц и к л и ч е с к а я ,
т о в е р ш и н е ,x y п о с т а в и м в с о о т в е т с т в и е x y , , x yx y , ч и с л о к о н -
т у р о в x yK в ц и к л о в о м р а з л о ж е н и и x y и с п и с к и xyR R , xyQ
,Q x y , восстанавливающие по исходной матрице матрицу 1C .
Определим в вершине ,x y оценку снизу ,x y стоимости любого об-
хода, содержащего элемент ,x y и все элементы списка R . Такой оценкой
Механизм ускорения вычислений в методе Литлла для решения задач класса...
«Штучний інтелект» 2’2012 101
5Л
является стоимость перестановки ,x y , включающей ,x y и R . Перестановка
,x y может совпадать или не совпадать с . Для того чтобы выяснить, когда
,x y и как найти ,x y , обратимся к контуру qZ , которому принад-
лежит дуга ,x y , соответствующая элементу, инициирующему ветвление. q qZ n .
Обозначим qn число дуг контура, получивших при поиске дуги ,x y оценку .
Каждой такой дуге соответствует элемент из списка R . Очевидно, при qn
1qZ не существует обхода, который содержит ,x y , т.е. ,x y (рис. 2, а).
Пусть 2q qn Z . Тогда ,x y , ,x y C , C C ,
, ,R x y R x y . Список ,Q x y формируется за время qO n добав-
лением к Q элементов, которые при изменении в матрице C своих действитель-
ных значений на устраняют контур с дугой ,x y и максимально возможным числом
дуг из R . Рассмотрим все случаи исключения подконтуров.
1. , ,Q x y Q y x , если дуга ,x y не инцидентна в контуре qZ дугам
с оценками, равными , и yxc в матрице 1C (рис. 2, б). Положив в C с yxc ,
получим матрицу 2C для поиска в ней очередного элемента, инициирующего ветв-
ление.
2. Если контур qZ содержит цепочку дуг 1 1 2, , ,..., , ,
q qn n pv x v y v v v 1pv с
оценками 1 1,nv x , 1,p pv v , 1,r rv v , 2,r p , и
pv xc (рис. 2, в),
то в матрице 1C положим
pv xc . В результате получим матрицу 2C и список
, ,pQ x y Q v x .
3 . П о д к о н т у р , о б р а з у е м ы й в qZ ц е п о ч к о й д у г 1 1, , . . . , , . . . , , ,
qn r p pv v v x v y v
2pv с о ц е н к а м и 1,
qnv v , 1 2,p pv v , 1 ,r rv v , 2 ,r p , и д у г о й
1, vy ,
1y vc (р и с . 2 , г ) у с т р а н я е т с я з а м е н о й в м а т р и ц е C д е й с т в и т е л ь н о г о зн а -
ч е н и я
1y vc н а . З а м е н а д а е т м а т р и ц у 2C и с п и с о к ,Q x y 1,Q y v .
4 . Ч т о б ы у с т р а н и т ь в qZ п о д к о н т у р ы , п о р о ж д а е м ы е ц е п о ч к о й д у г 1, , . . . ,
qnv v
1 1 1, . . . , , , , . . . , ,r s s s p pv x v y v v v v с о ц е н к а м и 1,
qnv v , ,pv 1pv ,
1 ,r rv v , 2 1r s , 1s r p , и д у г а м и 1,pv v , ,pv x , 1,y v ,
1pv vc ,
pv xc ,
1y vc (р и с . 2 , д ) , о б р а з у е м м а т р и ц у 2C , п о л о ж и в 1 1p pv v v x yvc c c в
м а т р и ц е C , 1 1, , ,pQ x y Q v v y v .
А.Ю. Левченко, А.В. Морозов, А.В. Панишев
«Искусственный интеллект» 2’2012102
5-З
Предположим, 2q qn Z . Тогда является значением оценки каждой дуги
контура qZ за исключением ,x y и 1,r rv v , 1 1qr n ,
qnx v , 1y v (рис. 2, е).
Если искомое решение содержит ,x y , то оно не содержит дугу 1,r rv v , иначе
1q qn Z . Отсюда следует, что оценкой ,x y является стоимость переста-
новки
1
,
r rv v x y
, в которую входит элемент ,x y и нет элемента 1,r rv v . Другими
словами,
1
,
r rv v x y
представляет собой решение ЗН для матрицы 2C , полученной
из C присвоением элементу 1,r rv v и элементам ,x j , ,i y , j y , i x , с
действительными значениями.
Перестановка
1
,
r rv v x y
строится как и перестановка ,ab x y , если по-
ложить ra v , 1rb v , ,a b – элемент, соответствующий 1,r rv v . Таким образом,
при 2q qn Z
2 , , если построена перестановка , ;
,
в противном случае.
ab abC x y x y
x y
Вершина ,x y не имеет допустимого продолжения, когда ,x y
или построена циклическая перестановка ,ab x y . Если построена нециклическая
перестановка ,ab x y , то вершине ,x y ставится в соответствие ,ab x y ,
, ,a bx y x y , ч и с л о к о н т у р о в ,a bK x y в ц и к л о в о м р а з л о ж е н и и
п ер естан о вк и ,a b x y и сп и ск и abR , ,x y R G x y , ,a bQ x y Q
,a b .
Т а к и м о б р а з о м , м н о ж е с т в о в с е х р е ш е н и й g з а д а ч и р а с с м а т р и в а е м о г о к л а с с а
о б р а з у е т о б ъ е д е н и е н е п е р е с е к а ю щ и х с я п о д м н о ж е с т в ,x y и ,x y .
Е с л и о б е п е р е с т а н о в к и x y и , ,a bx y x y , п о с т р о е н н ы е с о о т в е т с т в е н н о
в в ер ш и н ах ,x y и ,x y , о к азы в аю тся ц и к л и ч еск и м и , то *
x yg п р и x y
,x y и * ,g x y п р и , x yx y . Е с л и п о л у ч е н о т о л ь к о о д н о
р е ш е н и е З Н x y и л и ,x y , и о н о п р е д с т а в л е н о ц и к л и ч е с к о й п е р е с т а н о в к о й , т о
т а к а я п е р е с т а н о в к а я в л я е т с я и с к о м ы м о б х о д о м .
К о н ц е в ы е в е р ш и н ы , и м е ю щ и е д о п у с т и м ы е п р о д о л ж е н и я в с т р о я щ е м с я д е р е в е
п е р е б о р а , о б р а з у ю т м н о ж е с т в о а к т и в н ы х в е р ш и н , к о т о р ы м с о о т в е т с т в у ю т н ец и к ли -
ческ и е п ер естан о вки с оц ен к ам и , р авн ы м и стои м остям эти х п ер естан о вок . В етвл ен и ю п о д -
л е ж и т а к т и в н а я в е р ш и н а с н а и м е н ь ш е й о ц е н к о й . О ц е н к а в в е р ш и н е , д л я к о т о р о й н е
с у щ е с т в у е т р е ш е н и я З Н , р а в н а . П о с т р о е н и е о б х о д а *g з а в е р ш а е т с я н а х о ж д е н и е м
к о н ц е в о й в е р ш и н ы и с о о т в е т с т в у ю щ е й е й ц и к л и ч е с к о й п е р е с т а н о в к и с т о и м о с т ь ю ,
н е б о л ь ш е й , ч е м о ц е н к а в л ю б о й д р у г о й к о н ц е в о й в е р ш и н е .
Механизм ускорения вычислений в методе Литлла для решения задач класса...
«Штучний інтелект» 2’2012 103
5Л
а) б) в)
г) д) е)
Рисунок 2 – Дуга с оценкой изображена утолщенной линией, а дуга, исклю-
ченная из контура qZ , – пунктирной; а) для нециклической перестановки не
существует соответствующего ей обхода, который содержит ,x y ; исключается
подконтур б) , ,x y x , в) 1, ,..., ,..., ,
qn r px v y v v v x , г) 1 1, , ,..., ,p p rx v y v v v
..., x , д) устраняются подконтуры 1 1, , , ,...,s s sx v y v v v ,...,rv x , е) исключается
контур qZ .
Модифицированный метод Литтла
Перейдем к пошаговому представлению модификации метода Литтла.
S0. Из матрицы ij n
C c определить дважды приведенные матрицы 1C и 2C
и соответствующие им суммы 1 и 2 констант приведения;
если 1 2 , то положить 1C C , 1 , иначе 2C C , 2 ;
выполнить алгоритм решения ЗН для матрицы C ;
если для матрицы C , содержащей элемент ijc , i j , ЗН не имеет решения,
то конец: не существует обходов g .
если решением ЗН является циклическая перестановка , то – обход *g
минимальной стоимости;
– нециклическая перестановка стоимостью 0 C в вершине ветвления
X , представленной корнем дерева перебора, K – число контуров в цикловом
разложении перестановки , Q , copyC C ; 1m , m , m C ,
mK K , mQ Q , X mX .
( :comment выполнение основного этапа начинается с ветвления корня)
1y v
qZ
1rv
rv
qnx v1sx v sy v
rv
1v
qnv
qZ
1pv
pv
1sv
px v 1py v
rv
qZ
1v
qnv
qZ
2v
pv1pv
1qnv
qnx v
1y vx y
qZ
x y
qZ
А.Ю. Левченко, А.В. Морозов, А.В. Панишев
«Искусственный интеллект» 2’2012104
5-З
S1. mX X X – список концевых вершин; процедурой LANG выполнить
поиск в матрице copyC элемента ,m mx y , инициирующего ветвление вершины mX ;
если выходом процедуры является ,m mx y , то нет решений g , как со-
держащих, так и не содержащих элемент ,m mx y ; перейти к шагу S5;
сохранить результаты работы процедуры LANG : ,m mx y , список
, ,mR k l k l , м а т р и ц у C , м н о ж е с т в о в с е х э л е м е н т о в ,k l , со о т в етст -
в ую щ и х д угам к о н т ур а qZ , в к о т о р о м со д ер ж и т ся д уга ,m mx y , а так ж е о ц ен к у ,k l
к аж д о й д уги , qk l Z , qZ Z , Z – ц и к л о в о е р азл о ж ен и е п ер ест ан о вк и m ; q qn Z .
( c o m m e n t : ф о р м и р о в а н и е м н о ж е с т в а о б х о д о в , н е с о д е р ж а щ и х ,m mx y )
S 2 . m mx yX X X ; д л я м атр и ц ы 1C , п о л уч ен н о й и з C зам ен о й 0m mx yc R
н а , в ы п о л н и т ь п р о ц е д у р о й S IW п о с т р о е н и е п е р е с т а н о в к и
m mx y , н е в к л ю ч а ю щ е й
э л е м е н т ,m mx y ;
е с л и н е п о с т р о е н а п е р е с т а н о в к а
m mx y , т о в е р ш и н а m mx yX , п о р о ж д е н н а я
в е р ш и н о й mX , н е и м е е т д о п у с т и м о г о п р о д о л ж е н и я и п о л у ч а е т о ц е н к у
m mx y ; п е р е й т и к ш а г у S 3 . Е с л и п о с т р о е н а ц и к л и ч е с к а я п е р е с т а н о в к а
m mx y ,
т о m mx yX – к о н ц е в а я в е р ш и н а с д о п у с т и м ы м р е ш е н и е м
m mx yg с т о и м о с т ь ю
m mx y 1
m mx yC ; п е р е й т и к ш а г у S 3 ;
m mx y – н е ц и к л и ч е с к а я п е р е с т а н о в к а , m mx yX – а к т и в н а я в е р ш и н а , к о т о р о й
со о тветств ует
m mx y , н и ж н яя гр ан и ц а 1
m m m mx y x yC , ч и сл о к он т ур о в m mx yK
в ц и к л о в о м р а з л о ж е н и и п е р е с т а н о в к и
m mx y ,
m mx y mR R ,
m mx y mQ Q
,m mx y .
S3. Восстановить матрицу C в результате замены
m mx yc , 1
m mx yc C , на
действительное значение
m mx yc .
( comment : формирование множества обходов, включающих элемент ,m mx y )
S4. ,m mX X X x y . О п р е д е л и т ь ч и с л о qn э л е м е н т о в , lk qZ с
о ц е н к о й ,k l ;
ес л и 1q qn n , т о н е с ущ е с т в уе т п ер ест ан о в к и ,m mx y , в к л ю ч аю щ ей эл е м ен т
,m mx y (р и с . 3 , а ) ; в е р ш и н а ,m mX x y , п о р о ж д е н н а я в е р ш и н о й mX , я в л я е т с я
к о н ц е в о й с о ц е н к о й ,m mx y ; у д а л и т ь м а т р и ц у C и п е р е й т и к S 5 .
е с л и 2q qn n , т о а к т и в н о й в е р ш и н е ,m mX x y п о с т а в и т ь в с о о т в е т с т в и е
п е р е с т а н о в к у ,m mx y , н и ж н ю ю г р а н и ц у ,m m mx y C , m copy mC C ,
Механизм ускорения вычислений в методе Литлла для решения задач класса...
«Штучний інтелект» 2’2012 105
5Л
,m m mK x y K , ,m m mR x y R ,m mx y и ,m m mQ x y Q L ,
где содержимое L устанавливает один из четырех случаев исключения подконтуров
в qZ : 1) ,m mL y x (рис. 3, б); 2) ,p mL v x (рис. 3, в); 3) 1,mL y v (рис. 3, г);
4) L 1 1, , ,p p mv v v x y v (р и с . 3 , д ); уд ал и ть м атр и ц у C и п ер ей ти к ш агу S 5 .
2q qn n (р и с . 3 , е ) ; д л я м а т р и ц ы 2C , п о л у ч е н н о й и з C з а м е н о й н а д е й с т -
в и т е л ь н ы х з н а ч е н и й a bc ,
mx jc , mj y ,
miyc , mi x , , qa b Z , ,a b , ma x ,
mb y , в ы з в а т ь п р о ц е д у р у S IW д л я п о с т р о е н и я п е р е с т а н о в к и ,a b m mx y , к о т о р а я
в к л ю ч а е т ,m mx y и н е в к л ю ч а е т ,a b ;
е с л и н е с у щ е с т в у е т ,a b m mx y , т о ,m mx y в к о н ц е в о й в е р ш и н е
,m mX x y ; у д а л и т ь м а т р и ц у 2C ; п е р е й т и к ш а г у S 5 ;
е с л и ,a b m mx y – ц и к л и ч е с к а я п е р е с т а н о в к а , т о ,m mX x y – к о н ц е в а я
в е р ш и н а , а ,a b m mg x y – о б х о д с т о и м о с т ь ю 2, ,m m a b m mx y C x y
; у д а л и т ь м а т р и ц у 2C , п е р е й т и к ш а г у S 5 ;
,a b m mx y – н е ц и к л и ч е с к а я п е р е с т а н о в к а ; а к т и в н о й в е р ш и н е ,m mX x y
п о стави ть в со о тв етстви е п ер естан о вк у ,a b m mx y , н и ж н ю ю гр ан и ц у ,m mx y
2 ,a b m mC x y , ч и с л о к о н т у р о в ,m mK x y в ц и к л о в о м р а з л о ж е н и и п е р е -
с т а н о в к и ,ab m mx y , с п и с к и , ,m m m m mR x y R x y , ,m m mQ x y Q
,a b ; у д а л и т ь м а т р и ц у 2C .
S 5 . 1m m ; в с п и с к е X н а й т и в е р ш и н у mX с н а и м е н ь ш и м з н а ч е н и е м
m ;
е с л и m , т о н е с у щ е с т в у е т и с к о м о г о о б х о д а *g : к о н е ц ;
е с л и m – ц и к л и ч е с к а я п е р е с т а н о в к а , т о *
mg : к о н е ц ;
и н а ч е с ф о р м и р о в а т ь м а т р и ц у c o p yC , п о л о ж и в в и с х о д н о й м а т р и ц е C k jc ,
j l , i lc , i k , д л я в сех ,k l R и r sc д л я в сех эл ем ен то в , mr s Q ;
п е р е й т и к ш а г у S 1 ;
П р и м е р 1 . Н а й т и о б х о д *g м и н и м а л ь н о й с т о и м о с т и д л я м а т р и ц ы
C
1 2 3 4 5 6 7 8
4
7
5
9
6
1
3
5
5
5
1
2
3
5
1
4
5
1 1 8
1
4
2
0
4
1
5
1
9 3
4
0
2
0
А.Ю. Левченко, А.В. Морозов, А.В. Панишев
«Искусственный интеллект» 2’2012106
5-З
6
4
1
2
5
1 9
7
6
1 2
2
6
4 1
8
Выполним действия шага S0. Приведем матрицу C сначала по строкам, а затем
полученный результат по столбцам, определив матрицу
1C
1
2
2 3 3
3
1 7
4 7 3 5
5 0
6
3 9 5
7
8
и сумму констант приведения 1 47 12 14 14 20 12 22 18 59 0 0
0 0 0 14 4 216 . Приведем матрицу сначала по столбцам, а затем в получен-
ной таблице выполним приведение по строкам. В результате получим матрицу
2C
1 2 3 4 5 6 7 8
1 23 29 0
2 21 41 0
3 23 0 39 0
4 0 0 29 0 75
5 22 0
6 3 0 37 77
7 0 2
8 0 1
и сумму констант приведения 2 61+12+14+14+20+12+51+18+10+0+0+0+6+0+
+0+3=221. Поскольку 1 2 , положим 1C C , 1 . Для матрицы C найдем ре-
шение ЗН 1, 7 , 2, 6 , 3,8 , 4, 5 , 5, 4 , 6, 2 , 7,1 , 8, 3 , его стоимость 17C c
26 38 45 54 62 71 83c c c c c c c 0+0+0+6+0+0+0+6=6, и число K G контуров в
циклическом разложении перестановки . Стоимость искомого обхода *g ограни-
чена снизу величиной 0 C 6+216=222. Вершиной ветвления X G яв-
ляется корень дерева перебора. Сформируем матрицу copyC C , дублирующую на шаге
S0 матрицу C ; 1m , 1 6 , 1 222 , 1 4K , 1Q , 1X X .
S1. 1X X X . Выполним процедуру LANG с матрицей copyC на
входе: 1, 7 0+23-0=23, 2, 6 23+27-0=50, 3, 8 21+75-0=96, 4, 5 23+
+12-6=29, 5, 4 22+0-6=16, 6, 2 13+21-0=34, 7,1 0+7-0=7, 8, 3 7+
+23-0=30. На выходе процедуры получим 3, 8 96 , 1R , C copyC ,
3 3, 8 , 8, 3Z , 3 2n .
Механизм ускорения вычислений в методе Литлла для решения задач класса...
«Штучний інтелект» 2’2012 107
5Л
S2. 38X X . Положив 38c в матрице C , получим матрицу 1C , для
которой процедурой SIW найдем решений ЗН 38 1, 7 , 2, 6 , 3, 4 , 4, 8 ,
5, 2 , 6,1 , 7, 5 , 8, 3 , его стоимость 1
38C =0+0+0+75+20+13+0+0=108 и
нижнюю границу 38 108+216=324 в активной вершине 38X . Цикловое
разложение перестановки 38 состоит из двух контуров 1, 7 , 7, 5 , 5, 2 , 2, 6 ,
6,1 , 3, 4 , 4, 8 , 8, 3 , 38 2K ; 38R , 38Q 3, 8 .
S3. Восстановим матрицу C заменой 38c на 38 0c в матрице 1C .
S4. 3, 8X X X . Ч и сл о эл ем ен тов с оц ен к ой в 3Z 3 0n , 3 3 2n n .
П о л о ж и в в м а т р и ц е C 8 3c и 3 jc , 8j , 8ic , 3i , п о л у ч и м м а т р и ц у
2C
j
i
1 2 3 4 5 6 7 8
1 0 1 2 0
2 2 3 4 3 0
3 0
4 0 6 2 7 2 3
5 2 0 0
6 1 3 0 3 9 8 5
7 0 0
8 7
П р о ц е д у р а S IW с т р о и т д л я м а т р и ц ы 2C п е р е с т а н о в к у 83 3, 8 1, 7 , 2 , 6 ,
, 13, 8 , 4 , 3 , 5 , 4 , 6 , 2 , 7 , 5 , 8 , 2
8 3 3, 8 7C , 8 3 3, 8 7 + 2 1 6 = 2 2 3 .
Ц и к л ов о е р азл ож ен и е п ер естан о вк и 83 3, 8 п ред став л ен о к он т ур ам и 1, 7 , 7, 5 , 5, 4 ,
4, 3 , 3, 8 , 8, 1 , 2, 6 , 6, 2 , 3, 8 2K ; 3, 8R 3, 8 , 3, 8Q 8, 3 ;
у д а л и м м а т р и ц у 2C .
S 5 . 2m . В с п и с к е 3 8 , 3 , 8X X X в е р ш и н а 3, 8X а к т и в н а ,
и м е е т н а и м е н ь ш ую г р а н и ц у 2
8 33, 8 3, 8 2 2 3C и п о э т о м у я в л я е т с я
в е р ш и н о й в е т в л е н и я ; 2 8 3 3, 8 . И з и с х о д н о й м а т р и ц ы C о б р а з у е м м а т р и ц у
c o p yC , в к о т о р о й 3 jc , 8j , 8ic , 3i , 8 3c .
c o p yC
j
i
1 2 3 4 5 6 7 8
1 0 1 2 0
2 2 3 4 3 0
3 0
4 0 6 2 7 2 3
5 2 0 0
6 1 3 0 3 9 8 5
7 0 0
8 7
А.Ю. Левченко, А.В. Морозов, А.В. Панишев
«Искусственный интеллект» 2’2012108
5-З
S1. 38X X – список концевых вершин. После выполнения процедуры
LANG получим
1, 7 27 , 2, 6 50 , 3, 8 , 4, 3 46 , 5, 4 63 , 6, 2 33 ,
7, 5 6 , 8,1 ;
5, 4 63 , 2 3, 8 , 8,1R ; 1 1, 7 , 7, 5 , 5, 4 , 4, 3 , 3, 8 , 8,Z
1 , 1 6n . Матрицы C на выходе процедуры LANG отличается от copyC тем, что в
C 1ic , i .
S2. 38 54,X X X . В матрице C заменим 54 0c на . Для получен-
ной матрицы 1C выполним процедурой SIW построение перестановки 54 , не
содержащей 5,4 . Процедура строит циклическую перестановку 54 1,7 , 7,5 ,
5,2 , 2,4 , 4,6 , 6,3 , 3,8 , 8,1 стоимостью 54 352. Вершина 54X , поро-
ждаемая вершиной 3, 8X , не имеет допустимого продолжения.
S3. Заменив в матрице 1C 54c на 0, вновь получим матрицу C .
S4. 3 8 5 4, , 5 , 4X X X X , 1 12 2 4n n . В е р ш и н е 5 , 4X
с о о т в е т с т в у е т п е р е с т а н о в к а 8 3 3 , 8 , 5 , 4 2 2 3 , 5 , 4K = 83 3, 8 2K ,
8 35, 4 3, 8 5, 4R R = 3, 8 , 5, 4 , 5 , 4Q 83 3, 8 4, 5Q 8, 3 , 4,5
(с л у ч а й 1 у с т р а н е н и я п о д к о н т ур а в к о н т у р е 1Z ) .
S 5 . 3m . В е т в л е н и е в ы п о л н я е т с я в а к т и в н о й в е р ш и н е 5 , 4X с п и с к а X .
В е р ш и н е 5 , 4X с о о т в е т с т в у е т н а и м е н ь ш а я н и ж н я я г р а н и ц а 5 , 4 2 2 3 ;
3 5 , 4 . Ч т о б ы п о л уч и т ь м а т р и ц у c o p yC д л я п е р е с т а н о в к и 3 , в м а т р и ц е C п о -
л о ж и м 3 jc , 8j , 8ic , 3i , 5 jc , 4ic , 5i . 8 3c , 4 5c .
copyC
j
i 1 2 3 4 5 6 7 8
1 0 1 2 0
2 2 3 0
3 0
4 0 2 7 2 3
5 0
6 1 3 0 3 9 8 5
7 0 0
8 7
S 1 . 6 3 5 4,X X X . Н а в ы х о д е п р о ц е д у р ы L A N G п о л у ч и м 1, 7 2 3 ,
2 , 6 5 0 , 3, 8 , 4 , 3 4 6 , 5 , 4 , 6 , 2 , 7 , 5 1 2 ,
8 , 1 ; 2 , 6 5 0 , м а т р и ц у
j
i 1 2 3 4 5 6 7 8
Механизм ускорения вычислений в методе Литлла для решения задач класса...
«Штучний інтелект» 2’2012 109
5Л
1X
38X 3, 8X
54X 5, 4X
26X 2, 6X
1 222
38 324 83 3,8 223
54 352 83 3, 8 223
26 273 2, 6
C 1 0 12 0
2 23 0
3 0
4 0 27 23
5 0
6 0 85
7 0
8 7
3 3, 8 , 5, 4 , 6, 2 , 8,1R ; 2 2, 6 , 6, 2Z в цикловом разложении
перестановки 835, 4 3, 8 , 2 2n , 2 1n .
S2. 38 54 26, ,X X X X . В C заменить 26 0c на , чтобы получить
матрицу 1C . Результатом выполнения процедуры SIW для матрицы 1C является ци-
клическая перестановка 26 1, 7 , 7, 5 , 5, 4 , 4, 6 , 6, 2 , 2, 3 , 3,8 , 8,1 стоимо-
стью 26 273 .
S3. Определим матрицу C , заменив в 1C 26c на 0.
S4. 3 8 5 4 2 6, , , 2 , 6X X X X X . П е р е с т а н о в к а 2, 6 н е с у щ е с т -
в у е т , п о с к о л ь к у 2 2 1n n . В е р ш и н а 2 , 6X п о л у ч а е т о ц е н к у .
S 5 . 4m . В е р ш и н е 2 6X с о о т в е т с т в у е т ц и к л и ч е с к а я п е р е с т а н о в к а с м и н и -
м а л ь н ы м з н а ч е н и е м 2 6 2 7 3 . П о э т о м у и с к о м ы й о б х о д *
2 6g с т о и м о с т ь ю
*g 2 6 2 7 3C .
Р и с . 3 . о т о б р а ж а е т п р о ц е с с п о с т р о е н и я о б х о д а *g .
Р и с у н о к 3 – Д е р е в о п е р е б о р а д л я н а х о ж д е н и я о б х о д а *
2 6g ; 1 1, 7 ,
2 , 6 , 3 , 8 , 4 , 5 , 5 , 4 , 6 , 2 , 7 , 1 , 8 , 3 ; 3 8 1, 7 , 2 , 6 , 3, 4 ,
4 , 8 , 5 , 2 , 6 , 1 , 7 , 5 , 8 , 3 ; 8 3 3 , 8 1, 7 , 2 , 6 , 3 , 8 , 4 , 3 ,
5 , 4 , 6 , 2 , 7 , 5 , 8 , 1 ; 5 4 1, 7 , 7 , 5 , 5 , 2 , 2 , 4 , 4 , 6 , 6 , 3 , 3 , 8 , 8 , 1 ;
2 6 1, 7 , 7 , 5 , 5 , 4 , 4 , 6 , 6 , 2 , 2 , 3 , 3 , 8 , 8 , 1 ; 2 , 6
А.Ю. Левченко, А.В. Морозов, А.В. Панишев
«Искусственный интеллект» 2’2012110
5-З
Выводы
Предложен модифицированный метод Литтла для решения задач класса комми-
вояжера. Процедура ускоренного поиска нижней границы стоимости решения пред-
ставляет собой вариант алгоритма ЗН, который строит ее решение из перестановки,
полученной на предыдущем этапе ветвления.
Литература
1. Левченко А.Ю. Быстрый алгоритм решения задачи о назначениях для нахождения нижней гра-
ницы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний
інтелект.– 2011. – С. 406-416.
2. Кристофидес Н. Теория графов. Алгоритмический подход / Н. Кристофидес – М. : Мир, 1978 .– 432 с.
Literatura
1. Levchenko A.Yu. Isskusstvennuj intellekt. Donetsk. 2011. S. 406-416.
2. Christofides N. Teorija grafov. Algoritmicheskij podhod. М.: Мyr. 1978 .432s.
A.Yu. Levchenko, A.V. Morozov, А.V. Panishev
Mechanism of Computations Acceleration in Little’s Method
for Solving Traveling Salesman Class Tasks
Solutions search for traveling salesman problem class in the binary branching scheme of
branch-and-bound method can be noticeable accelerated by referring to a fast algorithm for
solving a variant of the assignment problem (AP), used to compute lower bounds for the
Hamiltonian routes’ cost [1]. Assignment problem’s optimal permutation for the resulting
matrix can be found in time 2O n using solution from the previous branching stage. The branch
and bound method that uses a fast algorithm for solving the assignment problem as a lower
bound of the solution’s cost is proposed.
Статья поступила в редакцию 10.05.2012.
|
| id | nasplib_isofts_kiev_ua-123456789-60701 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-11-30T10:55:07Z |
| publishDate | 2012 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Левченко, А.Ю. Морозов, А.В. Панишев, А.В. 2014-04-19T09:59:55Z 2014-04-19T09:59:55Z 2012 Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2012. — № 2. — С. 95-110. — Бібліогр.: 2 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/60701 519.161 Поиск решений задач класса коммивояжера в бинарной схеме ветвлений метода ветвей и границ можно значительно ускорить за счет обращении к быстрому алгоритму решения одного из вариантов задачи о назначениях (ЗН), применяемой для вычисления нижних оценок стоимости гамильтоновых маршрутов. Оптимальное решение ЗН для полученной матрицы можно найти за время O(n²). Предложен алгоритм по схеме ветвей и границ, использующий быстрый алгоритм решения ЗН в качестве нижней оценки стоимости решения. Пошук розв’язків задач класу комівояжера в бінарній схемі розгалуження метода гілок та меж можна суттєво прискорити за рахунок звернення до швидкого алгоритму розв’язку одного з варіантів задачі про призначення, яка використовується для обчислення нижніх оцінок вартості гамільтонових маршрутів. Оптимальний розв’язок задачі про призначення для отриманої матриці можна знайти за час O(n²). Запропоновано алгоритм за схемою гілок та меж, який використовує швидкий алгоритм розв’язку задачі про призначення в якості нижньої оцінки вартості розв’язку. Solutions’ search for Traveling Salesman task’s class in the binary branching scheme of branch-and-bound method can be noticeable accelerated by referring to a fast algorithm for solving a variant of the assignment problem, used to compute lower bounds for the Hamiltonian routes’ cost. Optimal solution for assignment problem for resulting matrix can be found in time O(n²). The algorithm of the branch and bound scheme that uses a fast algorithm for solving the assignment problem as a lower bound of the solution’s cost is proposed. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Обучающие и экспертные системы Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера Механізм прискорення обчислень в методі Литтла для розв’язку задач класу комівояжера Mechanism of Computations Acceleration in Little’s Method for Solving Traveling Salesman Class Tasks Article published earlier |
| spellingShingle | Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера Левченко, А.Ю. Морозов, А.В. Панишев, А.В. Обучающие и экспертные системы |
| title | Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера |
| title_alt | Механізм прискорення обчислень в методі Литтла для розв’язку задач класу комівояжера Mechanism of Computations Acceleration in Little’s Method for Solving Traveling Salesman Class Tasks |
| title_full | Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера |
| title_fullStr | Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера |
| title_full_unstemmed | Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера |
| title_short | Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера |
| title_sort | механизм ускорения вычислений в методе литтла для решения задач класса коммивояжера |
| topic | Обучающие и экспертные системы |
| topic_facet | Обучающие и экспертные системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/60701 |
| work_keys_str_mv | AT levčenkoaû mehanizmuskoreniâvyčisleniivmetodelittladlârešeniâzadačklassakommivoâžera AT morozovav mehanizmuskoreniâvyčisleniivmetodelittladlârešeniâzadačklassakommivoâžera AT paniševav mehanizmuskoreniâvyčisleniivmetodelittladlârešeniâzadačklassakommivoâžera AT levčenkoaû mehanízmpriskorennâobčislenʹvmetodílittladlârozvâzkuzadačklasukomívoâžera AT morozovav mehanízmpriskorennâobčislenʹvmetodílittladlârozvâzkuzadačklasukomívoâžera AT paniševav mehanízmpriskorennâobčislenʹvmetodílittladlârozvâzkuzadačklasukomívoâžera AT levčenkoaû mechanismofcomputationsaccelerationinlittlesmethodforsolvingtravelingsalesmanclasstasks AT morozovav mechanismofcomputationsaccelerationinlittlesmethodforsolvingtravelingsalesmanclasstasks AT paniševav mechanismofcomputationsaccelerationinlittlesmethodforsolvingtravelingsalesmanclasstasks |