Загрузить PDF
Загрузить PDF
Венгерский алгоритм позволяет находить минимальные совпадения. Его можно использовать там, где есть несколько определителей для различных групп действий, в которых каждое действие должно осуществляться разными людьми, чтобы вычислить минимальные затраты для выполнения.
Шаги
Загрузить PDF
-
Соберите всю вашу информацию в матрицу, люди должны быть слева, а действия — сверху, внутри матрицы должна быть записана стоимость каждой пары.
-
Убедитесь, что матрица квадратная, сложив количество колонок и рядов. Это количество должно быть одинаковым.
-
Если в матрице есть колонки без нулей, уменьшите колонки методом вычитания минимального значения каждой колонки из этой колонки.
-
Закройте все нулевые элементы минимальным количеством линий. Если количество линий равняется количеству рядов, переходите к 9 шагу.
-
Сложите минимальный незакрытый элемент с каждым закрытыми элементом. Если элемент закрыт дважды, сложите минимальный элемент с ним два раза.
-
Отнимите минимальный элемент от каждого элемента в матрице.
-
Закройте все нулевые элементы. Если количество линий, закрывающих нулевые элементы, не равняется количеству рядов, вернитесь к 6 шагу.
-
Выберите комбинации, обведя все нули так, чтобы в каждом ряде или колонке был выбран только один ноль.
-
Примените полученную комбинацию к оригинальной матрице , не обращая внимания на остальные ряды. Здесь указано минимальная стоимость выполнения действий различными людьми.Реклама
Советы
- Если вы хотите найти максимальную стоимость, умножьте каждое число на -1 в первом шаге.
- Ключевым моментом здесь является то, что добавление одного и того же числа ко всем записям в одной строке или столбце матрицы дает новую матрицу с тем же оптимальным решением. Именно это позволяет избежать сокращения матрицы на шаге 6.
Реклама
Что вам понадобится
- Ручка
- Бумага
Об этой статье
Эту страницу просматривали 2898 раз.
Реклама
