Метод решения гамильтоновой задачи коммивояжера

Предлагается двухэтапный метод поиска решения гамильтоновой задачи коммивояжера, который либо находит решение поставленной задачи, либо корректно устанавливает, что задача неразрешима. Разработанный метод имеет значительно меньшую потребность в вычислительных ресурсах, чем известные алгоритмы....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2008
Автори:	Гаращенко, И.В., Морозов, А.В., Панишев, А.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2008
Теми:	Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/7139
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Метод решения гамильтоновой задачи коммивояжера / И.В. Гаращенко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2008. — № 3. — С. 630-637. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-7139
record_format	dspace
spelling	irk-123456789-71392010-03-25T12:01:08Z Метод решения гамильтоновой задачи коммивояжера Гаращенко, И.В. Морозов, А.В. Панишев, А.В. Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Предлагается двухэтапный метод поиска решения гамильтоновой задачи коммивояжера, который либо находит решение поставленной задачи, либо корректно устанавливает, что задача неразрешима. Разработанный метод имеет значительно меньшую потребность в вычислительных ресурсах, чем известные алгоритмы. Пропонується двоетапний метод пошуку розв’язання гамільтонової задачі комівояжера, який або знаходить розв’язання поставленої задачі, або коректно встановлює, що задача не має розв’язання. Розроблений метод має значно меншу потребу в обчислювальних ресурсах, ніж відомі алгоритми. The two-stage method is offered for solving the Hamilton commercial traveller problem which either finds a solution or correctly specifies that task in unsolvable. Developed method has significantly lesser computational power requirements than known analogues. 2008 Article Метод решения гамильтоновой задачи коммивояжера / И.В. Гаращенко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2008. — № 3. — С. 630-637. — Бібліогр.: 8 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/7139 51:330.115 ru Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем
spellingShingle	Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Гаращенко, И.В. Морозов, А.В. Панишев, А.В. Метод решения гамильтоновой задачи коммивояжера
description	Предлагается двухэтапный метод поиска решения гамильтоновой задачи коммивояжера, который либо находит решение поставленной задачи, либо корректно устанавливает, что задача неразрешима. Разработанный метод имеет значительно меньшую потребность в вычислительных ресурсах, чем известные алгоритмы.
format	Article
author	Гаращенко, И.В. Морозов, А.В. Панишев, А.В.
author_facet	Гаращенко, И.В. Морозов, А.В. Панишев, А.В.
author_sort	Гаращенко, И.В.
title	Метод решения гамильтоновой задачи коммивояжера
title_short	Метод решения гамильтоновой задачи коммивояжера
title_full	Метод решения гамильтоновой задачи коммивояжера
title_fullStr	Метод решения гамильтоновой задачи коммивояжера
title_full_unstemmed	Метод решения гамильтоновой задачи коммивояжера
title_sort	метод решения гамильтоновой задачи коммивояжера
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2008
topic_facet	Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем
url	http://dspace.nbuv.gov.ua/handle/123456789/7139
citation_txt	Метод решения гамильтоновой задачи коммивояжера / И.В. Гаращенко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2008. — № 3. — С. 630-637. — Бібліогр.: 8 назв. — рос.
work_keys_str_mv	AT garaŝenkoiv metodrešeniâgamilʹtonovojzadačikommivoâžera AT morozovav metodrešeniâgamilʹtonovojzadačikommivoâžera AT paniševav metodrešeniâgamilʹtonovojzadačikommivoâžera
first_indexed	2025-07-02T09:58:14Z
last_indexed	2025-07-02T09:58:14Z
_version_	1836528744349564928
fulltext	«Искусственный интеллект» 3’2008 630 8Г УДК 51:330.115 И.В. Гаращенко, А.В. Морозов, А.В. Панишев Житомирский государственный технологический университет, Украина org_giv1@us.ztu.edu.ua Метод решения гамильтоновой задачи коммивояжера Предлагается двухэтапный метод поиска решения гамильтоновой задачи коммивояжера, который либо находит решение поставленной задачи, либо корректно устанавливает, что задача неразрешима. Разработанный метод имеет значительно меньшую потребность в вычислительных ресурсах, чем известные алгоритмы. Введение В статье формулируются признаки негамильтоновости графа, опираясь на которые еще на первом этапе решения задачи можно определить, разрешима ли она. Это дает возможность на втором этапе искать оптимальное решение. Сформулируем гамильтонову задачу коммивояжера (ГЗК). Задан связный граф H = (V, U) без петель и кратных рёбер, V – множество вершин, V n= , U – множество рёбер. Ребру { }i, j U∈ приписан вес (стоимость) 0ijd Z +∈ , , 1, i j n= , 0Z + – множество неотрицательных чисел. Симметричная матрица весов ij n d   , где 0ijd Z +∈ , если { }i, j U∈ , и ijd = ∞ иначе, i j≠ , iid = ∞ , 1, i n= , полностью определяет взвешенный граф H = (V, U). Граф H = (V, U) гамильтонов, если он содержит гамильтонов цикл, то есть простой цикл, проходящий по всем вершинам V точно один раз. Гамильтонову циклу z поставлена в соответствие стоимость ( )D z , равная сумме весов его рёбер. ГЗК состоит в нахождении гамильтонова цикла z* минимальной стоимости D(z). Поставленная задача NP – трудна [1]. Известные методы её решения представ- лены схемами организации полного перебора всех циклов в графе Н [2-5]. Практи- ческая реализация этих методов проблематична даже с применением самых мощных компьютерных систем. ГЗК характеризуется тем, что она не всегда разрешима. Поэтому единственным методом поиска гамильтонова цикла минимальной стоимости z является метод, который либо строит z* , если ГЗК разрешима, либо корректно устанавливает, что граф H = (V, U) негамильтонов. Основной результат Поиск решения будем выполнять в два этапа. На первом этапе проверяются достаточные условия негамильтоновости графа H = (V, U). ГЗК не разрешима, если выполнено хотя бы одно из достаточных условий негамильтоновости графа. Очевидно, что если граф Н содержит концевые вершины, то ГЗК не имеет решений. Менее очевидным является условие негамильтоновости графа, содержащего Метод решения гамильтоновой задачи коммивояжера «Штучний інтелект» 3’2008 631 8Г точки сочленения. Точкой сочленения называется вершина, при удалении которой вместе с инцидентными ей рёбрами, образуется несвязный граф [6], [7]. Иначе говоря, если v – точка сочленения связного графа Н, то граф Н – v несвязен (рис. 1). e c d b a f g h j i e c d b a f g f h j ib а) б) Рисунок 1 – а) Граф Н с точками сочленения b и f; б) компоненты связности, как результат удаления вершин b и f Утверждение. Если граф H = (V, U) содержит точки сочленения, то он негамильтонов. Доказательство. Вершина v связного графа является точкой сочленения тогда и только тогда, когда существуют две другие вершины x и y, такие, что любая цепь между x и y содержит вершину v. Но в гамильтоновом цикле, кроме цепи (х, …, v, …, y) должна быть цепь (y, …, х), которая не проходит через вершину v. Следствие. Пусть связный граф H = (V, U) содержит цикл z = (p, q, …, t, p), где 2pδ > , 2q t...δ δ= = = . Тогда граф Н негамильтонов. Доказательство. Рассмотрим пару вершин f и j , f z∈ , j z∉ . Так как граф связен, то любая цепь, соединяющая вершины f и j , проходит через вершину p . Следовательно, вершина р является точкой сочленения. На рис. 2 представлен граф Н, удовлетворяющий условиям следствия. 1 2 4 3 5 6 7 8 Рисунок 2 – Граф Н содержит цикл (3, 2, 1, 4, 3), где 3 4δ = , 2 1 4 2δ δ δ= = = и поэтому негамильтонов Распознавание точек сочленения в связном графе H = (V, U) выполняется с трудоёмкостью O(\|V\|+\|U\|) [6]. На втором этапе ищется решение ГЗК z* для графа, не содержащего концевых вершин и точек сочленения. Алгоритм поиска z* построен в соответствии с классической схемой метода ветвей и границ, вызывающей процедуру решения задачи о назначениях (ЗН) для вычисления оценок снизу величины ( )D z* [4]. Вместе с тем, он имеет присущие только ему особенности, которые в процессе ветвления позволяют определить, какие подзадачи ГЗК не имеют решения. Гаращенко И.В., Морозов А.В., Панишев А.В. «Искусственный интеллект» 3’2008 632 8Г Рассмотрим матрицу весов ij n d   ГЗК. Чтобы найти оценку снизу искомой ве- личины ( )D z* , требуется для этой матрицы решить задачу о назначениях (ЗН). Но ЗН с матрицей стоимостей ij n d   содержит часть элементов ijd = ∞ и может не иметь решения. Следовательно, для вычисления нижних оценок в процессе поиска z* требуется алгоритм, который или корректно находит решение ЗН, или строго фиксирует, что ЗН неразрешима. Так работает модификация алгоритма Кана- Мункреса, предложенная в [4]. Алгоритм Кана-Мункреса решает ЗН на максимум в предположении, что все элементы ijd ≠ ∞ , i j≠ . Входом модифицированного алгоритма служит матрица ij n d ′  , где ij ijd d d= − , если ijd ≠ ∞ , и ijd ′ = −∞ иначе, d ≠ ∞ – максимальный эле- мент матрицы ij n d   . Тогда, если существует решение ЗН на максимум для матрицы ij n d ′  , то оно является решением ЗН на минимум для матрицы ij n d   . Стоимости ре- шения ( )C π и ( )C π′ соответственно для матриц ij n d   и ij n d ′  связаны равенством ( ) ( )C nd Cπ π′= − . Модифицированный алгоритм Кана-Мункреса ищет решение ЗН в двудольном графе ( ), , K X Y E , X = Y n= , 2E U= , отвечающем матрице ij n d ′  , в котором вер- шина ix X∈ соединена с вершиной jy Y∈ ребром ( ),i jx y с весом ( ),i jd x y = ijd ≠ ∞ . ЗН разрешима, если в графе ( ), , K X Y E построено совершенное паросочетание π с максимальной суммой весов рёбер. ЗН неразрешима, если граф (K X , ), Y E не содержит совершенных паросочетаний. Детальное описание модификации алгоритма Кана-Мункреса представлено в [4]. Её основной конструкцией является известная процедура поиска совершенного паро- сочетания в двудольном не взвешенном графе ( ), , H X Y E , X Y= , 2E U= , допол- ненная средствами, устанавливающими при каком количестве элементов ijd = −∞ и их расположении в матрице ij n d ′  ЗН неразрешима [4], [6]. Как алгоритм Кана- Мункреса, так и его модификация характеризуется трудоёмкостью, оцениваемой величиной ( )4O n [6]. Алгоритм поиска z* выполняется по схеме метода ветвей и границ, предложенной в [2] для решения симметричной ЗК. Эта схема в комбинации с модификацией алгоритма Кана-Мункреса применима и для решения ГЗК. Пусть построено совершенное паросочетание π. Оно доставляет целевому функ- ционалу ЗН минимум ( )C π , принимаемый за нижнюю оценку стоимости искомого цикла z* . Рассматривая паросочетание π как перестановку столбцов матрицы стоимостей, представим его цикловым разложением, то есть в виде совокупности непересекающихся циклов. Цикловое разложение перестановки π и оценка ( )C π образуют корень дерева ветвлений. Перестановка π , представленная единственным циклом, является решением z* ГЗК. Его стоимость равна ( )C π . Метод решения гамильтоновой задачи коммивояжера «Штучний інтелект» 3’2008 633 8Г В общем случае решение ЗН содержит несколько непересекающихся циклов. Выберем из них цикл σ = ( 1v , 2v ,…, kv , )1v с наименьшим числом рёбер. Удалим все решения ЗН, которые содержат цикл σ , не потеряв при этом в исходной матрице ни одного допустимого решения z . Поскольку хотя бы одно из k рёбер ( )1 2,v v , ( )2 3,v v ,…, ( )1,kv v не должно входить в z, то множество всех решений ЗН можно представить разбиением на k подмножеств. ЗН с исходной матрицей ij n d   обозна- чим 0P . Тогда 0P разбивается на k подзадач 1P , 2P ,…, kP . Каждой из них взаимно однозначно соответствует ребро цикла σ , вес которого полагается в матрице ij n d   равным ∞ , а все остальные веса остаются без изменений. В матрице ij n d ′  ЗН на максимум этому ребру приписывается вес −∞ . Тогда, если существует решение ГЗК, то оно принадлежит множеству решений какой-либо из подзадач 1P , 2P , …, kP , представленных вершинами дерева ветвлений, исходящими из вершины 0P . В каждой подзадаче iP , 1, i k= , можно добиться исключения не только решений, содержащих цикл σ , но и решений, включающих циклы с вершинами из множества { }1 2, ,..., kS v v v= . С этой целью в матрице стоимостей подзадачи iP , полученной из 0P присвоением элементу 1v vi id + , 1 i , k= , 1 1kv v+ = , веса ∞ , положим v vi jd = ∞ для всех { }i iv S \ v∈ . В соответствующей матрице стоимостей подзадачи ЗН на максимум каж- дый элемент v vi jd получает вес −∞ . Для ЗН на максимум, соответствующей подзадаче iP , 1, i k= , построим моди- фикацией алгоритма Кана-Мункреса перестановку iπ , если iP разрешима, или определим, что она не имеет решений. Если подзадача iP неразрешима, то соот- ветствующая ей вершина в дереве ветвлений не имеет допустимого продолжения. Предположим, что из k подзадач iP разрешимы 1k подзадач isP , i∈{1, 2, …, k}, 1, s k= , то есть построены оптимальные перестановки isπ и вычислены доставляе- мые ими значения ( )isC π . Очевидно, стоимость искомого гамильтонова цикла z* можно ограничить снизу величиной ( ) { }{ }11 2 1 isC min C \| i , ,..., k , s , kπ= ∈ = . Рассмотрим подзадачу qP , для которой ( )qC Cπ = . Если решение qπ является гамильтоновым циклом, то оно будет и решением ГЗК. В противном случае перестановка qπ образует несколько непересекающихся циклов. Тогда вершина qP дерева решений объявляется вершиной ветвления [2]. Задача qP разбивается на под- задачи, решения которых не содержат цикла минимальной длины σ из разложения перестановки qπ . В решениях подзадач исключены также все циклы, порожденные на множестве вершин σ . Выполнив модификацию алгоритма Кана-Мункреса для Гаращенко И.В., Морозов А.В., Панишев А.В. «Искусственный интеллект» 3’2008 634 8Г каждой полученной подзадачи, определим 2k разрешимых подзадач qsP , q∈{1, 2, …, 1k }, 21, s k= . Теперь текущей нижней границей стоимости оптимального гамиль- тонова цикла z* является величина ( ) { }{ }{ 1 21, 2, ..., 1 qsC min min C \| q k , s , kπ= ∈ = , ( ){ ismin C \|π { }1, 2, ..., i k∈ , { }11, 2, ..., s k∈ , }}si q≠ , которой соответствует задача pP . Если все подзадачи, полученные из задачи qP неразрешимы, то вершине ветвления дерева решений соответствует задача pP с текущей оценкой ( ) { } { }{ }11, 2, ..., , 1, 2, ..., , i ssC min C \| i k s k i qπ= ∈ ∈ ≠ . Дальнейшее ветвление для вершины pP осуществляется точно так же, как и для вершины qP . Поиск решения ГЗК завершается в одном из двух случаев. В первом случае алгоритм находит гамильтонов цикл z* ГЗК, который является решением ЗН с текущим значением С. Во втором случае алгоритм устанавливает, что все конечные вершины дерева решений не поддаются дальнейшему ветвлению, и, следовательно, ГЗК неразрешима. Пример Для графа H = (V, U), изображенного на рис. 3, и входной матрицы стоимостей 8ijd   выполним поиск решения ГЗК. Граф Н не имеет висячих вершин и точек сочленения. Поэтому нельзя утверждать, что граф Н негамильтонов. Для матрицы 8ijd   выполним поиск решения ЗН 0P , применив модифицированный алгоритм Кана-Мункреса [4]. 6 5 2 8 1 7 3 4 8ijd   = 1 2 3 4 5 6 7 8 1 ∞ ∞ 9 5 10 6 11 4 2 ∞ ∞ ∞ ∞ 11 4 9 4 3 9 ∞ ∞ 4 ∞ ∞ 2 ∞ 4 5 ∞ 4 ∞ ∞ 11 9 ∞ . 5 10 11 ∞ ∞ ∞ 12 ∞ ∞ 6 6 4 ∞ 11 12 ∞ ∞ ∞ 7 11 9 2 9 ∞ ∞ ∞ ∞ 8 4 4 ∞ ∞ ∞ ∞ ∞ ∞ Рисунок 3 – Граф H = (V, U) и матрица стоимостей его рёбер Метод решения гамильтоновой задачи коммивояжера «Штучний інтелект» 3’2008 635 8Г Алгоритм ищет решение ЗН на максимум для матрицы. 8ijd ′  = 1 2 3 4 5 6 7 8 1 −∞ −∞ 3 7 2 6 1 8 2 −∞ −∞ −∞ −∞ 1 8 3 8 3 3 −∞ −∞ 8 −∞ −∞ 10 −∞ 4 7 −∞ 8 −∞ −∞ 1 3 −∞ 5 2 1 −∞ −∞ −∞ 0 −∞ −∞ . 6 6 8 −∞ 1 0 −∞ −∞ −∞ 7 1 3 10 3 −∞ −∞ −∞ −∞ 8 8 8 −∞ −∞ −∞ −∞ −∞ −∞ Оптимальным решением ЗН 0P как на максимум, так и на минимум является перестановка π = (4, 8, 7, 1, 6, 5, 3, 2), ( )C π′ = 50. Минимум целевого функционала ЗН 0P ( )C π = 46 ограничивает снизу стоимость искомого решения z* ГЗК. Цикловое раз- ложение перестановки π имеет следующий вид: 1σ = (1, 4, 1), 2σ = (2, 8, 2), 3σ = (3, 7, 3), 4σ = (5, 6, 5). Каждый цикл разложения содержит два ребра. Поэтому для ветвления выберем любой из четырёх, например, 3σ = (3, 7, 3). На рис. 4 представлено дерево ветвлений, отображающих процесс поиска гамильтонова цикла z* ( )C π . Все результаты вычислений, формирующие дерево ветвлений, содержатся в табл. 1. 0P 1P 2P 12P 11P 13P 121P 122P 22P 21P 23P 221P 222P ( ) 46C π = ( )1 49C π = ( )11 57C π = ( )13 58C π = ( )12 52C π = ( )121 56C π = ∅ ( )2 49C π = ( )21 63C π = ( )23 57C π = ( )22 52C π = ( )221 56C π = ∅ 34d = −∞ 73d = −∞ 37d = −∞ 73d = −∞ 43d = −∞ 47d = −∞ 73d = −∞ 74d = −∞ 56d = −∞ 65d = −∞ 34d = −∞ 37d = −∞ 73d = −∞ 74d = −∞ 43d = −∞ 47d = −∞ 56d = −∞ 65d = −∞ Рисунок 4 – Дерево ветвлений для ГЗК с числовыми данными примера 1 ЗН 0P в результате ветвления порождает две задачи 1P и 2P на максимум с матрицами стоимостей, полученными из 8ijd ′  . В матрице 8ijd ′  для задачи 1P на −∞ заменяется элемент 37 'd =10, а для задачи 2P – элемент 73d =10. Модифицированный алгоритм Кана-Мункреса находит решения 1π и 2π этих задач и определяет стоимости полученных решений ( )1C π = ( )2C π = 49. Для ветвления можно выбрать любую из подзадач с одинаковыми оценками. Выберем задачу 1P . Перестановку 1π исчерпывают Гаращенко И.В., Морозов А.В., Панишев А.В. «Искусственный интеллект» 3’2008 636 8Г два цикла, из которых цикл (3, 4, 7, 3) имеет минимальную длину. Исключение решений ЗН, содержащих этот цикл и всех циклов с вершинами из множества {3, 4, 7}, даёт три задачи 11P , 12P , 13P на максимум и соответствующие им матрицы стоимостей. В первой матрице 37d ′ = 34d ′ = −∞ , во второй 37d ′ = 43d ′ = 47d ′ = −∞ , в третьей 37d ′ = 73d ′ = 74d ′ = −∞ . Все три задачи разрешимы. Стоимости их решений равны ( )11C π = 57, ( )12C π = 52, ( )13C π = 58. На текущий момент все концевые вершины дерева ветвлений 2P , 11P , 12P , 13P активны. Так как C min= ( ){ 2C π , ( )11C π , ( )12C π , ( )}13C π = min {49, 57, 52, 58} = 49, вершина 2P оказывается вершиной ветвления. Таблица 1 – Результаты вычислений, формирующие дерево ветвлений ЗН Решение ЗН Цикловое разложение решения ЗН 0P π = (4, 8, 7, 1, 6, 5, 3, 2), ( ) 46C π = (1, 4, 1) (2, 8, 2) (3, 7, 3) (5, 6, 5) 1P 1π = (5, 8, 4, 7, 6, 2, 3, 1), ( )1 49C π = (1, 5, 6, 2, 8, 1) (3, 4, 7, 3) 2P 2π = (5, 8, 7, 3, 6, 2, 4, 1), ( )2C π = 49 (1, 5, 6, 2, 8, 1) (3, 7, 4, 3) 11P 11π = (4, 8, 1, 7, 6, 5, 3, 2), ( )11 57C π = (1, 4, 7, 3, 1) (2, 8, 2) (5, 6, 5) 12P 12π = (8, 7, 4, 1, 6, 5, 3, 2), ( )12 52C π = (1, 8, 2, 7, 3, 4, 1) (5, 6, 5) 13P 13π = (3, 7, 4, 3, 6, 5, 2, 1), ( )13 58C π = (1, 8, 1) (2, 7, 2) (3, 4, 3) (5, 6, 5) 21P 21π = (8, 7, 1, 3, 6, 5, 4, 2), ( )21 63C π = (1, 8, 2, 7, 4, 3, 1) (5, 6, 5) 22P 22π = (4, 8, 7, 3, 6, 5, 2, 1), ( )22 52C π = (1, 4, 3, 7, 2, 8, 1) (5, 6, 5) 23P 23π = (3, 8, 7, 1, 6, 5, 4, 2), ( )23 57C π = (1, 3, 7, 4, 1) (2, 8, 2) (5, 6, 5) 121P 121π = (8, 7, 4, 6, 1, 5, 3, 2), ( )121 56C π = (1, 8, 2, 7, 3, 4, 6, 5, 1) 122P ЗН неразрешима – 221P 222π = (5, 8, 7, 3, 6, 4, 2, 1), ( )52 56C π = (1, 5, 6, 4, 3, 7, 2, 8, 1) 222P ЗН неразрешима – Задача 2P разбивается на три подзадачи 21P , 22P , 23P со стоимостями решений ( )21 63C π = , ( )22 52C π = , ( )23 57C π = . Из текущего множества активных вершин { 11P , 12P , 13P , 21P , 22P , }23P дерева ветвлений выберем вершину с минимальной оценкой C min= {57, 52, 58, 63, 52, 57} = 52. Равноправными претендентами на вершину ветвления являются вершины 12P , 22P . Для дальнейшего разбиения выберем подзадачу 12P . В циклическом разложении перестановки 12π цикл (5, 6, 5) имеет минимальную длину. Поэтому задача 12P порождает две подзадачи 121P и 122P . Модифицированный алгоритм Кана-Мункреса строит решение ЗН 121P в виде гамильтонова цикла (1, 8, 2, 7, 3, 4, 6, 5, 1) стоимостью ( )121 56C π = и устанавливает, что задача 122P не имеет решений. Метод решения гамильтоновой задачи коммивояжера «Штучний інтелект» 3’2008 637 8Г С построением гамильтонова цикла стоимостью 56 отпадает необходимость ветвления всех активных вершин с не меньшими оценками. Остаётся единственная ЗН 22P , стоимость решения которой равна 52. Циклическое разложение перестановки 22π включает цикл (5, 6, 5), вызывающий две новые подзадачи 121P и 222P . ЗН 222P не имеет решения, а решением ЗН 221P является гамильтонов цикл (1, 5, 6, 4, 3, 7, 2, 8, 1), у которого суммарный вес рёбер ( )221C π равен 56. Стоимость построенных гамильтоновых циклов меньше, чем нижняя граница в любой концевой вершине дерева ветвлений. Таким образом, оптимальным решением ГЗК являются циклы 1 121 z π= = (1, 8, 2, 7, 3, 4, 6, 5, 1), 2 221 z π= = (1, 5, 6, 4, 3, 7, 2, 8, 1). Заключение Метод реализован программно на языке С#. Вычислительный эксперимент проведен на машине Seleron 1,8 Гц с оперативной памятью 2 Гб. Генерировалось не менее 100 матриц размерности 40, 60, 80, 100, которые заполнялись на 75 % значениями из интервала 1 – 50, а на 25 % – ∞ . Полученные во время эксперимента результаты содержатся в табл. 2. Таблица 2 – Результаты, полученные во время эксперимента Размерность матриц 40 60 80 100 Минимальное время решения, с 10,25 15,78 23,27 39,18 сек Максимальное время решения, мин 4,58 26,22 65,26 121,75 мин Литература 1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с. 2. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с. 3. Бондаренко М.Ф., Белоус Н.В., Руткас А.Г. Компьютерная дискретная математика. – Харьков: «Компания СМИТ», 2004. – 480 с. 4. Панишев А.В., Плечистый Д.Д. Модели и методы оптимизации в проблеме коммивояжера. – Житомир: ЖГТУ, 2006. – 300 с. 5. Вьялицин А.А. О перечислении гамильтоновых циклов // Дискретная математика. – 1991. – Т. 3, Вып. 3. – С. 46-49. 6. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 476 с. 7. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с. 8. Свами М., Тхуласираман К. Графы, сети, алгоритмы. – М.: Мир, 1984. – 454 с. І.В. Гаращенко, А.В. Морозов, А.В. Панішев Метод розв’язання гамільтонової задачі комівояжера Пропонується двоетапний метод пошуку розв’язання гамільтонової задачі комівояжера, який або знаходить розв’язання поставленої задачі, або коректно встановлює, що задача не має розв’язання. Розроблений метод має значно меншу потребу в обчислювальних ресурсах, ніж відомі алгоритми. I.V. Garashchenko, A.V. Morozov, A.V. Panishev The Method for Solving of Hamilton’s Commercial Traveller Problem The two-stage method is offered for solving the Hamilton commercial traveller problem which either finds a solution or correctly specifies that task in unsolvable. Developed method has significantly lesser computational power requirements than known analogues. Статья поступила в редакцию 25.06.2008.

Метод решения гамильтоновой задачи коммивояжера

Репозитарії

Схожі ресурси