Как следует из названия, это связано с проблемой назначения, когда нужно минимизировать / максимизировать стоимость в соответствии с функцией объекта. Все подобные проблемы связаны с проблемами оптимизации.

Давайте разберемся на простом примере. Например: если вы хотите устроить вечеринку, вам нужно искать украшения, кухню, такси, уборку и т. Д. И у вас есть несколько брокеров / человек, которые назвали свою цену за одну или несколько вакансий. Теперь возникает вопрос, какой из них выбрать ?. Возможно, один работник дает мне наименьшую цену, но выбрать этого человека для всех работ непрактично (поскольку у нас есть ограничение, согласно которому только один человек может быть задействован для одной работы)?

Комбинированная техника: если есть 3 рабочих и 3 рабочих места, и мы знаем, что никакие две работы не могут быть выполнены одним и тем же работником. 3C1 (выбор 1 из 3) X 2C1 (выбор 1 из 2, поскольку 1 уже занято первой комбинацией) X 1C1 = n! = 6 комбинаций [выберите самую дешевую из 6 списков]. Но есть проблема, если 'n' становится все больше и больше, время вычислений становится очень большим.

Предположим, Задания определены как (j1, j2 .. jn), Рабочие определены как (w1, w2 .. wn), а матрица затрат определяется как (C j [ 1..2], w1 | C j [1..2..3], w2 | Cj3, w3… Cjn, wn), где 'C j [1..2], w1' - стоимость для J 1, J 2 Работник 1 может выполнить задание. Существует два подхода, а именно:

  • Жадный: отсортируйте рабочих согласно цене, указанной для каждого задания в возрастающем порядке (скажем, C j1, w1 ‹Cj1, w2‹ C j2, w1 ‹Cj2, w2‹ Cj3, w2 ‹Cj3, w3, если вы развернете выше матрицу затрат) . Выберите первый и назначьте J 1 на W 1 и удалите w1 и j1 из приведенного выше списка, т.е. {C j2, w1, Cj1, w2} (потому что теперь w1 не может выполнять более 1 работы одновременно). L1: (Cj2, w2 ‹Cj3, w2‹ Cj3, w3), выберите первый снова и назначьте J 2 на W 2 и удалите w2 и j2 из приведенного выше списка, т.е. С j3, w2. Таким образом, я получаю [j1- ›w1, j2-› w2 и j3- ›w3]. Но подождите одну секунду, достигаю ли я оптимального решения? Нет! Причина очевидна, потому что я беру первую самую дешевую стоимость и назначаю, не думая, что общая стоимость может вырасти. например, что если, Cj1, w2 ‹---------------- C j2, w1. так что эта комбинация будет на [j1- ›w2, j2-› w1 и j3- ›w3] более оптимальной, чем предыдущая. Мы просто попали в локальную ловушку, вот в чем проблема жадных !!
  • Оптимизированный: этот алгоритм, который мы, возможно, слышали в наших методах оптимизации, является двудольным венгерским. Если вы внимательно присмотритесь, множества [w1, w2 .. wn] и [j1, j2 .. jn] - это непересекающиеся множества, в которых наше двудольное сопоставление входит в картину. First and Foremost преобразовать в список смежности, предположим, что это выглядит как

Строки :: Вакансии и столбцы :: Рабочие. Итак, выполнение Job-2 с помощью Worker-2 снимает затраты в 250 долларов.

Если мы пойдем по алгоритму, он говорит:

  1. Найдите наименьшую стоимость в каждой строке отдельно и вычтите соответствующую стоимость в соответствующей строке.
  2. Найдите наименьшую стоимость в отдельном столбце и вычтите соответствующую стоимость в соответствующем столбце.
  3. Проведите линию над строками или столбцами, в которых нет записей, так, чтобы было нарисовано минимальное количество линий.
  4. Посмотрите, нарисованы ли линии = n, тогда ваш алгоритм завершен и остановлен.
  5. Если нарисованы линии ‹n. Найдите наименьшую стоимость среди непокрытых ячеек и вычтите строки, которые не являются разбросом штрихов, и добавьте столбцы, которые отбрасываются штрихами.
  6. Перейти к шагу 3.

Вычтите 100 из строки 1, 250 из строки 2 и 150 из строки 3.

Вычтите 0 из col1, 0 из col2 и 150 из col3.

Проведите линии. 2 строки ‹3 (что равно’ n ’в нашей матрице затрат). Теперь найдите наименьший элемент среди непокрытых ячеек (а это 100).

  • Вычтите 100 из всех строк, которые не зачеркнуты, т.е. 1-я и 3-я строки. (0,0) - ›-100 и (0,1) -› -100
  • Добавьте 100 во все зачеркнутые столбцы, т. Е. В 1-й столбец. (0,0) - ›(-100 + 100), (0,1) -› (-1) (- 100 + 100)

Это последняя матрица, так как минимальное количество строк с нулевыми элементами = 3 (что равно «n»).

Итак, мы выбрали j3 на w3, j2 на w2 и j1 на w1 (350 + 250 + 150 = 750) будут моей оптимальной стоимостью.

Примечание.

  • Важно иметь квадратную матрицу, чтобы, если вы занимаетесь сортировкой заданий, помещать наивысшее значение в ячейку, соответствующую этому работнику.
  • Сценарии использования могут варьироваться от проблемы к проблеме, например, от организации вечеринок, логистики, от водителей до рабочих заданий и т. Д.
  • Вы когда-нибудь заказывали такси для междугороднего сообщения? И, если вы когда-нибудь замечали, почему они говорят, водитель будет уведомлен за 1 или 2 часа до вашей поездки, даже после бронирования за 3 дня вперед :)
  • Все, что требуется, - это понимание сценария использования и его грамотная настройка.

Спасибо руководителю моей группы за то, что позволил мне поработать над такими вещами и помог мне понять красоту алгоритмов. Прокомментируйте в этом посте свои варианты использования или все, что требует подробностей, что поможет нам вместе развиваться.

Другие проблемы с заданиями будут в моем следующем посте ...