Рекуррентный метод решения задачи о назначениях

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2014
Hauptverfasser:	Маций, О.Б., Морозов, А.В., Панишев, А.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2014
Schriftenreihe:	Искусственный интеллект
Schlagworte:	Интеллектуальные системы планирования, управления, моделирования и принятия решений
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/85260
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:	Рекуррентный метод решения задачи о назначениях / О.Б. Маций, А.В. Морозов, А.В. Панишев // Искусственный интеллект. — 2014. — № 2. — С. 107–118. — Бібліогр.: 3 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85260
record_format	dspace
spelling	irk-123456789-852602015-07-24T03:02:16Z Рекуррентный метод решения задачи о назначениях Маций, О.Б. Морозов, А.В. Панишев, А.В. Интеллектуальные системы планирования, управления, моделирования и принятия решений В статье предлагается новый метод решения задачи о назначениях, основанный на рекурсивном получении оптимального решения задачи. Он состоит в нахождении взвешенного паросочетания минимального суммарного веса в двудольном графе, используя понятия кратчайшего увеличивающего пути. Предложенный метод позволяет получать решения задачи о назначениях значительно быстрее, чем существующие методы. У статті пропонується новий метод розв'язання задачі про призначення, який ґрунтується на рекурсивному отриманні оптимального розв’язку задачі. Він полягає в знаходженні зваженого паросполучення мінімального сумарної ваги в дводольному графі, використовуючи поняття найкоротшого збільшуючого шляху. Запропонований метод дозволяє отримувати розв’язки задачі про призначення значно швидше, ніж існуючі методи. The article proposes new method for solving the assignment problem based on recursive obtaining an optimal solution. It consists in finding a minimum weighted matchings total weight in a bipartite graph, using concepts the shortest increasing path. The proposed method allows to obtain solutions of the assignment problem is significantly faster than existing methods. 2014 Article Рекуррентный метод решения задачи о назначениях / О.Б. Маций, А.В. Морозов, А.В. Панишев // Искусственный интеллект. — 2014. — № 2. — С. 107–118. — Бібліогр.: 3 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/85260 519.161 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	2014
topic_facet	Интеллектуальные системы планирования, управления, моделирования и принятия решений
url	http://dspace.nbuv.gov.ua/handle/123456789/85260
citation_txt	Рекуррентный метод решения задачи о назначениях / О.Б. Маций, А.В. Морозов, А.В. Панишев // Искусственный интеллект. — 2014. — № 2. — С. 107–118. — Бібліогр.: 3 назв. — рос.
series	Искусственный интеллект
work_keys_str_mv	AT macijob rekurrentnyjmetodrešeniâzadačionaznačeniâh AT morozovav rekurrentnyjmetodrešeniâzadačionaznačeniâh AT paniševav rekurrentnyjmetodrešeniâzadačionaznačeniâh
first_indexed	2025-07-06T12:27:18Z
last_indexed	2025-07-06T12:27:18Z
_version_	1836900522613800960
fulltext	ISSN 1561-5359 «Штучний інтелект» 2014 № 2 107 4С УДК 519.161 О.Б. Маций1, А.В. Морозов2, А.В. Панишев2 1Харьковский национальный автомобильно-дорожный университет Украина, 61002, г. Харьков, ул. Петровского, 25 2Житомирский государственный технологический университет Украина, 10005, г. Житомир, ул. Черняховского, 103 Рекуррентный метод решения задачи о назначениях O.B. Matsiy1, A.V. Morozov2, A.V. Panishev2 1Kharkiv National Automobile and Highway University, Ukraine Ukraine, 61002, c. Kharkiv, Petrosvkogo st., 25 2Zhytomyr State Technological University Ukraine, 10005, c. Zhytomyr, Chernyakhivskogo st., 103 Recurrent Method for Solving The Assignment Problem О.Б. Маций1, А.В. Морозов2, А.В. Панішев2 1Харківський національний автомобільно-дорожній університет Україна, 61002, м. Харків, вул. Петровського, 25 2Житомирський державний технологічний університет Україна, 10005, м. Житомир, вул. Черняхівського, 103 Рекурентний метод розв’язання задачі про призначення В статье предлагается новый метод решения задачи о назначениях, основанный на рекурсивном получении оптимального решения задачи. Он состоит в нахождении взвешенного паросочетания минимального суммарного веса в двудольном графе, используя понятия кратчайшего увеличивающего пути. Предложенный метод позволяет получать решения задачи о назначениях значительно быстрее, чем существующие методы. Ключевые слова: задача о назначениях, паросочетание, двудольный граф, увеличивающий путь. The article proposes new method for solving the assignment problem based on recursive obtaining an optimal solution. It consists in finding a minimum weighted matchings total weight in a bipartite graph, using concepts the shortest increasing path. The proposed method allows to obtain solutions of the assignment problem is significantly faster than existing methods. Key words: the assignment problem, matching, bipartite graph, increasing path. У статті пропонується новий метод розв'язання задачі про призначення, який ґрунтується на рекурсивному отриманні оптимального розв’язку задачі. Він полягає в знаходженні зваженого паросполучення мінімального сумарної ваги в дводольному графі, використовуючи поняття найкоротшого збільшуючого шляху. Запропоно- ваний метод дозволяє отримувати розв’язки задачі про призначення значно швидше, ніж існуючі методи. Ключові слова: задача про призначення, паросполучення, дводольний граф, збільшуючий шлях. Широко известные методы решения задачи о назначениях (ЗН), такие, как венгер- ский метод, метод Кана-Мункреса и метод потенциалов, построены с использованием разных подходов, применяемых в комбинаторной оптимизации, и характеризуются разной временной сложностью, не меньшей, чем  3 ,O n где n – порядок матрицы стоимостей [1]. В [2] изложен алгоритм решения одного из вариантов ЗН, стоимость которого пони- жена до  2 .O n В [2] показано, что он выполняет функции процедуры, встроенной в метод ветвей и границ для быстрого вычисления более точных нижних оценок стоимости Маций О.Б., Морозов А.В., Панишев А.В. «Искусственный интеллект» 2014 № 2 108 4М В замкнутых маршрутов в задаче коммивояжера. Алгоритм состоит в нахождении взвешен- ного паросочетания минимального суммарного веса в двудольном графе с 2n верши- нами, используя введенные в [2] понятия кратчайшего увеличивающего пути. В данной статье описан рекуррентный метод решения ЗН, развивающий результаты работ [2], [3] и технически упрощающий наиболее распространенный венгерский метод. Перестановочно-матричная постановка задачи. Опишем рассматриваемый здесь алгоритм решения ЗН, исходя из её формулировки в следующем виде. Для матрицы стоимостей (весов) ,ij n C c    где 0ijc R или ,ijc   0R – мно- жество неотрицательных действительных чисел, найти   [ ] 1 min . n i i C c      (1) Здесь  [1], [2], ..., [ ]n    – перестановка множества {1, 2, …, n} номеров столбцов матрицы C,  [1], [2], ..., [ ]n    – оптимальная перестановка стоимостью   [ ]1 ,n iiC c  [ ] ,ic   1, ,i n или решение ЗН. Перестановку  [1],  [2], ..., [ ] ,n  в которой [ ] ,ic   1, ,i n назовем допустимым решением ЗН. Заметим, что ЗН с матрицей стоимостей, содержащей элементы ,ijc   может не иметь решения. В этом случае необходимо установить, что множество допустимых решений задачи пусто. Будем искать , пошагово увеличивая на единицу число элементов k, 1, ,k n последовательности, образующей определенную часть до- пустимого решения ЗН. Рассмотрим свойства этой последовательности и способ её построения. Любая часть допустимого решения ЗН, включающая k элементов, однозначно определяет подматрицу s ti j k c   матрицы C, 1 2 ... ... ,s ki i i i     1 2 ...j j  ... ... .t kj j   Пусть последовательность  1 2[ ], [ ], ..., [ ], ...,k k k k si i i    [ ] ,k ki  1 2[ ] , , ..., , ..., ,k s t ki j j j j  1, 1,k n  а) является решением ЗН для подматрицы , s ti j k c   б) стоимость k не больше стоимости решения ЗН для любой подматрицы порядка k матрицы С. Если существует эффективная процедура преобразования последовательности k в последовательность 1, 0, 1,k k n    и задача (1) имеет решение, то на нахождение n  требуется n шагов. Матричный подход к построению оптимального назначения. Покажем, как строятся последовательности , 1, .k k n  Исходная последовательность  1 1 1[ ]i  определяется тривиально: в матрице С находится  min \| , ,lr ijc c i i j n   и, следо- вательно, 1 11, [ ] .i i r  Чтобы получить  2 2 1 2 2[ ], [ ] ,i i   определим  min \| , ,ms ijc c i l j r   lpc   min \| ,ljc j r  min \|vr irc c i l  (рис. 1). Рекуррентный метод решения задачи о назначениях «Штучний інтелект» 2014 № 2 109 4М lpc lrc msc vrc Рисунок 1 Нетрудно видеть, что если ,lr ms lp vrc c c c   то условия а) и б) выполняются для последовательности 2 , в которой 1 2 1 2 2 2, [ ] , , [ ] .i l i r i m i s     Ей соответ- ствует подматрица lrc msc . В противном случае этим условиям удовлетворяет последовательность 2 с элемен- тами 2 1 1 2 2 2[ ] , , [ ] , i p i l i r i v     и подматрицей lpc lrc vrc . Преобразуем последовательность 2 в последовательность 3 3 1[ ],i  3 2[ ],i 3 3[ ] .i Способ построения 3 не зависит от того, какие элементы образуют 2 . Для определенности предположим, что  2 2 2[ ] , [ ] .l r m s     Найдем wqc   min \| , ; , ijc i l m j s r   и 1 .lr ms wqMIN c c c   Заметим, что ,wq msc c если  2 2 2[ ] , [ ] .l p v r     Преобразование 2 в 3 является результатом решения следующей вспомога- тельной задачи. Для строк l, m и столбцов r, s, определяемых числами lrc и msc матрицы С, требуется найти тройку элементов с минимальной суммой их значений при условии, что любые два элемента из тройки должны находиться в трех разных строках, включающих l, m, и трех разных столбцах, включающих r, s. Если искомая тройка не содержит ,lrc но содержит ,msc то сумма значений её элементов ограничена снизу величиной 1 ,vr lp msS c c c   где  min \| , ,vr irc c i l m   min \| , .lp ljc c j r s  Пусть решение вспомогательной задачи является тройкой, в которую входит lrc и не входит .msc Тогда оно доставляет сумму 2 ,lr mp vsS c c c   где  min \| , ,mp mjc c j s r   min \| , .vs isc c i l m  Маций О.Б., Морозов А.В., Панишев А.В. «Искусственный интеллект» 2014 № 2 110 4М В Элементы решения вспомогательной задачи, не содержащем lrc и ,msc опреде- ляют величину  3 min , .lp mr ws mq ls vrS c c c c c c     Здесь (рис. 2)  min \| , ,ws isc c i l m   min \| , mq mjc c j s r  . Определим величину, равную  1 2 32 min , , .MIN S S S Ясно, что она соответст- вует искомой последовательности 3, если 2 1,MIN MIN иначе 3 3[ ] ,l r   3[ ] ,m s  3[ ] .w q  В общем случае последовательность  1 2[ ], [ ], ..., [ ], ..., [ ]k k k k s k ki i i i     со свойствами а) и б) преобразуется в последовательность 1 1 1[ ],k k i   1 2[ ], ...,k i  1 1 1[ ], ..., [ ]k r k ki i    с этими же свойствами следующим образом. p r s w wsc l lpc lrc m mrc msc q r s l lrc lsc m mqc msc v vrc Рисунок 2 В матрице C находится  1[ ] 1 2 1 2min \| , , ..., , ..., , [ ], [ ], ..., [ ], ..., [ ] , k ki ij s k k k k s k kc c i i i i i j i i i i         формируется последовательность  1 1 1, [ ]k k k ki    и вычисляется 1[ ] [ ] 1 1 . s k k k i i s MIN c c      Далее решается задача нахождения k + 1 элементов, которые в матрице C доставляют минимальную сумму своих значений и располагаются в разных строках и столбцах, включая все строки и столбцы с номерами, задаваемыми величинами 1 2[ ] [ ] [ ] [ ], ,..., ,..., . k k k s k ki i i ic c c c    Обозначим эту сумму MIN2. Найденные элементы образуют искомую последовательность 2 1 1,k k   если 2 1.MIN MIN Иначе 1 1 1.k k   Обоснование и описание рекурсивного алгоритма. Изложенная схема поиска оптимального назначения является основой алгоритма, в котором решение задачи (1) находится исключительно средствами теории паросочетаний для двудольных графов [1]. Матрице стоимостей ЗН C взаимно-однозначно соответствует двудольный граф (X, Y, U), где X Y n  и вершина i X соединена с вершиной j Y ребром  ,i j U весом .ijc   Рекуррентный метод решения задачи о назначениях «Штучний інтелект» 2014 № 2 111 4М Паросочетание графа образует такое множество ребер, что никакие два из них не имеют общей вершины. Ребра, не входящие в паросочетание, называются свободными. Максимальное паросочетание – паросочетание с наибольшим числом ребер. Вершина, принадлежащая ребру паросочетания, называется насыщенной, остальные вершины графа – свободными. Ребро (i, j), включенное в паросочетание, обозначим [i, j]. Вершина j ребра [i, j] определяется как напарник i. Совершенное паросочетание – это паросочетание, насыщающее все вершины графа. В двудольном графе (X, Y, U) мощность совершенного паросочетания, если оно существует, равна n. Решение ЗН  состоит в построении в двудольном взвешенном графе (X, Y, U) совершенного паросочетания с минимальным суммарным весом ребер [1]. Пусть в графе зафиксировано паросочетание M. Простой путь называется чере- дующимся относительно паросочетания M, если рёбра пути через одно присутст- вуют в M [1]. Чередующийся путь, который начинается и заканчивается ребрами, не принадлежащими паросочетанию M, называется увеличивающим относительно паросоче- тания M. Следовательно, если  1 2 2 3 1 1, , , , ..., , , , k k k ki j i j i j i j  – увеличивающий путь в двудольном графе (X, Y, U), то в нем свободны вершины 1 1, ki j  и k + 1 рёбер        1 2 2 3 1 1, , , , ..., , , , .k k k ki j i j i j i j  Остальные k ребер пути образуют паросочетание  2 2 3 3[ , ], [ , ], ..., [ , ] .k k ki j i j i j  Длиной пути называется число встречающихся в нем ребер. Предположим, что во взвешенном графе (X, Y, U), соответствующем матрице стоимостей ЗН C, не зафиксировано паросочетание. Тогда каждое ребро в (X, Y, U) является увеличивающим путем длины 1, а ребро с минимальным весом образует паросочетание или исходную последовательность 1. Пусть в графе (X, Y, U) построено паросочетание  1 1 2 2[ , ], [ , ], ...,k i j i j  [ , ], ..., [ , ]l l k ki j i j с минимальной суммой  kC  весов ребер среди всех паросочетаний мощности k. Преобразуем k в паросочетание 1 1 1 2 2[ , ], [ , ], ...,k i j i j      1 1[ , ], ..., [ , ], [ , ] ,l l k k k ki j i j i j       у которого величина  1kC   достигает минимума на множестве 1Пk всех паро- сочетаний мощности k + 1. Паросочетание k разбивает множества X, Y соответственно на подмножества насыщенных вершин    1 2 1 2, , ..., , ..., , , , ..., , ...,k l k k l kI i i i i J j j j j  и на подмножест- ве свободных вершин  1 2, , ..., , ..., ,k k k s nX I i i i i    1 2, , ...,k k kY J j j   , ..., .q nj j Найдем свободное ребро весом  min \| , , r p s qi j i j s k q kc c i X I j Y J     (2) и присоединив его к паросочетанию k получим паросочетание 1k k    [ , ]r ri j стоимостью  1 . r pk i jMIN C c  Если 1k  не является паросочетанием 1k  с мини- мальной суммой весов на множестве 1,k то  1 1 1 .k k k     Любое паросочета- ние в  1 1k k   содержит l ребер , 0, 1k l k   и 1k l  ребер увеличивающего пути относительно .k Маций О.Б., Морозов А.В., Панишев А.В. «Искусственный интеллект» 2014 № 2 112 4М В Лемма. Пусть  1 1 1 .k k k     Тогда    1 1 1 ,k k k k kP P        где 1kP  – кратчайший увеличивающий путь относительно паросочетания .k Доказательство. Построим кратчайший увеличивающий путь 1kP  относительно паросочетания ,k и, следовательно, паросочетание 2 1.k  Покажем, что 2 1 1.k k   Ясно, что    2 1 .k kC C   В величинах  kC  и  2 1kC   выделим общее слагаемое 2 1 0 [ ] [ ] . k s k s k k i i C c        Поэтому    2 0 1 0 .k kC C C C     Но 2 1 1,k k k kP      а  2 1 0kC C   сумма весов ребер множества 1 .k kP   Эта сумма минимальна, когда 1kP  – кратчайший увеличивающий путь относительно паросочетания .k Следовательно, 2 1k  – паро- сочетание с минимальной суммой весов ребер на множестве  1 1 ,k k   т.е. 2 1 1.k k   Пусть вершина  , 1, 2, ..., l kj J l k  является концом свободного ребра  ,r li j весом  min \| , r l s li j i j s kc c i X I   (3) вершина  , 1, 2, ..., f ki I f k  – началом свободного ребра  ,f pi j весом  min \| . f p f qi j i j q kc c j Y J   (4) Обозначим kX множество свободных вершин ,ri каждая из которых инцидентна ребру  ,r li j весом, определяемым из (3), .kX k Соответственно kY – множество свободных вершин ,pj инцидентных рёбрам  ,f pi j с весами, определяемыми из (4), .kY k Ясно, что кратчайший увеличивающий путь относительно паросочетания k начинается в вершине множества kX и заканчивается в вершине множества .kY Построим вспомогательный взвешенный орграф (V, A), обеспечивающий поиск кратчайшего увеличивающего пути 1kP  относительно паросочетания .k В орграфе (V, A) множество вершин  0 .k k kV i X I Y    Множество дуг А орграфа (V, A) представлено разбиением на подмножества 0 1 2, 3, , .A A A A Подмножество 0A содержит kX дуг  0 , ri i нулевого веса, .r ki X В под- множество 1A входит дуга  , , , ,r l r k l ki i i X i I  если, и только если, в паросочетании k вершина rj ребра  ,r li j – напарник вершины .li Дуге  , r li i присвоен вес  , . r l l lr l i j i jc i i c c  Дуга   2, , , ,d l d l ki i A i i I  тогда и только тогда, когда в паро- сочетании k вершина lj ребра  , , ,d l l ki j j J является напарником .li Дуга  ,d li i имеет вес  , . d l l ld l i j i jc i i c c  Подмножество 3A включает дугу  , ,f pi j , ,f k p ki I j Y  если вершины fi и pj соединены в графе (X, Y, U) ребром  , .f pi j Дуге  ,f pi j приписан вес  , . f pf p i jc i j c Рекуррентный метод решения задачи о назначениях «Штучний інтелект» 2014 № 2 113 4М На рис. 3 представлен граф (X, Y, U), для которого получено паросочетание , 4.k k  Рёбра паросочетания изображены жирными линиями. Вершины 5i и 6i образуют множество ,kX а вершины 5j и 6j – множество .kY Рёбра  5 1, ,i j  6 2, ,i j  6 3,i j имеют вес, полученный из (3), а веса рёбер      2 5 3 6 4 6, , , , ,i j i j i j определены из (4). Вспомогательный орграф  , ,V A построенный на графе (X, Y, U) и соответст- вующий паросочетанию 4 , изображен на рис. 4. Множество вершин V содержит вместе с вершиной 0i подмножества      1 5 6 2 1 2 3 4 3 7 8, , , , , , , .V i i V i i i i V i i   Множество дуг А образует подмножества       0 0 5 0 6 1 5 1, , , , A , ,A i i i i i i            6 2 6 3 2 1 3 1 4 3 1, , , , , , , , , ,i i i i A i i i i i i       3 2 7 3 8 4 8A , , , , , .i i i i i i Из способа построения орграфа (V, A) следует, что множество путей, достижи- мых из вершины 0i во все вершины 3,pi V совпадает с множеством увеличивающих путей относительно паросочетания ,k соединяющих в графе (X, Y, U) кардую вершину ri X I  с каждой вершиной .pi Y J  Кроме того, любому пути орграфа (V, A), начинающемуся в вершине ri X I  в вершину pj Y J  относительно паросочетания .k Если в графе (V, A) построен кратчайший путь из вершины 0i в вершину 3,pi V то он содержит одну из дуг   1, r li i A и одну из дуг   3, .f pi i A Пусть 3ti V конечная вершина пути, кратчайшего среди всех путей из 0i в остальные вершины множества 3.V Очевидно, такой путь в графе (X, Y, U) определит кратчайший увеличивающий путь 1kP  относительно .k Рисунок 3 Рисунок 4 Маций О.Б., Морозов А.В., Панишев А.В. «Искусственный интеллект» 2014 № 2 114 4М В Таким образом, поиск в графе (X, Y, U) кратчайшего увеличивающего пути 1kP  относительно паросочетания k выполняется следующим образом. 1. При насыщенных вершинах  , , , 1, 2, ..., , ,l fj J i I l f k I J k     находят- ся свободные рёбра  ,r li j и    , , , 1, 2, ..., ,f pi j r p k k n   с весами, определяе- мыми соответственно из (3) и (4). 2. Для множества всех свободных рёбер  ,r li j и  ,f pi j и всех рёбер паро- сочетания k строится взвешенный орграф (V, A), предлагаемым выше способом. 3. В орграфе (V, A) ищется путь  0 , , , , ..., , , ,v a b e d ti i i i i i i кратчайший на мно- жестве путей из 0i в каждую вершину ,pi представленную в графе (X, Y, U) свободной вершиной pj ребра  , .f pi j Если существует такой путь, то существует кратчайший увеличивающий путь  1 , , , , , ..., , , , ,k v a a b b e d d tP i j i j i i i i i  ,vi X I  , , ..., ,a b dj j j J , , ..., ,a b ei i i ,di I ,tj Y J  относительно паросочетания ,k и следовательно, паросочетение 2 1.k  Стоимость  2 1 ... . v a a b e d d tk i j i j i j i jС c c c c       В противном случае не существует пути 1kP  и паросочетания 2 1.k  Очевидно, для нахождения в графе (X, Y, U) паросочетания 1,k  стоимость которого минимальна на множестве 1k  паросочетаний мощности k +1, достаточно а) определить паросочетание 1 [ , ]k k r ki j    и суммарный вес её ребер  1 , r pk i j kMIN C c   – паросочетание минимальной стоимости на множестве всех паросочетаний k мощности k, r pi jc – вес ребра , ,r pi j   определяемый из (2); б) найти паросочетание 2 1k  и  2 12 ,kMIN C   построив кратчайший увели- чивающий путь 1kP  относительно паросочетания ;k в) положить 1 1 1,k k   если 1 2,MIN MIN и 2 1 1k k   в противном случае. Следующий алгоритм выполняет поиск решения ЗН, рекурсивно определяя в двудольном графе с 2n вершинами паросочетания ,k содержащие k рёбер мини- мального суммарного веса. Предлагаемый алгоритм состоит из такого же числа этапов и имеет такую же временную сложность, что и наилучший из известных методов оптимального на- значения – венгерский метод [1]. S0. Алгоритм решения ЗН для матрицы стоимостей , 2,ij n С с n    элементы которой принимают значения из множества неотрицательных действительных чисел или равны ; решение представлено совершенным паросочетанием n  с минимальной суммой  C  весов рёбер  ,i j в двудольном графе (X, Y, U), , , ,X Y n i X j Y    где 0 ,ijc R если  , ,i j U иначе ;ijc   1;k  найти  min \| , 1, , k ki j ijc c i j n     , ,k k k kI i J j      , , . k kk k k k i ji j C c   Рекуррентный метод решения задачи о назначениях «Штучний інтелект» 2014 № 2 115 4М S1. 1;k k  если ,k n то конец: построено решение ЗН . S2. Найти  1 1min \| , ; k ki j ij k kc c i X I j Y J      если , k ki jc   то положить 1 ,MIN   перейти к шагу S6, иначе    1 1 1 , , 1 .k k k k ki j MIN C     S3. Найти все ri такие, что для   1, 1, 2, ..., 1 , min \| r l ll k i j ijj J l k c c i     1 ,kX I    и сформировать из них список ;kX если ,kX   то положить 2MIN   и перейти к шагу S6. S4. Найти все pj такие, что для  1, 1, 2, ..., 1 ,l ki I l k   min \| l p li j i jc c j  1 ,kY J    и сформировать из них список ,kY если ,kY  то положить 2MIN   и перейти к шагу S6. S5. Построить взвешенный орграф (V, A),  0 1k k kV i X I Y    и выполнить в нем поиск пути, кратчайшего на множестве всех путей в вершины ,kY достигаемые из 0;i если построен такой путь, то в графе (X, Y, U) найти соответствующий ему кратчайший путь    2 1 1 ,k k k k kP P        22 ,kMIN C  иначе положить 2 , 2 .k MIN     S6. Если 1 2 ,MIN MIN   то конец: не существует для матрицы ij n c   решения ЗН; Если 1MIN   или 2 ,MIN   то если 1 2,MIN MIN то 1 ,k k   1 ,k k kI I i   1 ,k k kJ J j  иначе 2 ,k k     2\| 1, ; , ,k l l l kI i l k i j    kJ    2\| 1, , , ;l i l kj l k i j    перейти к шагу S1. Теорема. Решение ЗН  корректно находится за время  3O n построением в двудольном графе с 2n вершинами последовательностей паросочетаний ,k 1, ,k n где k – паросочетание, содержащее k рёбер минимального веса, .k  Доказательство. Пусть построено паросочетание 1, 2, .k k n   Алгоритм останав- ливается, когда 1) не находится ребра, объединение которого с 1k  давало бы 1 ;k 2) во вспомогательном графе нет пути из любой вершины в любую вершину, следовательно, не существует увеличивающего пути относительно текущего паросочетания 1.k  Чтобы оценить трудоёмкость решения ЗН, заметим, что оно строится в результате выполнения n этапов, каждый из которых увеличивает паросочетание на одно ребро. На первом этапе находится 1 за время, оцениваемое в худшем случае величи- ной  2 .O n На каждом следующем этапе строятся паросочетания 1 k и 2 ,k 2, .k n Время построения 1 k оценивается величиной   21 .O n k  Нахождение 2 k требует  2 1n k  операций на поиск вершин множеств, k + 1 операций на построение Маций О.Б., Морозов А.В., Панишев А.В. «Искусственный интеллект» 2014 № 2 116 4М В вспомогательного орграфа,  2O k действий на построение в нем алгоритмом Дейкстры кратчайшего пути и  O k операций с множествами для определения 2.k Поэтому время каждого k-го этапа ограничено величиной  2 .O n � Пример. Исходная матрица ij n c   имеет вид: 1 2 3 4 5 6 7 1   2 8 9 0  2 15  3 0 24 0 24 3 5   5 0 2  4  10 2  23  0 5  0 0     6 0 15 10 3 17   7 14 0 24 2 2 15  S0.  1, 2, 3, 4, 5, 6, 7 ,X Y  k = 1,  1 1 16min \| , 1, 7 c 0,i j ijс c i j     1 1 ,I   1 6 ,J  1 1 ,X Y     1 1,6 ,   1С   16 0с  . S1. k = 2. S2.         2 2 1 24 2 1min \| 1, 6 0, 2, 4 1,6 , 2, 4 ,i j ijc c i j c          1MIN   1 2 16 24 0 0 0.C c c      S3. Для 16 J    6 6 26 2min \| 1 0, 2 . ri ic c i c X     S4. Для 11 I    1 1 13 2min \| 6 2, 3 . pj jc c j c Y     S5. Взвешенный граф (V, A) представляет собой путь  0 , 2, 1, 3 ,i где 0 2 0,iс  21 26 16 16 130, 0, 2.c c c c c     Этому пути соответствует кратчайший увеличиваю- щий путь  2 2, 6, 1, 3Р  относительно паросочетания   1 1, 6 .  Путь 2Р образуют рёбра      2,6 , 1,6 , 1,3 . Поэтому     2 2 2,6 , 1,3 , 2MIN   26 13 0 2 2.c c    S6. Так как MIN1 < MIN2,         1 2 2 2 21, 6 , 2, 4 , 1, 2 , 6, 4 .I J     S1. k = 3. S2.  3 3 35min \| 1, 2; 6, 4 0,i j ijc c i j c          1 3 2 4, 7 1, 6 , 2, 4 ,     3, 5 ,  1 31 0MIN C   . S3. Так как    2 21, 2 , 6, 4 ,I J  то  6 6 36 4min \| 1, 2 2, r ri i iс c i c c      4 74min \| 1, 2 2,ic i c    и  3 3, 7 .Х  S4.      1 1 13 2 2 23 3min \| 6, 4 2, min \| 6, 4 3, 3 . p pj j j jc c j c c c j c Y         S5. Подграфу двудольного графа (X, Y, U), определенному на множестве вершин 3 2 2 3X I J Y   (рис. 5) соответствует вспомогательный граф (рис. 6) с весами дуг: 0 03 7 0,i ic c  31 36 16 2 0 2,c c c     12 14 24 8 0 8,c c c     21 26 16c c c   0 0 0,   72 74 24 0 2 2,c c c     23 3,c  33 .Y Рекуррентный метод решения задачи о назначениях «Штучний інтелект» 2014 № 2 117 4М Рисунок 5 Рисунок 6 Кратчайший путь  7, 2, 3 , 3 ,Y связывающий в орграфе (V, A) вершины из 3Х с вершинами из 3,Y состоит из рёбер       37, 4 , 2, 4 , 2, 3 , 3 ,Y кратчайшего увеличивающего пути 3P относительно паросочетания     2 1, 6 , 2, 4 .  Выполнив восемь итераций алгоритма, получим решение задачи:               7 1, 6 , 2, 4 , 3, 5 , 4, 7 , 5, 3 , 6, 1 , 7, 2 .  Рисунок 7 Для исследования времени решения задач разных размерностей различными методами проведен вычислительный эксперимент. Исследовалась зависимость времени решения ЗН от размерности входных данных. При помощи языка программирования Microsoft Visual C# были реализованы три метода решения ЗН: метод потенциалов, венгерский алгоритм и рекуррентный метод. На размерностях, больших 30, наи- лучшие результаты показал рекуррентный метод, а наихудшие – метод потенциалов. Список литературы 1. Пападимитриу Х. Комбинаторная оптимизация: Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц. – М. : Мир, 1985. – 510 с. 2. Панишев А.В. Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Искусственный интеллект. Институт проблем искусственного интеллекта. – 2011. – С. 406-416. 3. Левченко А.Ю. Механизм ускорения вычислений в методе Литтла для решения задач класса коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Искусственный интеллект. – 2012. – С. 95-110. Маций О.Б., Морозов А.В., Панишев А.В. «Искусственный интеллект» 2014 № 2 118 4М В References 1. Papadimitriou C. Combinatorial Optimization: Algorithms and Complexity / C. Papadimitriou, K. Steiglitz. – M.: Mir, 1985. – 510 p. 2. Panishev А.V. Fast algorithm for solving the assignment problem for finding lower bounds on the cost of the route of a Salesman / A.Y. Levchenko, A.V. Morozov, A.V. Panishev // Artificial intelligence The Institute of Artificial Intelligence.– Donetsk, 2011 .– P. 406-416. 3. Levchenko A.Y. Acceleration mechanism in the Little’s method for solving problems in the class of a Salesman / A.Y. Levchenko, A.V. Morozov, A.V. Morozov // Artificial intelligence The Institute of Artificial Intelligence.– Donetsk, 2012. – P. 95-110. RESUME O.B. Matsiy, A.V. Morozov, A.V. Panishev Recurrent Method for Solving the Assignment Problem Well-known methods for solving the assignment problem, such as the Hungarian method, Huhn-Munkres method, method of potentials are constructed using different approaches in combinatorial optimization, and are characterized by different time complexity, no less than O(n3). The paper proposes a new method for solving the assignment problem based on recursive obtaining an optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of a matrix approach to an optimal solution. The algorithm consists in finding a minimum total weight matching in the bipartite graph with 2n vertices. Computational scheme of the recurrence method for solving the assignment problem is presented in a form adapted for implementation on a computer. The layout is the purpose of finding the optimal basis for the algorithm in which the solution is found solely by means of the theory of matchings for bipartite graphs presented in the rearrangement matrix form. The developed method, in comparison with others, gives the opportunity to save computational resources, making a gain on large dimension of the input data. Статья поступила в редакцию 11.03.2014.

Рекуррентный метод решения задачи о назначениях

Institution

Ähnliche Einträge