Венгерский алгоритм - произвольный выбор
Я рассмотрел несколько объяснений венгерского алгоритма для решения проблемы назначения, и подавляющее большинство из них покрывают очень упрощенные случаи.
Самое понятное объяснение, которое я нашел, - это видео на YouTube.
Я могу написать алгоритм, но меня беспокоит один особый случай. Если вы смотрите видео, соответствующий случай объясняется с 31:55 до 37:42, но я объясню это ниже.
Прежде всего я должен упомянуть, что я буду иметь дело с матрицей 300 x 300, поэтому о визуальном осмотре не может быть и речи. Кроме того, мне нужно найти все минимальные задания. Другими словами, если есть несколько назначений, которые дают одинаковое минимальное значение, мне нужно найти их все.
Вот частный случай, который меня беспокоит. Вы можете увидеть это в видео на YouTube, но я расскажу об этом здесь. Начнем с этой матрицы:
3 1 1 4
4 2 2 5
5 3 4 8
4 2 5 9
Когда мы уменьшаем строки и столбцы, мы получаем это:
0 0 0 0
0 0 0 0
0 0 1 2
0 0 3 4
(Позвольте мне упомянуть, что я могу визуально увидеть, что есть 4 решения для этой матрицы, и общая оценка составляет 13).
Учитывая приведенную выше уменьшенную матрицу, в каждой строке или столбце нет уникальных нулей, поэтому в соответствии с алгоритмом, описанным в видео, я могу произвольно выбрать любой нулевой элемент для назначения, поэтому я выбираю (1,1).
Я помечу назначенный ноль звездочкой и поставлю "x" рядом с теми нулями в строках и столбцах, которые больше не доступны для рассмотрения. Теперь у нас есть это:
0* 0x 0x 0x
0x 0 0 0
0x 0 1 2
0x 0 3 4
Далее мы продолжим изучение строк на предмет уникального нуля. Мы находим один в (3,2), поэтому помечаем его звездочкой и отмечаем недоступные нули знаком "x":
0* 0x 0x 0x
0x 0x 0 0
0x 0* 1 2
0x 0x 3 4
Далее мы начинаем искать уникальные нули в столбцах (так как все строки были исчерпаны). Мы находим, что столбец три имеет уникальный ноль в (2,3), поэтому мы помечаем его:
0* 0x 0x 0x
0x 0x 0* 0x
0x 0* 1 2
0x 0x 3 4
На этом этапе больше нет доступных нулей, и строка 4 оставлена неназначенной. (Это конкретное видео на YouTube теперь использует "процедуру тикования", которая является обычной техникой для определения минимального количества строк, необходимых для покрытия всех нулей. Если вы не знакомы с этой техникой, это объясняется начиная с 14:10 до 16:00, хотя докладчик использует матрицу, отличную от показанной здесь.) "Процедура тика" заключается в следующем:
- Отметьте все строки, которые не имеют назначенных нулей (строка 4).
- Для каждой отмеченной строки отметьте столбцы, которые содержат ноль в этой строке.
- Для каждого столбца, отмеченного на шаге 2, отметьте соответствующие строки, которым назначены нули.
- Повторяйте шаги 2 и 3 до тех пор, пока тиканье не станет возможным.
- Нарисуйте линии через все отмеченные столбцы и не отмеченные строки.
На этом этапе процедура тиканья генерирует 4 вертикальные линии, охватывающие все нули. Четыре вертикальные линии говорят нам, что нули в матрице представляют одно или несколько решений, но, как мы видим, строка 4 не назначена. Тот факт, что четвертый ряд остается неназначенным, несмотря на четыре вертикальные линии, говорит нам о том, что мы выбрали неправильные нули для назначения!
Ведущий видео указывает, что эта проблема является результатом нашего начального (произвольного) назначения элемента (1,1). Докладчик говорит: "Есть более сложные методы", чтобы вытащить нас из этой ситуации, потому что он не объясняет, что это за методы. Он ссылается на существование "интеллектуальных" способов выбора нуля, а не на произвольный выбор, который мы использовали для выбора нуля в (1,1).
Один из подходов, который я мог бы использовать (я не уверен, что это лучший вариант), когда он сталкивался с выполнением произвольного присваивания, - это сделать присвоение из строки или столбца с наименьшим количеством доступных произвольных вариантов. В этом примере это означает, что я бы сделал произвольное назначение из строки 3 или 4, где есть только два произвольных выбора, а не из строки 1 или 2, где есть четыре произвольных выбора. Конечно, поскольку мне нужны все правильные решения, мне нужно было бы перебирать все доступные произвольные назначения всякий раз, когда производится произвольное назначение. Например, если я выберу (3,1) в качестве произвольного присваивания, мне также придется присваивать (3,2) позже.
После всего этого у меня возникает вопрос: каков наилучший подход, когда я сталкиваюсь с выбором произвольного выбора нуля для назначения? Это то, что я упоминаю в предыдущем абзаце? Как я могу устранить тупиковые решения, подобные показанному? Пожалуйста, помните, мне все еще нужно перечислить все решения, имеющие одинаковый минимальный балл.
2 ответа
После того, как шаги вычитания были выполнены для всех строк и столбцов, как вы сделали, в алгоритме есть этот шаг, который требует, чтобы вы нашли минимальное количество строк или столбцов, которые вы можете вычеркнуть, чтобы не найти больше нулей в ячейках, которые являются осталось (см. шаг 3 в статье Википедии). Если это минимальное количество зачеркнутых строк / столбцов равно n, то вы пришли к матрице, в которой назначения могут быть сделаны в позициях, которые все представлены нулями.
Это случай в вашей второй матрице.
Затем есть также этот шаг алгоритма, когда вы выполнили все возможные шаги вычитания: если строка или столбец имеет только один ноль, этот ноль представляет (оптимальное) назначение.
Я думаю, что это правило можно обобщить следующим образом:
Если каждая из i строк (или столбцов) имеет не более i нулей, то i из этих нулей представляют (оптимальные) назначения.
Это правило очевидно (и совершенно бесполезно), когда я n.
Но для малых я это может быть полезно, хотя алгоритм поиска таких строк может занимать много времени. В примере задачи мы находим для i = 2 правило, применимое к строкам 3 и 4. Правило также подразумевает, что мы можем запретить любые другие назначения в столбцах, которые содержат нули. Это означает, что мы можем написать нашу матрицу как:
- - 0 0
- - 0 0
0 0 1 2
0 0 3 4
Теперь правило может быть применено снова к строкам 1 и 2, каждая из которых теперь также имеет только 2 нуля.
Мы видим две субматрицы только из нулей (предмет, где мы применили правило):
0 0
0 0
Есть два способа сделать назначения:
x 0
0 x
или же:
0 x
x 0
В общем, для подматрицы с i строками и i столбцами существует i! решения, если все его элементы равны нулю, но меньше, некоторые из них не являются.
В конкретном примере, таким образом, 2! решения для нижней левой подматрицы, и 2! для верхней правой матрицы, в результате 4 возможных решений.
Заключение
Хотя приведенные выше соображения могут показаться интересными, я не думаю, что алгоритм, который ищет такие подматрицы, будет более производительным, чем алгоритм, который просто выбирает назначения упорядоченным образом, и возвращает его обратно, как только обнаруживает, что он неверен. трек. Поскольку вам понадобятся все решения, начинать с определенной строки не имеет смысла. Откат должен убедиться, что алгоритм не тратит время на выбор, который не имеет будущего.
В этом конкретном сценарии, когда назначение больше невозможно, потому что каждая неназначенная строка или столбец имеет более 1 нуля. Выбор строки или столбца с минимальными нулями и выполнение произвольного назначения в этой строке или столбце сработали для меня. Рассмотрение только строк и исключение столбцов также сработало (как упоминалось здесь https://python.plainenglish.io/hungarian-algorithm-introduction-python-implementation-93e7c0890e15).