Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера

Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка n заменить значение какого-либо элемента на бесконечно большое число, то оптимальное решение ЗН для полученной матрицы находится за время О(n²)....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автори:	Левченко, А.Ю., Морозов, А.В., Панишев, А.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2011
Назва видання:	Штучний інтелект
Теми:	Обучающие и экспертные системы
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/60487
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2011. — № 4. — С. 406-416. — Бібліогр.: 4 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-60487
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-604872025-02-09T09:32:58Z Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера Швидкий алгоритм розв’язання задачі про призначення для знаходження нижньої межі вартості маршруту комівояжера Algorithm for Fast Solution of the Problem of Allocation for Lower Limit Weight of Salesman Route Левченко, А.Ю. Морозов, А.В. Панишев, А.В. Обучающие и экспертные системы Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка n заменить значение какого-либо элемента на бесконечно большое число, то оптимальное решение ЗН для полученной матрицы находится за время О(n²). Показано, що якщо в оптимальному розв’язку задачі про призначення (ЗП) та її матриці вартостей порядку n замінити значення якого-небудь елемента на нескінченно велике число, то оптимальний розв’язок ЗП для отриманої матриці знаходиться за час О(n²). It is shown that if to replace the value of any element by infinitely large number in the optimal solution for the problem of allocations and for its matrix of weights with size n, then the optimal solution of the problem of allocation for resulting matrix is found in a time О(n²). 2011 Article Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2011. — № 4. — С. 406-416. — Бібліогр.: 4 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/60487 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	Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка n заменить значение какого-либо элемента на бесконечно большое число, то оптимальное решение ЗН для полученной матрицы находится за время О(n²).
format	Article
author	Левченко, А.Ю. Морозов, А.В. Панишев, А.В.
author_facet	Левченко, А.Ю. Морозов, А.В. Панишев, А.В.
author_sort	Левченко, А.Ю.
title	Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера
title_short	Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера
title_full	Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера
title_fullStr	Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера
title_full_unstemmed	Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера
title_sort	быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2011
topic_facet	Обучающие и экспертные системы
url	https://nasplib.isofts.kiev.ua/handle/123456789/60487
citation_txt	Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2011. — № 4. — С. 406-416. — Бібліогр.: 4 назв. — рос.
series	Штучний інтелект
work_keys_str_mv	AT levčenkoaû bystryjalgoritmrešeniâzadačionaznačeniâhdlânahoždeniânižnejgranicystoimostimaršrutakommivoâžera AT morozovav bystryjalgoritmrešeniâzadačionaznačeniâhdlânahoždeniânižnejgranicystoimostimaršrutakommivoâžera AT paniševav bystryjalgoritmrešeniâzadačionaznačeniâhdlânahoždeniânižnejgranicystoimostimaršrutakommivoâžera AT levčenkoaû švidkijalgoritmrozvâzannâzadačípropriznačennâdlâznahodžennânižnʹoímežívartostímaršrutukomívoâžera AT morozovav švidkijalgoritmrozvâzannâzadačípropriznačennâdlâznahodžennânižnʹoímežívartostímaršrutukomívoâžera AT paniševav švidkijalgoritmrozvâzannâzadačípropriznačennâdlâznahodžennânižnʹoímežívartostímaršrutukomívoâžera AT levčenkoaû algorithmforfastsolutionoftheproblemofallocationforlowerlimitweightofsalesmanroute AT morozovav algorithmforfastsolutionoftheproblemofallocationforlowerlimitweightofsalesmanroute AT paniševav algorithmforfastsolutionoftheproblemofallocationforlowerlimitweightofsalesmanroute
first_indexed	2025-11-25T09:05:17Z
last_indexed	2025-11-25T09:05:17Z
_version_	1849752581873598464
fulltext	«Искусственный интеллект» 4’2011 406 7Л УДК 519.161 А.Ю. Левченко, А.В. Морозов, А.В. Панишев Житомирский государственный технологический университет, Украина dear_anton@yahoo.com, morozov.andriy@gmail.com, irinagar@rambler.ru Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка n заменить значение какого-либо элемента на бесконечно большое число, то оптимальное решение ЗН для полученной матрицы находится за время  2O n . Цель работы и постановка задачи Сформулируем задачу о назначениях (ЗН) для матрицы стоимостей ij n C c    , где ijc   при i j и 0ijc Z  или ijc   при i j , , 1,i j n , 0Z  – множество неотрицательных целых чисел. Найти     1 , n i i C min c     здесь      1 , 2 ,..., n    – перестановка n столбцов матрицы, а   1 ,     2 ,..., n  – оптимальная перестановка, или решение ЗН стоимостью  C    1 n ii c  ,  ic   , 1,i n . Заметим, что для матрицы С, содержащей элементы ijc   , i j , ЗН может не иметь решения. Предположим, что получена перестановка  . Рассматриваемая здесь задача состоит: а) в построении по известному решению  решения xy ЗН с матрицей стоимостей xyC , отличающейся от С только тем, что элемент       1 2, ,...,xy nc c c c   в С равен  в xyC ; б) время нахождения xy меньше, чем время, за которое можно определить  . Матрица С совпадает с матрицей стоимостей NP-трудной гамильтоновой задачи коммивояжера, решением которой является циклическая перестановка минимальной стоимости. Поскольку ЗН эффективно разрешима, то она используется как релаксация в точных и приближенных алгоритмах решения NP-трудных задач проблемы коммивояжера. Точные переборные методы построения циклических перестановок характеризуются обращением к уже полученному решению ЗН  для нахождения нового решения в матрице, где один из элементов  ic заменен на  ,  1, 2,...,i n . К ним относится алгоритм Кристофидеса, который строит по схеме Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы … «Штучний інтелект» 4’2011 407 7Л метода ветвей и границ маршрут коммивояжера в полном взвешенном графе, заданном симметричной матрицей стоимостей [1]. Алгоритм Кристофидеса начинает работу с решения ЗН, позволяющего оценить снизу стоимости всех возможных замкнутых маршрутов и переходит к выбору в полученном решении элемента, инициирующего ветвление. После замены значения выбранного элемента на  снова находится решение ЗН, по которому определяется нижняя граница стоимости маршрутов коммивояжера, не включающая этот элемент. Трудоемкости всех известных алгоритмов решения ЗН оценивается величинами, не меньшими  3O n [1], [2]. Поэтому неоднократное обращение к какому-либо из них, характерное для метода ветвей и границ, требует значительных временных затрат. Эти затраты могут быть уменьшены нахождением перестановки xy алгоритмом, временная сложность которого меньше, чем  3O n . В его основу положены подходы к решению задач о паросочетаниях [1], [3]. Сведение к задаче построения кратчайшего пути Матрице стоимостей ЗН С поставим во взаимно-однозначное соответствие двудольный граф  , ,X Y U , X Y n  , где вершина i X соединена с вершиной j Y ребром  ,i j U весом ijc   . Паросочетанием графа называется такое множество ребер, что никакие два из них не имеют общей вершины. Ребра графа, не входящие в паросочетание, называются свободными. Максимальное паросочетание – паросочетание с наибольшим числом ребер для данного графа. Вершина, принадлежащая ребру паросочетания, называется насыщенной, остальные вершины графа – свободными. Если i – насыщенная вершина ребра  ,i j , входящая в паросочетание, то вершина j определяется, как напарник i. Совершенное паросочетание – паросочетание, насыщающее все вершины графа. В двудольном графе  , ,X Y U , соответствующему матрице С, мощность совер- шенного паросочетания, если оно существует, равна n [2]. Решение ЗН  является совершенным паросочетанием двудольного графа  , ,X Y U , включающим ребра с минимальным суммарным весом. Элемент  ,x y матрицы С представлен в паросочетании  ребром  ,x y , которому присваивается в матрице xyC вес, равный  . Изменение значения 0xyc Z  на  влечет удаление из  ребра  ,x y . Таким образом, поставленная задача заключается в нахождении совершенного паросочетания xy с минимальным суммарным весом  xyC  относительно заданного паросочетания  ,x y  . Рассмотрим чередующийся путь  1 2, ,..., ,...,l mv v v v графа   , , ,X Y U x y , lv X Y  , 1,l m , т. е. путь, в котором ребра      1 2 3 4 2 1 2, , , ,..., , ,...k kv v v v v v свободны, а ребра  2 3,v v ,  4 5,v v ,…,  2 2 1,k kv v  ,… входят в паросочетание. Чередующийся путь  1,v 2 ,v …, mv называется увеличивающим, если вершины 1v и Левченко А.Ю., Морозов А.В., Панишев А.В. «Искусственный интеллект» 4’2011 408 7Л mv свободны [2]. Увеличивающий путь состоит из внешних и внутренних вершин, расположенных соответственно на нечетных и четных позициях. Поэтому в нем первое и последнее ребра свободны. Лемма 1. Решение xy существует, если в графе   , , ,X Y U x y , содержащем паросочетание  ,x y  , существует увеличивающий путь из вершины x X в вершину y Y . Доказательство. Заданное паросочетание  ,x y  состоит из 1n  ребер. Следовательно, в графе   , , ,X Y U x y только две вершины x и y свободны. Если в нем существует увеличивающий путь P между вершинами x и y относительно паросочетания  ,x y  , то существует паросочетание        , ,x y P x y P P          ,x y  мощностью n, а значит, и совершенное паросочетание xy . Лемма 2. Решение ЗН xy состоит в нахождении кратчайшего увеличи- вающего пути xyP из вершины x в вершину y относительно паросочетания  ,x y  . Доказательство. Пусть в графе  ( , , , )X Y U x y построен кратчайший увели- чивающий путь xyP из вершины х в вершину у относительно паросочетания  ,x y  . Определим совершенное паросочетание    ,xy xyx y P        ,xyP x y  и покажем, что оно имеет минимальный суммарный вес ребер  xyC  среди всех совершенных паросочетаний графа   , , ,X Y U x y . Рассмотрим xy вместе с совершенным паросочетанием  , построенным в графе  , ,X Y U . Очевидно, для  и xy справедливо неравенство    xyC C  . Числа  C  и  xyC  содержать общую часть       , i i xy C x y c       . Из неравенства    xyC C  для   ,xy xyx y P          ,xyP x y   следует неравенство        , ,xyC C x y C C x y    . Но    ,xyC C x y  – минимальная сумма весов ребер множества xyP    ,x y , поскольку xyP – кратчайший увеличивающий путь из вершины х в вершину у относительно паросочетания  ,x y  . Лемма 3. Если в графе  , ,X Y U содержится  совершенных паросочетаний , 2m   , включающих ребро  ,x y и имеющих минимальную стоимость   ,mC  1,m  , то длина кратчайшего увеличивающего пути в графе   , , ,X Y U x y не зависит от того, относительно какого из паросочетаний  ,m x y  построен этот путь. Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы … «Штучний інтелект» 4’2011 409 7Л Доказательство. Без потери общности предположим, что граф  , ,X Y U содержит два оптимальных совершенных паросочетания  1 1 1 ,   1 2 ,...,  1 n и       2 2 2 21 , 2 ,..., n    ,    1 2C C  ,   1 2,x y    . Так как 1 2  , то      0 1 2, ,x y x y       ,    1 0 2 0       , 1 0 2 0      ,    1 0 2 0C C      . По отношению к подмножеству ребер 1  0 паросочетания  1 ,x y  каждое ребро  2 2 0l    является свободным, и обратно, каждое ребро  1 1 0l    свободно относительно подмножества 2 0  паросочетания  2 ,x y  (рис. 1). Кратчайший увеличивающий путь 1xyP из вершины х в вершину у относительно паросочетания  1 ,x y  включает подмножество ребер 1 0  и подмножество свободных ребер 2 0  и имеет длину  1 02C   . Но такую же длину имеет кратчайший увеличивающий путь 2xyP относительно паросочетания  2 ,x y  , содержащий подмножество ребер 2 0  и подмножество свободных ребер  1 ,x y  . Следствие. Пусть m – совершенное паросочетание минимальной стоимости в графе  , ,X Y U , 1,m  , 2  . Стоимость совершенного паросочетания xy графа   , , ,X Y U x y не зависит от паросочетания  ,m x y  , относительно которого построен кратчайший увеличивающий путь из вершины х в вершину у в графе   , , ,X Y U x y . Доказательство. Достаточно положить 2  . В результате построения кратчайших увеличивающих путей 1xyP и 2xyP из вершины х в вершину у в графе   , , ,X Y U x y относительно паросочетаний  1 ,x y  и  2 ,x y  получим два совершенных паросочетания 1xy и 2xy , каждое из которых включает подмножество ребер     0 1 2, ,x y x y      . Определим их стоимости:     1 0 2xyC C C     0 ,      2 0 1 0xyC C C      , но    1 0 2 0C C      . Доказанные утверждения дают основание перейти к организации эффективного поиска xy с помощью нахождения тех увеличивающих путей из вершины х в вершину у относительно паросочетания  ,xy x y  , среди которых содержится кратчайший путь xyP . Поэтому для решения поставленной задачи применим адапти- рованный к ее условиям метод поиска в ширину, развивающий идеи алгоритма построения максимального паросочетания в двудольном графе [2]. Как и в алгоритме из [2], отнесем х к внешним вершинам искомого пути xyP . Тогда у – внутренняя вершина xyP . В двудольном графе   , , ,X Y U x y , содержащем паросочетание  ,x y  , все вершины i X и j Y за исключением х и у насыщены. Будем искать путь xyP построением всех возможных чередующихся путей из Левченко А.Ю., Морозов А.В., Панишев А.В. «Искусственный интеллект» 4’2011 410 7Л вершины х. В каждой паре ребер     , , ,k l l mi j j i чередующегося пути с началом в вершине х вершины ,k mi i X внешние, а вершина lj Y – внутренняя. Так как в нем вершина х свободна, то свободно ребро  , lx j , а ребро  ,l mj i содержится в паросочетании xy   ,x y . а) б) Рисунок 1 –     0 1 12 11 2, , ,v v v v  ; а)       1 0 5 4 7 6 9 8, , , , , ;v v v v v v   б)       2 0 5 8 7 4 9 6, , , , ,v v v v v v   Идея эффективного поиска пути xyP в ширину заключается в пошаговом построении орграфа, в котором вершина х имеет нулевую полустепень захода, а вершина у – нулевую полустепень исхода [3]. Каждая пара ребер     , , ,l l kx j j i представлена в орграфе дугой  , kx i весом xi xj i jk l k l c c c  . Поскольку ki является напарником lj , а любая вершина не может иметь более одного напарника, то такая замена однозначно определяет очередную внешнюю вершину чередующегося пути, игнорируя внутреннюю вершину. Вершины ki , инцидентные х, образуют первый ярус вершин орграфа. Тогда для каждой вершины ki , смежной со свободной вершиной у, можно построить увеличивающий путь  ,x ,lj ,ki y , определить соответствующее ему совершенное паросочетание         , , , ,l k k lx j i y x y i j    , вес которого равен xj i yl k c c    1 n xy i ji k l i c c c     . Среди всех полученных совершенных паросочетаний выберем паросочетание 1 xy с наименьшим весом  1 xyC  , принимаемым за рекордное текущее значение MIN верхней границы для  xyC  . В каждом построенном увеличивающем пути отметим дугу, входящую в у, и вершину ki , если она не смежна в   , , ,X Y U x y с внутренними вершинами или смежна только с вершиной у. Паросочетание 1 xy тогда является решением поставленной задачи, когда оно имеет вес, равный MIN, и все вершины ki , а следовательно, и дуги  ,ki y отличны (рис. 2). 2v 4v 6v 8v 10y v 12 2nv v 1v 3x v 5v 7v 9v 11 2 1nv v  2v 4v 6v 8v 10y v 12 2nv v 1v 3x v 5v 7v 9v 11 2 1nv v  Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы … «Штучний інтелект» 4’2011 411 7Л а) б) в) Рисунок 2 – а) Двудольный граф   , , ,X Y U x y и его паросочетание           1 2 2 3 3 4 4 5, , , , , , , , ;x y i j i j i j i j   б) увеличивающие пути из вершины 5x i в вершину 1y i относительно паросочетания  ,x y  ; в) двудольный граф   ,, ,UX Y x y и его совершенное паросочетание    1 2 2 1, , , ,xy i j i j     3 4 4 5, , ,i j i j В общем случае каждый ярус вершин орграфа, за исключением непосредственно предшествующего у, состоит как из отмеченных, так и неотмеченных вершин. Чтобы найти вес вершины второго яруса, для каждой неотмеченной вершины ki определим ее вес  k xjl C i c ,    , ,k lj j x y  . Не теряя общности, предположим, что в графе   , , ,X Y U x y вершина ki инцидентна двум свободным ребрам  ,k ri j и  ,k si j , вершина mi – одному свободному ребру  ,m si j , rj y , sj y , весом  m xjt C i c ,    , ,t mi j x y  , pi является напарником ri , а qi – напарником sj . Представим пары ребер     , , ,k r r pi j i i ,     , , ,k s s qi j j i ,     , , ,m s s qi j j i графа   , , ,X Y U x y соответствующими дугами  ,k pi i ,  ,k qi i ,  ,m qi i в строящемся орграфе и отнесем pi , qi ко второму уровню его вершин (рис. 3). Вычислим веса pi и qi :      , , ,p k i j p rk r C i C i c i j x y      ;         , , , ,q k i j m i j s qk s m s C i min C i c C i c i j x y       . Пусть qi – вершина второго яруса, из которой исходит дуга  ,qi y . Вершина ki в графе   , , ,X Y U x y принадлежит увеличивающему пути из х в у, длина которого равна  q i yq C i c . Предположим, что это путь  ,x ,lj ,ki ,sj ,qi y . По нему найдем со- вершенное паросочетание          , , , , , ,i l k s q k l q sq x j i j i y x y i j i j              с суммарным весом ребер     1 n i xj i j i y xy i j i jiq l k s q k l q s i C c c c c c c c         , x 1i 3i 2i y 2j 3j 4j 5j 1i 2i 3i 4i 5x i 1y j1y j 2j 3j 4j 5j 1i 2i 3i 4i 5x i Левченко А.Ю., Морозов А.В., Панишев А.В. «Искусственный интеллект» 4’2011 412 7Л отметим дугу  ,qi y и вершину qi , если она не смежна в   , , ,X Y U x y ни с какой другой внутренней вершиной. После выполнения таких действий для каждой вершины второго яруса, инцидентной у, определим совершенное паросочетание 2 xy с минимальным суммарным весом ребер  2 xyC  и, если  2 xyC MIN  , то положим MIN=  2 xyC  . Рисунок 3 – Увеличивающие пути из вершины x , содержащие дуги  , kx i ,  , mx i ,  4,ki i ,  ,k pi i ,  ,m qi i Процесс нахождения увеличивающих путей продолжается для неотмеченных вершин яруса, сформированного на очередном шаге, и завершается построением орграфа, в котором отмечены все дуги, входящие в вершину у. Искомым решением xy является полученное на шаге n , n  1, 2,…, совершенное паросочетание n xy с суммой весов ребер, равной MIN. Поиск xy в ширину упрощается в орграфе  ,V A , где  1 2, ,..., nV v v v , V X Y  , xv x , yv y , А – множество дуг, таких, что  ,k lv v A , если и только если в двудольном графе   , , ,Y UX x y : а)    , ,k li j U x y  и lj y ; б) вершина ki X смежна с напарником mj Y вершины li X , т.е. вершины , ,k m li j i образуют пару ребер  ,k mi j ,  ,m lj i некоторого увеличивающего пути. В орграфе  ,V A дуга имеет вес v v i jk l k l c c , если lj y , и v v i jk l k m c c иначе. Нетрудно видеть, что решение xy достигается построением во взвешенном орграфе  ,V A кратчайшего пути из вершины rv x в вершину sv y . Алгоритм решения задачи Изложенную схему эффективного поиска xy представим алгоритмом, выполня- ющим следующие действия. S0. Алгоритм нахождения решения ЗН xy для матрицы стоимостей xyC по известному решению ЗН  для матрицы стоимостей С; С – матрица порядка n , элемент которой ijc   при i j и 0ijc Z  или ijc   при i j , , 1,i j n , 0Z  – lj ki rj pi tj mi sj qi x Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы … «Штучний інтелект» 4’2011 413 7Л множество целых неотрицательных чисел; xyC отличается от С тем, что в С 0xyc Z  , а в xyC xyc   , x y ; xyc является одним из элементов  ic   , 1,i n , в решении         1 , 2 , ..., n   . S1. По матрице xyC и паросочетанию  ,x y  построить взвешенный орграф с множеством вершин  1 2, , ..., nV v v v и множеством дуг А следующим образом: для каждого элемента  ,k j матрицы xyC , kjc   , соответствующее ребро которого не входит в паросочетание  ,x y  , если j y , то  ,k lv v A , v v kjk l c c тогда и только тогда, когда элемент  ,l j представлен ребром  ,l j в паросочетании  ,x y  , иначе  ,k jv v A , v v kjk j c c . S2. В построенном орграфе  ,V A алгоритмом Дейкстры найти все кратчайшие пути из вершины xv . S3. Если в орграфе  ,V A не существует пути из вершины xv в вершину yv , то конец: ЗН для матрицы xyC не имеет решения. S4. Каждую дугу  ,k lv v кратчайшего пути из вершины kv в вершину yv заменить на ребро  ,k j весом kjc ; сформировать из полученных ребер подмножество xy  искомого паросочетания xy . S5. Найти все ребра паросочетания xy , выполнив такие действия: исключить из паросочетания  ,x y  каждое ребро  ,k r , если xy  содержит ребро  ,k s , r s ; объединить подмножество из оставшихся ребер множества  ,x y  с xy  ; вычислить  xyC  . Теорема. Представленный алгоритм корректно находит за время  2O n решение ЗН xy для матрицы стоимостей порядка n . Доказательство. Алгоритм останавливается на шаге S3, если в построенном орграфе  ,V A не существует пути из вершины xv в вершину yv . В этом случае по лемме 1 не существует увеличивающего пути из вершины х в вершину у в двудольном графе   , , ,X Y U x y , соответствующем орграфу  ,V A . Следовательно, граф  , ,X Y U  ,x y не содержит совершенного паросочетания, и поставленная задача не имеет решения. Действия по построению орграфа  ,V A , выполненные на шаге S4, требуют времени, оцениваемого величиной  2O n . Такую же временную сложность имеет шаг S2, на котором алгоритмом Дейкстры находится кратчайший путь из вершины xv в вершину yv . Шаги S4 и S5 имеют одинаковую оценку трудоемкости, равную  O n . Левченко А.Ю., Морозов А.В., Панишев А.В. «Искусственный интеллект» 4’2011 414 7Л Пример. Для матрицы 1 2 3 4 5 6 7 8 47 59 61 1 35 55 122 35 14 51 183 4 14 20 41 51 93 5 40 20 6 64 12 51 97 7 61 22 8 64 18 C                                                           перестановка  7, 6, 8, 5, 4, 2,1, 3  является решением ЗН;  C   17c 26c  + 38c  45c  54c  62c  71c  83c  61+12+18+20+20+12+61+18=222. Определим матрицу 45C , заменив в С значение 45 20c  на  . Выполним алгоритм нахождения решения 45 для матрицы 45C . Матрице 45C соответствует двудольный взвешенный граф   , , 4, 5X Y U  , в котором найдем кратчайший увеличивающий путь из вершины х=4 в вершину у=5 относительно паросочетания  4,5  (рис. 4). На рис. 5 изображен граф  ,V A , построенный на шаге S1 алгоритма нахождения 45 . В орграфе  ,V A из вершины 1 исходит дуга в вершину 8 , поскольку 13c   , а элемент (8, 3) матрицы 45C соответствует ребру  8, 3 весом 18, входящему в паросочетание  4, 5  . Так как у=5 и 15c   , то орграф  ,V A содержит дугу (1, 5) весом, равным 15 59c  . Рисунок 4 – Граф   , , 4, 5X Y U  ; утолщенными линиями обозначены ребра паросочетания  4, 5  3j 4j 5j 6j 7j 8j 1j 2j 1i 2i 3i 4i 5i 6i 7i 8i Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы … «Штучний інтелект» 4’2011 415 7Л В результате выполнения алгоритма Дейкстры определим кратчайший путь в каждую вершину графа  ,V A , достижимую из вершины 4: 1 2 3 4 5 6 7 8 51 41 92 0 96 128 78 14 Рисунок 5 – Взвешенный орграф  ,V A ; утолщенными линиями обозначены дуги кратчайшего пути из вершины 4 в вершину 5 Кратчайший путь из вершины 1 в вершину 5 в графе  ,V A состоит из дуг (4, 8), (8, 7), (7, 5) с весами соответственно 43 14c  , 81 64c  , 75 22c  (рис. 5). В графе   , , 4,5X Y U  ему отвечает кратчайший увеличивающий путь    45 4 3 3 8, , , ,P i j j i      8 1 1 7 7 5, , , , ,i j j i i j , в котором ребра  4 3,i j ,  8 1,i j ,  7 5,i j являются сво- бодными. Они образуют подмножество ребер      45 4, 3 , 8,1 , 7, 5   искомого паросочетания 45 . Чтобы определить все ребра в 45 , нужно в паросочетании  4, 5              1, 7 , 7,1 , 2, 6 , 6, 2 , 3, 8 , 8, 3 ,  5, 4 исключить ребра  8, 3 и  7,1 и объединить полученное подмножество с подмножеством ребер       4, 3 , 8,1 , 7, 5 . В результате искомым решением является паросочетание      45 1, 7 , 7, 5 , 5, 4 ,     4, 3 , 3, 8 ,    8,1 , 2, 6 ,  6, 2 стоимостью  45 233C   . Выводы Изложенные результаты получены в процессе обсуждения и поиска возможно- стей, уменьшающих трудоемкость известных алгоритмов типа ветвей и границ для нахождения кратчайших маршрутов коммивояжера. Как известно, эффективность ме- тода ветвей и границ зависит от способа получения оценок, ограничивающих снизу в выбранной схеме ветвления стоимость оптимального решения комбинаторной задачи. 4 3 2 1 8 7 6 5 3(14) 7(51) 5(41) 4(93) 6(51) 3(35) 3(47) 1(64) 1(64) 97 4(55) 2(35) 4(14) 3(51) 22 53 Левченко А.Ю., Морозов А.В., Панишев А.В. «Искусственный интеллект» 4’2011 416 7Л Для задач класса коммивояжера существует несколько способов нахождения оценок. В данной статье утверждается, что способ с использованием в качестве релаксации ЗН позволяет ускорить вычисление нижней оценки стоимости циклических маршрутов со значением, достаточно близким к стоимости оптимального маршрута. Литература 1. Кристофидес Н. Теория графов. Алгоритмический подход / Кристофидес Н. – М. : Мир, 1978. – 432 с. 2. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стай- глиц. – М. : Мир, 1975. – 510 с. 3. Панишев А.В. Модели и методы оптимизации в проблеме коммивояжера / А.В. Панишев, Д.Д. Пле- чистый. – Житомир : ЖГТУ, 2006.– 300 с. 4. Борханов И.Ф. Об оптимальном приведении матрицы стоимостей / И.Ф. Борханов, В.Р. Фазылов // Ученые записки Казанского государственного университета. Физико-математические науки. – 2006. – Т. 148, кн. 2. – С. 18-22. Literatura 1. Kristofides N. Teorija grafov. Algoritmicheskij podhod. M.: Mir. 1978 . 432 s. 2. Papadimitriu H. Kombinatornaja optimizacija. Algoritmy i slozhnost'. M.: Mir. 1975. 510 s. 3. Panishev A.V. Modeli i metody optimizacii v probleme kommivojazhera. Zhitomir: ZhGTU. 2006. 300 s. 4. Borhanov I.F. Uchenye zapiski Kazanskogo gosudarstvennogo universiteta. Fiziko-matematicheskie nauki. 2006. T 148. Kn 2. S 18-22 А.Ю. Левченко, А.В. Морозов, А.В. Панішев Швидкий алгоритм розв’язання задачі про призначення для знаходження нижньої межі вартості маршруту комівояжера Показано, що якщо в оптимальному розв’язку задачі про призначення (ЗП) та її матриці вартостей порядку n замінити значення якого-небудь елемента на нескінченно велике число, то оптимальний розв’язок ЗП для отриманої матриці знаходиться за час  2O n . A.Yu. Levchenko, A.V. Morozov, A.V. Panishev Algorithm for Fast Solution of the Problem of Allocation for Lower Limit Weight of Salesman Route It is shown that if to replace the value of any element by infinitely large number in the optimal solution for the problem of allocations and for its matrix of weights with size n, then the optimal solution of the problem of allocation for resulting matrix is found in a time  2O n . Статья поступила в редакцию 22.06.2011.

Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера

Репозитарії

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