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

Угорський алгоритм дозволяє знаходити мінімальні збіги. Його можна використовувати там, де є кілька визначників для різних груп дій, в яких кожна дія має здійснюватися різними людьми, щоб знайти мінімальні витрати для виконання.

Кроки

1. 1

   

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

2. 2

   

   Переконайтеся, що матриця квадратна, склавши кількість колонок і рядів. Ця кількість має бути однаковим.

3. 3

   

   Зменшіть кількість рядів, віднявши мінімальне значення кожного ряду з цього ряду.







4. 4

   

   Якщо в матриці є колонки без нулів зменшите колонки шляхом вирахування мінімального значення кожної колонки з цієї колонки.

5. 5

   

   Закрийте всі нульові елементи мінімальною кількістю ліній. Якщо кількість ліній ровняется кількістю рядів, переходьте до 9 кроці.

6. 6

   

   Складіть мінімальний не закриті елемент з кожним закритими елементом. Якщо елемент закритий двічі, складіть мінімальний елемент з ним два рази.

7. 7

   

   Відніміть мінімальний елемент від кожного елемента в матриці.





8. 8

   This example had to be reduced once more

   Закрийте всі нульові елементи. Якщо кількість ліній, що закривають нульові елементи не рівняються кількістю рядів, поверніться до 6 кроці.

9. 9

   

   Виберіть комбінацію, обвівши всі нулі так, щоб у кожному ряді або колонці був вибраний тільки один нуль.

10. 10

    Notice that D has not been used

    Застосуйте отриману комбінацію до оригінальної матриці, не звертаючи увагу на інші ряди. Тут вказано мінімальна вартість виконання дій різними людьми.

Поради

• Якщо ви хочете знайти максимальну вартість, помножте кожне число на -1 в першому кроці.

Що вам знадобиться

• Ручка
• Папір