Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне

Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне

В статье формулируется гамильтонова задача о сельском почтальоне, являющаяся обобщением задачи коммивояжера. Предлагается процедура вершинно-рёберного преобразования, которая выполняется непосредственно перед решением задачи. У статті формулюється гамільтонова задача про сільського листоношу, яка...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2009
Hauptverfasser: Морозов, А.В., Панишев, А.В.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут проблем штучного інтелекту МОН України та НАН України 2009
Schlagworte:
Системы принятия решений, планирования и моделирования
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/8170
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне / А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2009. — № 4. — С. 138-143. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-8170
record_format dspace
spelling Морозов, А.В.
Панишев, А.В.
2010-05-14T08:34:24Z
2010-05-14T08:34:24Z
2009
Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне / А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2009. — № 4. — С. 138-143. — Бібліогр.: 4 назв. — рос.
1561-5359
https://nasplib.isofts.kiev.ua/handle/123456789/8170
51:330.115
В статье формулируется гамильтонова задача о сельском почтальоне, являющаяся обобщением задачи коммивояжера. Предлагается процедура вершинно-рёберного преобразования, которая выполняется непосредственно перед решением задачи.
У статті формулюється гамільтонова задача про сільського листоношу, яка є узагальненням задачі комівояжера. Пропонується процедура вершинно-реберного перетворення, яка виконується безпосередньо перед розв’язанням задачі.
The Hamiltonian Rural Postman Problem which is generalisation of the Travelling Salesman Problem is formulated in this article. Procedure of vertex-edge transformation which is applied before a problem solving is offered.
ru
Інститут проблем штучного інтелекту МОН України та НАН України
Системы принятия решений, планирования и моделирования
Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне
Вершинно-реберні перетворення у гамільтоновій задачі про сільського листоношу
Vertex-edge Transformation in the Hamiltonian Rural Postman Problem
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне
spellingShingle Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне
Морозов, А.В.
Панишев, А.В.
Системы принятия решений, планирования и моделирования
title_short Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне
title_full Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне
title_fullStr Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне
title_full_unstemmed Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне
title_sort вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне
author Морозов, А.В.
Панишев, А.В.
author_facet Морозов, А.В.
Панишев, А.В.
topic Системы принятия решений, планирования и моделирования
topic_facet Системы принятия решений, планирования и моделирования
publishDate 2009
language Russian
publisher Інститут проблем штучного інтелекту МОН України та НАН України
format Article
title_alt Вершинно-реберні перетворення у гамільтоновій задачі про сільського листоношу
Vertex-edge Transformation in the Hamiltonian Rural Postman Problem
description В статье формулируется гамильтонова задача о сельском почтальоне, являющаяся обобщением задачи коммивояжера. Предлагается процедура вершинно-рёберного преобразования, которая выполняется непосредственно перед решением задачи. У статті формулюється гамільтонова задача про сільського листоношу, яка є узагальненням задачі комівояжера. Пропонується процедура вершинно-реберного перетворення, яка виконується безпосередньо перед розв’язанням задачі. The Hamiltonian Rural Postman Problem which is generalisation of the Travelling Salesman Problem is formulated in this article. Procedure of vertex-edge transformation which is applied before a problem solving is offered.
issn 1561-5359
url https://nasplib.isofts.kiev.ua/handle/123456789/8170
citation_txt Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне / А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2009. — № 4. — С. 138-143. — Бібліогр.: 4 назв. — рос.
work_keys_str_mv AT morozovav veršinnorebernoepreobrazovanievgamilʹtonovoizadačeoselʹskompočtalʹone
AT paniševav veršinnorebernoepreobrazovanievgamilʹtonovoizadačeoselʹskompočtalʹone
AT morozovav veršinnoreberníperetvorennâugamílʹtonovíizadačíprosílʹsʹkogolistonošu
AT paniševav veršinnoreberníperetvorennâugamílʹtonovíizadačíprosílʹsʹkogolistonošu
AT morozovav vertexedgetransformationinthehamiltonianruralpostmanproblem
AT paniševav vertexedgetransformationinthehamiltonianruralpostmanproblem
first_indexed 2025-11-27T06:45:11Z
last_indexed 2025-11-27T06:45:11Z
_version_ 1850802235277049856
fulltext «Искусственный интеллект» 4’2009 138 3М УДК 51:330.115 А.В. Морозов, А.В. Панишев Житомирский государственный технологический университет, Украина morozov.andriy@gmail.com Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне В статье формулируется гамильтонова задача о сельском почтальоне, являющаяся обобщением задачи коммивояжера. Предлагается процедура вершинно-рёберного преобразования, которая выполняется непосредственно перед решением задачи. Введение Многочисленные результаты, накопленные в изучении проблемы коммивояже- ра, непрерывно развиваются, охватывая актуальные вопросы разработки и совер- шенствования методов комбинаторной оптимизации и их применения. Далеко не для каждой прикладной задачи типа коммивояжера известны алгоритмы поиска решения с показателями эффективности, пригодными в реальных ситуациях. Одной из таких задач является задача о сельском почтальоне, формулируемая следующим образом [1]. Задан связный взвешенный граф H = (V, U) с множеством вершин V, V n , и множеством рёбер U. Каждому ребру  i, j U приписан вес 0ijd Z  , i j , 1i, j ,n , 0Z  – множество неотрицательных целых чисел. Граф H полностью определяется сим- метричной матрицей стоимости ij n d   , где 0ijd Z  , если  i, j U , и ijd   , иначе, i j , 1i, j ,n , iid   , 1i, j ,n . На множестве U задано непустое подмножество рё- бер R. Требуется найти в графе H цикл, включающий каждое ребро из R и имеющий минимальную сумму весов всех рёбер. Обозначим z(R) гамильтонов цикл графа H, проходящий по всем рёбрам мно- жества R. Назовём гамильтоновой задачей о сельском почтальоне (ГЗСП) задачу, кото- рая состоит в нахождении гамильтонова цикла  *z R , минимизирующего функционал:        kl k ,l z R C z R d    . Заинтересованность в решении ГЗСП проявляется в том случае, когда требуется определить кольцевой маршрут на транспортной сети графа или района, моделируе- мой графом H = (V, U). Каждому пункту отправления (прибытия) сети соответствует вершина i V , V n  , а каждому ребру  i, j U отвечает отрезок дорожного полотна между парой соседних пунктов i и j. Ребро  i, j характеризуется весом (стоимостью) ijd , равным затратам на перемещение транспортного средства из i в j или из j в i. Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне «Штучний інтелект» 4’2009 139 3М Основной результат ГЗСП NP-полна, поскольку, в случае R   , она является NP-полной гамильтоно- вой задачей коммивояжера (ГЗК) [1]. В [2] предложен алгоритм, который корректно находит решение ГЗК, если граф H гамильтонов, и устанавливает её неразрешимость в противном случае. В основе предложенного алгоритма лежит схема ветвей и границ, выполняемая после проверки достаточных условий неразрешимости ГЗСП. Ясно, что трудоёмкость такой проверки должна быть ограничена полиномом от размера задачи. Непосредственное применение алгоритма ветвей и границ из [2] не позволяет решить ГЗСП. Включение в искомый гамильтонов цикл заданного подмножества рё- бер R   оказывается настолько сильным ограничением, что требует иного подхода к организации ветвления и вычисления нижних оценок для   *C z R . В данной рабо- те предлагается модификация классического метода ветвей и границ (метода Литтла), обеспечивающая нахождение решения как в ГЗСП, так и в ГЗК. Очевидно, и ГЗК, и ГЗСП не имеют решений, если граф H содержит концевые (ви- сячие) вершины. Висячие вершины в графе H находятся тривиально за время  O V . Задачи неразрешимы, когда граф H имеет точку сочленения [2], [3]. Чтобы определить, со- держит ли граф H точку сочленения, требуется  O V U элементарных операций [3]. Нетрудно увидеть, что ГЗСП неразрешима, если в графе Н: а) подмножество рё- бер множества R образует негамильтонов цикл; б) существует вершина, инцидентная трём или более рёбрам из R. Следовательно, граф Н, в котором множество рёбер R не образует совокупности вершинно-непересекающихся цепей, не содержит цикла z(R). На проверку условий а) и б) достаточно времени, ограниченного величиной  O V U . Пусть граф H = (V, U) не имеет висячих вершин и точек сочленения, а множест- во его рёбер R U в ГЗСП представлено вершинно-непересекающимися цепями. Выполним вершиннно-рёберное преобразование (ВРП) графа Н, в результате которого устанавливаются достаточные условия неразрешимости ГЗСП, дополняющие пере- численные условия. S0. H = (V, U) – граф, не содержащий висячих вершин и точек сочленения; непустое множество рёбер R U образует совокупность Z вершинно-непересекающихся цепей. S1. Если число цепей совокупности Z равно R , то положить R R  , перейти к шагу S5. S2. Для каждой цепи  a,b,...,c,d Z удалить все рёбра из U R , которые: а) соединяют её любые две вершины, б) инцидентные одной вершине из  b,...,c – и определить степени всех вершин множества V. Если хотя бы одна вершина в полученном остовном подграфе графа Н является изолированной или висячей, то ГЗСП не имеет решения. S3. Заменить каждую цепь  a,b,...,c,d на ребро  a,d , присвоив ему вес, равный сумме весов рёбер цепи. S4.  H V ,U   – граф, построенный после выполнения шага S3, R– множество всех рёбер, полученных из R в результате построения H  . S5. Положить 0R  . S6. Если граф не содержит вершин степени 2, то конец. S7. Если множество 0R R не образует паросочетания, то конец: ГЗСП неразрешима. S8. Каждую цепь  p,q,...,t ,w со степенями вершин 2p w,   , 2q t...    заменить на ребро  p,w с весом, равным сумме весов её рёбер; удалить из R и 0R все рёбра цепи, принад- Морозов А.В., Панишев А.В. «Искусственный интеллект» 4’2009 140 3М лежащие R и 0R ; положить  0 0R R p,w  ; если существует еще одно ребро   0p,w R R  , удалить его. S9. Если множество 0R R не образует совокупности вершинно-пересекающихся цепей, то конец: ГЗСП неразрешима. S10. Если степени всех вершин построенного графа равны 2, то конец: ГЗСП имеет решение, иначе положить 0R  ; для каждой цепи  p,w,...,r ,v , все рёбра которой содержатся в 0R R , исключить рёбра, инцидентные вершинам w,...,r ; исключить из R рёбра цепи, принадлежащие R ; заменить цепь на ребро  p,v . Если существует еще одно ребро, соединяющее p и v, удалить его; установить  0 0R R p,v  , pv pw rvd d ... d   ; перейти к шагу S6. Каждая цепь рёбер множества R является простой цепью, т.е. такой, у которой все вершины (а значит, и рёбра) различны. В противном случае она образует негамиль- тонов цикл, и, следовательно, ГЗСП не имеет решения. В гамильтонов цикл  z R долж- ны входить все рёбра, образующие простую цепь  x,a,b,...,c,d , y . В него не могут входить рёбра, соединяющие пары вершин  a,b,...,c,d , и рёбра, инцидентные одной, вершине в  b,...,c . Поэтому их следует удалить, рассматривая ГЗСП на остовном подграфе графа H, в котором могут содержаться изолированные и висячие верши- ны. Отсюда следует корректность действий, выполняемых на шаге S2. Пусть остовный граф не содержит изолированных и висячих вершин, тогда вер- шины a,b,...,c,d имеют степени 2 2 2a b c d, ... ,        . Гамильтонов цикл  z R должен проходить все рёбра цепи  a,b,...,c,d , которую можно заменить на ребро  a,d весом, равным сумме весов её рёбер. Множество R, содержащееся в цикле  z R , если он существует, представлено совокупностью Z вершинно-непересекающихся цепей. Поэтому каждую цепь из Z с двумя и более рёбрами следует рассматривать после выполнения шага S3 как одно ребро в цепи  z R . На шаге S3 находится граф  H V ,U   , V V ,U U   и мно- жество рёбер R , R Z  , которое включено в гамильтонов цикл  z R , соответст- вующий  z R . Процесс ВРП прекращается на шаге S6, если степени всех вершин графа H  больше 2. В этом случае либо оказываются выполненными достаточные ус- ловия того, что ГЗСП не имеет решения, либо следует перейти к построению  z R по схеме метода ветвей и границ. Если в графе H  содержатся вершины степени 2, то на шаге S5 формируется множество рёбер 0R . Каждое ребро   0p,w R , полученное на шаге S8, заменяет цепь  p,q,...,t ,w , 2p w,   , 2q t...    , рассматриваемую как часть гамильтонова цик- ла  z R . Поэтому из R и 0R можно удалить все её рёбра, которые содержатся в R или 0R . Очевидно, ГЗСП разрешима, если в графе, построенном на шаге S8, сущест- вует гамильтонов цикл, проходящий по всем рёбрам множества 0R R . Если после выполнения шага S8 множество 0R R представлено одним ребром, то ГЗСП имеет единственное решение. Она не имеет решения, если найдется пара цепей, состоящих из рёбер 0R R и имеющих общую вершину. Перед выполнением шага S10 множество рёбер 0R R образует совокупность вершинно-непересекающихся цепей  p,w,...,r ,v . В графе, построенном на шаге S8, Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне «Штучний інтелект» 4’2009 141 3М для каждой цепи  p,w,...,r ,v удаляются рёбра, инцидентные вершинам из множест- ва  w,...,r , поскольку они не могут входить в решение ГЗСП. На шаге S10 вновь формируется множество 0R , в которое добавляется каждое ребро  p,w , заменяю- щее цепь  p,w,...,r ,v , а из R исключаются все рёбра, содержащиеся в R . Шаги S6 – S10 повторяются, пока не будет построен граф со степенями вершин, не равными 2. Тогда, рассматривая каждое ребро в 0R R построенного графа как однозвенную цепь, получим достаточное условие того, что граф Н не содержит гамильтонова цикла  z R . Таким образом, получен следующий результат. Утверждение. Если результатом ВРП графа Н является граф, в котором мно- жество рёбер 0R R не образует паросочетания, то ГЗСП не имеет решения. Следовательно, ГЗСП сводится к этой же задаче на графе  H V ,U , в котором: а) степени всех вершин больше 2, б) множество рёбер R, содержащееся в искомом гамильтоновом цикле, образует паросочетание R. Очевидно, 2 nR ,n V     , 2 nR ,n V     . Заметим, что величина R ограничивает пространство решений настолько, что оно мо- жет оказаться пустым. Пример Выполним алгоритм ВРП для графа Н, изображенного на рис. 1.             11 15 15 14 8 5 5 3 4 12 1 2R , , , , , , , , , , , ,         11 15 14 1 2 3 5 8 4 12Z , , , , , , , , , . Предполагается, что все рёбра имеют единичный вес. Заметим, что граф содер- жит гамильтонов цикл    1 2 6 7 4 12 3 5 8 9 10 11 15 14 13 1z R , , , , , , , , , , , , , , , . Остовный подграф графа Н, полученный на шаге S2 представлен на рис. 2. Рисунок 1 Рисунок 2 После выполнения шага S3 получим граф H  (рис. 3), где     11 14 3 8 1 2 4 12R , , , , , , ,     1114 3 8 1 2 4 12R , , , , , , , . Положим 0R  . Построенный граф имеет вершины степени 2, а мно- жество 0R R образует паросочетание. На шаге S8 каждая из цепей  11 14 13, , ,  8 9 10 11, , , ,  2 6 7, , сворачивается в реб- ро (рис. 4),       0 8 11 11 13 2 7R , , , , , ,       3 8 1 2 4 12R , , , , ,  . 1 2 6 7 8 9 10 11 12 13 14 15 3 4 5 1 2 6 7 8 9 10 11 12 13 14 15 3 4 5 Морозов А.В., Панишев А.В. «Искусственный интеллект» 4’2009 142 3М Рисунок 3 Рисунок 4 На шаге S10 0R  , цепи  3 8 11 13, , , и  1 2 7, , преобразуются в рёбра {3, 13} и {1, 7}. Результат преобразования изображен на рис. 5;   4 12R ,  ,     0 3 13 1 7R , , , . Построенный граф не является гамильтоновым циклом, содержит вершины степени 2, а множество 0R R образует парасочетание. Для построенного графа (рис. 5) повторяется шаг S8. На шаге S8 рассматриваются цепи  1 13 3, , и  1 7 4 12 3, , , , , каждая из которых за- меняется на ребро  1 3, ; R   ,   0 1 3R , . Степени всех вершин построенного гра- фа равны 2 (рис. 6), ГЗСП имеет решение. Рисунок 5 Рисунок 6 Поскольку множество 0R R представлено единственным кратным ребром  1 3, , ГЗСП имеет единственное решение. Выполним восстановление гамильтонова цикла. Для этого будем разворачивать рёбра полученного графа в порядке, обратном порядку сворачивания рёбер (рис. 7). Рисунок 7 Рисунок 8 Последней осуществлялась замена ребра  1 3, на цепь  1 7 4 12 3, , , , . Поэтому за- меняем ребро {1, 3} набором рёбер {1, 7}, {7, 4}, {4, 12}, {12, 3}, образующих цепь  1 7 4 12 3, , , , . Получаем граф, изображенный на рис. 8. 1 7 12 13 3 4 7 12 3 4 1 1 3 1 7 12 13 3 4 1 2 7 8 11 12 13 3 4 1 2 6 7 8 9 10 11 12 13 14 3 4 Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне «Штучний інтелект» 4’2009 143 3М Далее выполняем разворачивание ребра {1, 3}, заменяя его на рёбра {1, 13} и {13, 3}, поскольку оно было свернуто в цепь  1 13 3, , . Результат изображен на рис. 9. Далее осуществляется разворачивание ребра  1 7, , которое было заменено на цепь  1 2 7, , . Продолжая процесс, выполняем замены:        3 13 3 8 11 13 2 7 2 6 7, , , , , , , , ,         8 11 8 9 10 11 11 3 11 14 13, , , , , , , ,  ,       3 8 3 5 8 11 14 11 15 14, , , , , , ,  . В результате выполнения последовательности замен, получаем гамильтонов цикл  1 2 6 7 4 12 3 5 8 9 10 11 15 14 13 1, , , , , , , , , , , , , , , на рис. 10. Рисунок 9 Рисунок 10 Заключение Предложенная процедура вершинно-рёберного преобразования может быть ис- пользована непосредственно перед решением задачи [4]. В результате выполнения преобразования возможны следующие варианты: 1) найдено оптимальное решение гамильтоновой задачи о сельском почтальоне; 2) обнаружено, что задача не имеет решения; 3) получена задача меньшей размерности, требуется поиск решения задачи. Литература 1. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М. : Мир, 1982. 2. I. Garashchenko. Method of Finding Hamilton Routes in Transport Network / I. Garashchenko, A. Panishev // Artificial Intelligence and Decision Making. – ITHEA, Sofia. – 2008. – № 7. – Р. 43-48. 3. Теория расписаний и вычислительные машины / под. ред. Э.Г. Коффмана. – М. : Наука, 1984. 4. Garashchenko I. Method of Finding Hamilton Routesin Transport Network / Irina Garashchenko, Ana- toliy Panishev // Artificial Intelligence and Decision Making. – ITHEA, Sofia. – 2008. – № 7. – P. 43-48. А.В. Морозов, А.В. Панишев Вершинно-реберні перетворення у гамільтоновій задачі про сільського листоношу У статті формулюється гамільтонова задача про сільського листоношу, яка є узагальненням задачі комівояжера. Пропонується процедура вершинно-реберного перетворення, яка виконується безпосередньо перед розв’язанням задачі. A.V. Morozov, A. V. Panishev Vertex-edge Transformation in the Hamiltonian Rural Postman Problem The Hamiltonian Rural Postman Problem which is generalisation of the Travelling Salesman Problem is formu- lated in this article. Procedure of vertex-edge transformation which is applied before a problem solving is offered. Статья поступила в редакцию 01.06.2009. 1 2 6 7 8 9 10 11 12 13 14 15 3 4 5 1 7 12 13 2 4 3

Ähnliche Einträge