Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Угорський алгоритм



План:


Введення

Угорський алгоритм - алгоритм оптимізації, вирішальний завдання про призначеннях за поліноміальний час (див. дослідження операцій). Він був розроблений і опублікований Харолд Куном в 1955. Автор дав йому ім'я "угорський метод" у зв'язку з тим, що алгоритм в значній мірі заснований на більш ранніх роботах двох угорських математиків ( Кеніга та Егерварі).

Джеймс Манкрес в 1957 році помітив, що алгоритм є (строго) поліноміальних. З цього часу алгоритм відомий також як алгоритм Куна - Манкреса або алгоритм Манкреса рішення задачі про призначення. Часова складність оригінального алгоритму була O (n ^ 4) , Однак Едмондс і Карп (а також Томідзава незалежно від них) показали, що його можна модифікувати так, щоб досягти часу виконання O (n ^ 3) . Форд і Фалкерсоном поширили метод на загальні транспортні задачі. У 2006 році було виявлено, що Якобі знайшов рішення задачі про призначення в XIX столітті і опублікував його в 1890 році на латині [1].


1. Пояснення на прикладі

Припустимо, є три працівника: Іван, Петро та Андрій. Потрібно розподілити між ними виконання трьох видів робіт (які ми назвемо A, B, C), кожен працівник повинен виконувати тільки один різновид робіт. Як це зробити так, щоб витратити найменшу суму грошей на оплату праці робітників? Спочатку необхідно побудувати матрицю вартостей робіт.

A B C
Іван 1000 руб. 2000 руб. 3000 руб.
Петро 3000 руб. 3000 руб. 3000 руб.
Андрій 3000 руб. 3000 руб. 2000 руб.

Угорський алгоритм, застосований до наведеної вище таблиці дасть нам необхідний розподіл: Іван виконує роботу A, Петро - роботу B, Андрій - роботу С.


2. Постановка завдання

Дана ненегативна матриця розміру n n, де елемент в i-му рядку і j-му стовпці відповідає вартості виконання j-ого виду робіт i-м працівником. Потрібно знайти таку відповідність робіт працівникам, щоб витрати на оплату праці були найменшими. Якщо мета полягає в знаходженні призначення з найбільшою вартістю, то рішення зводиться до вирішення тільки що сформульованої задачі шляхом заміни кожної вартості C на різницю між максимальною вартістю і C. [2]


3. Основні ідеї

Алгоритм заснований на двох ідеях:

  • якщо з усіх елементів якоїсь рядка або стовпця відняти одне й те ж число y , Загальна вартість зменшиться на y , А оптимальне рішення не зміниться;
  • якщо є рішення нульовою вартістю, воно оптимально.

Алгоритм шукає значення, які треба відняти з усіх елементів кожного рядка і кожного стовпця (різні для різних рядків і стовпців), такі що всі елементи матриці залишаться ненегативними, але з'явиться нульове рішення.


4. Визначення

Алгоритм простіше описати, якщо сформулювати завдання, використовуючи двочастковий граф. Дан повний двочастковий граф G = (S, T; E) c n вершинами, що відповідають працівникам (S), і n вершинами, що відповідають видам робіт (T); вартість кожного ребра c (i, j) неотрицательна. Потрібно знайти досконале, або повне паросполучення c найменшою вартістю.

Будемо називати функцію y: (S \ cup T) \ mapsto \ mathbb {R} потенціалом, якщо y (i) + y (j) \ leq c (i, j) для кожних i \ in S, j \ in T . Значення потенціалу y одно \ Sum_ {v \ in S \ cup T} y (v) . Неважко помітити, що вартість будь-якого досконалого паросполучення не менше, ніж значення будь-якого потенціалу. Угорський метод знаходить повне паросполучення і потенціал з однаковою вартістю / значенням, що доводить оптимальність обох величин. Фактично він знаходить досконале паросполучення жорстких ребер: ребро ij називається жорстким для потенціалу y, якщо y (i) + y (j) = c (i, j) . Підграф жорстких ребер будемо позначати як G_y . Вартість повного паросполучення в G_y (Якщо воно існує) дорівнює значенню y.


5. Алгоритм в термінах дводольних графів

Алгоритм зберігає в пам'яті потенціал y \ і орієнтацію (завдання напрямки) кожного жорсткого ребра, що володіє тим властивістю, що ребра, спрямовані від T \ до S \ утворюють паросполучення M \ . Орієнтований граф, що складається з жорстких ребер із заданою орієнтацією, ми позначаємо \ Overrightarrow {G_y} . Таким чином, в будь-який момент є три типи ребер:

  • нежорсткі (і не належать M \ )
  • жорсткі, але не належать M \
  • жорсткі і належать M \

Спочатку y \ скрізь дорівнює 0, і всі ребра спрямовані від S \ до T \ (Таким чином, M \ пусто). На кожному кроці або модифікується y \ так, що увелічівется безліч вершин Z \ , Визначене в наступному абзаці, або змінюється орієнтація, щоб отримати паросполучення з великою кількістю ребер; завжди залишається вірним, що всі ребра з M \ є жорсткими. Процес закінчується, якщо M \ - Досконале паросполучення.

Нехай на кожному кроці R_S \ subseteq S і R_T \ subseteq T складають безліч вершин, не інцидентних ребер з M \ (Тобто R_S \ - Безліч вершин з S , В які не входить жодне ребро, а R_T \ - Безліч вершин з T , З яких не виходить ні одне ребро). Позначимо через Z \ безліч вершин, досяжних з R_S \ в \ Overrightarrow {G_y} (Воно може бути знайдено пошуком в ширину).

Якщо R_T \ cap Z не є порожнім, це означає, що є хоча б один шлях в \ Overrightarrow {G_y} з R_S \ в R_T \ . Вибираємо будь-який з таких шляхів, і змінюємо орієнтацію всіх його ребер на зворотну. Розмір паросполучення збільшиться на 1.

Для доказу відзначимо два очевидні факти:

  • На обраному шляху ребра з S \ в T \ чергуються з ребрами з T \ в S \ . Це випливає з дводольними графа.
  • Перша вершина шляху належить S \ , А остання - T \ . Отже, перше і останнє його ребра спрямовані з S \ в T \ .
За визначенням \ Overrightarrow {G_y} , Звідси випливає, що на вибраному шляху ребра, належать і не належать M \ чергуються, причому перше і останнє ребра не належать M \ , Тобто шлях є підвищувальним, звідки і випливає доказуване твердження.

Якщо R_T \ cap Z порожньо, покладемо \ Delta: = \ min \ {c (i, j)-y (i)-y (j): i \ in Z \ cap S, j \ in T \ setminus Z \} . \ Delta позитивна, тому що немає жорстких ребер між Z \ cap S і T \ setminus Z .

У самому справі, нехай таке ребро (i, j) є. Оскільки i \ in Z , Але j \ notin Z , Вершина i \ досяжна з R_S \ в \ Overrightarrow {G_y} , А вершина j \ недосяжна. Отже, \ Overrightarrow {G_y} не може містити ребра (i, j). Отже, (I, j) \ in M , Звідки i \ notin R_S . Оскільки i \ досяжна з R_S \ в \ Overrightarrow {G_y} , Існує шлях у i \ з якоїсь вершини, що належить R_S \ . Розглянемо останнє ребро цього шляху. Позначимо його (k, i). Оскільки k \ досяжна з R_S \ в \ Overrightarrow {G_y} , А j \ недосяжна, k \ neq j . Оскільки (K, i) \ in \ overrightarrow {G_y} , (I, k) \ in M . Отже, i \ інцидентна відразу двом ребрам з M \ : (I, j) \ і (I, k) \ , Що неможливо, так як M \ - Паросполучення. Суперечність.

Збільшимо y \ на \ Delta на вершинах з Z \ cap S і зменшимо y \ на \ Delta на вершинах, що входять до Z \ cap T . Новий y \ залишається потенціалом.

У самому справі, для будь-якого ребра (i, j), i \ in S , j \ in T :

  • якщо i \ notin Z , j \ notin Z , То c ​​(i, j)-y (i)-y (j) не змінюється, тому що не змінюються ні y (i), ні y (j)
  • якщо i \ in Z , j \ in Z , То c ​​(i, j)-y (i)-y (j) не змінюється, тому що y (i) збільшується на \ Delta , А y (j) на стільки ж зменшується
  • якщо i \ notin Z , j \ in Z , Різниця c (i, j)-y (i)-y (j) збільшується на \ Delta , Отже, залишається неотрицательной
  • якщо i \ in Z , j \ notin Z , Різниця c (i, j)-y (i)-y (j) зменшується на \ Delta , Але все одно залишається неотрицательной, тому що \ Delta - Найменша з таких різниць.

Граф \ Overrightarrow {G_y} змінюється, але, незважаючи на це, містить M \ .

У самому справі, щоб виключити з \ Overrightarrow {G_y} якесь ребро (i, j), i \ in S , j \ in T , Треба зробити його нежорстких, тобто підвищити різниця c (i, j)-y (i)-y (j). Як ми бачили, різниця підвищується тільки якщо i \ notin Z , j \ in Z , Іншими словами, i недосяжна з R_S , А j досяжна. Але в такому випадку ребро (j, i) не може належати \ Overrightarrow {G_y} , Отже, ребро не належить M .

Орієнтуємо нові ребра від S \ до T \ . За визначенням \ Delta , Безліч Z \ вершин, досяжних з R_S , Збільшиться (при цьому число жорстких ребер зовсім не обов'язково зросте).

Для доказу цього утвержеденія спочатку доведемо, що ні одна вершина не пропаде з Z. Нехай V \ in Z . Тоді існує шлях з якоїсь вершини, що належить R_S , В V. Всі вершини на цьому шляху досяжні з R_S , Тобто належать Z. Кожне ребро на цьому шляху інцидентне двом вершинам з Z. Як ми бачили вище, для таких ребер різниця c (i, j)-y (i)-y (j) не змінюється. Значить, всі ребра шляху залишаться жорсткими, і V як і раніше буде досяжна з R_S . Тепер доведемо, що хоча б одна вершина додасться до Z. Розглянемо ребро, на якому досягається мінімум \ Min \ {c (i, j)-y (i)-y (j): i \ in Z \ cap S, j \ in T \ setminus Z \} . Для цього ребра, різниця c (i, j)-y (i)-y (j) обнулиться, отже, воно стане жорстким і буде спрямовано з S в T, тобто від i до j. Оскільки i \ in Z , J також стане досяжним з R_S , Тобто додасться до Z.

Повторюємо ці кроки до тих пір, поки M \ не стане досконалим паросполучення; в цьому випадку воно дає призначення з найменшою вартістю. Час виконання цієї версії алгоритму одно O (n ^ 4) : M \ доповнюється n \ раз, а в стадії, коли M \ не змінюється, може бути не більше n \ змін потенціалу (так як Z \ збільшується кожного разу). Час, необхідний на зміну потенціалу, одно O (n ^ 2) .


6. Матрична інтерпретація

Для n працівників і робіт, дана матриця n n, що задає вартість виконання кожної роботи кожним працівником. Знайти мінімальну вартість виконання робіт, таку що кожен працівник виконує рівно одну роботу, а кожну роботу виконує рівно один працівник.

Надалі ми під призначенням розуміємо відповідність між працівниками і роботами, що має нульову вартість, після того як ми зробили трансформації, що впливають лише на загальну вартість робіт.

Перш за все запишемо задачу в матричній формі:

\ Begin {bmatrix} a1 & a2 & a3 & a4 \ \ b1 & b2 & b3 & b4 \ \ c1 & c2 & c3 & c4 \ \ d1 & d2 & d3 & d4 \ end {bmatrix}

де a, b, c, d - працівники, які мають виконати роботи 1, 2, 3, 4. Коефіцієнти a1, a2, a3, a4 позначають вартість виконання працівником "a" робіт 1, 2, 3, 4 відповідно. Аналогічний сенс мають інші символи. Матриця квадратна, тому кожен працівник може виконати тільки одну роботу.

Крок 1

Зменшуємо елементи порядково. Знаходимо найменший з елементів першого рядка (а1, а2, а3, а4), і віднімаємо його з усіх елементів першого рядка. При цьому хоча б один з елементів першого рядка обнулиться. Те ж саме виконуємо і для всіх інших рядків. Тепер у кожному рядку матриці є хоча б один нуль. Іноді нулів вже достатньо, щоб знайти призначення. Приклад показаний у таблиці. Червоні нулі позначають призначені роботи.

0 a2 ' 0 a4 '
b1 ' b2 ' b3 ' 0
0 c2 ' c3 ' c4 '
d1 ' 0 d3 ' d4 '

При великій кількості нулів для пошуку призначення (нульовою вартістю) можна використовувати алгоритм знаходження максимального паросполучення дводольних графів, наприклад алгоритм Хопкрофта-Карпа. Крім того, якщо хоча б в одному стовпці немає нульових елементів, то призначення неможливо.

Крок 2

Часто на першому кроці немає призначення, як, наприклад, в наступному випадку:

0 a2 ' a3 ' a4 '
b1 ' b2 ' b3 ' 0
0 c2 ' c3 ' c4 '
d1 ' 0 d3 ' d4 '

Задача 1 може бути ефективно (за нульову вартість) виконана як працівником a, так і працівником c, зате завдання 3 не може бути ефективно виконана ніким.

У таких випадках ми повторюємо крок 1 для стовпців і знову перевіряємо, чи можливе призначення.

Крок 3

У багатьох випадках ми досягнемо бажаного результату вже після кроку 2. Але іноді це не так, наприклад:

0 a2 ' a3 ' a4 '
b1 ' b2 ' b3 ' 0
0 c2 ' c3 ' c4 '
d1 ' 0 0 d4 '

Якщо працівник d виконує роботу 2, нікому виконувати роботу 3, і навпаки.

У таких випадках ми виконуємо процедуру, описану нижче.

Спочатку, використовуючи будь-який алгоритм пошуку максимального паросполучення в дводольному графі, призначаємо якомога більше робіт тим працівникам, які можуть їх виконати за нульову вартість. Приклад показаний в таблиці, призначені роботи виділені червоним.

0 a2 ' a3 ' a4 '
b1 ' b2 ' b3 ' 0
0 c2 ' c3 ' c4 '
d1 ' 0 0 d4 '

Відзначимо всі рядки без призначень (рядок 1). Відзначимо всі стовпці з нулями в цих рядках (стовпець 1). Відзначимо всі рядки з нулями в цих стовпцях (рядок 3). Продовжуємо, поки нові рядки і стовпці не перестали відзначатися.

0 a2 ' a3 ' a4 '
b1 ' b2 ' b3 ' 0
0 c2 ' c3 ' c4 '
d1 ' 0 0 d4 '

Тепер проводимо лінії через усі зазначені стовпці і невідмічені рядки.

0 a2 ' a3 ' a4 '
b1 ' b2 ' b3 ' 0
0 c2 ' c3 ' c4 '
d1 ' 0 0 d4 '

Всі ці дії переслідували лише одну мету: провести найменшу кількість ліній (вертикалей і горизонталей), щоб покрити всі червоні нулі. Можна було скористатися будь-яким іншим методом замість описаного.

Крок 4

З непокритих лініями елементів матриці (в даному випадку це a2 ', a3', a4 ', c2', c3 ', c4') знайти найменший. Відняти його з усіх не зазначених рядків і додати до всіх пересіченнях зазначених рядків і стовпців. Так, наприклад, якщо найменший елемент з перерахованих дорівнює а2 ', ми отримаємо

0 0 a3'-а2 ' a4'-a2 '
b1 '+ a2' b2 ' b3 ' 0
0 c2'-а2 ' c3'-а2 ' c4'-а2 '
d1 '+ a2' 0 0 d4 '


Повторювати процедуру (кроки 1-4) до тих пір, поки призначення не стане можливим.


7. Бібліографія

  • RE Burkard, M. Dell'Amico, S. Martello: Assignment Problems. SIAM, Philadelphia (PA.) 2009. ISBN 978-0-89871-663-4
  • Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2 :83-97, 1955. Kuhn's original publication.
  • Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253-258, 1956.
  • J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5 (1) :32-38, 1957 March.
  • M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995.
  • R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993.

Примітки

  1. politechnique.fr - www.lix.politechnique.fr/ ~ olliver / JACOBI / jacobiEngl.htm
  2. http://www.ams.jhu.edu/ ~ castello/362/Handouts/hungarian.pdf - www.ams.jhu.edu/ ~ castello/362/Handouts/hungarian.pdf

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Угорський форинт
Угорський пенге
Фінно-угорський міфологія
Андрій Угорський (герцог Калабрійській)
Алгоритм
EM-алгоритм
Алгоритм Ву
Алгоритм де Кастельжо
Алгоритм Брезенхема
© Усі права захищені
написати до нас