Венгерский алгоритм

Question

Я нашел реализацию венгерского алгоритма, но у меня есть вопрос о значении "звездный ноль" и "загрунтованный ноль". Я думаю, что это используется для обозначения отмеченного нуля, но я не уверен. Это правильно?

Это код: http://ccp.uchicago.edu/khetarpal/code/edit-distance/HungarianAlgorithm.java

Благодарю.

Answer 1

Как вы должны знать, венгерский (или Кун-Мункрес) алгоритм является комбинаторным алгоритмом оптимизации, который решает проблему назначения. Он состоит из набора операций, примененных к квадратной матрице, значения ячеек которой являются функцией стоимости назначения "задачи" i для "работника" j или "работника" i для "задачи" j. Будучи i и j номера строк и столбцов соответственно. Здесь я привожу краткое описание используемой вами реализации, чтобы вы могли понять, какова цель помечать и заполнять ячейки (или нули).

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

Шаг 1 (reduMatrix): для каждой строки найдите наименьший элемент и вычтите его из каждого элемента в его строке. Перейти к шагу 2.

Шаг 2 (initStars): найдите ноль (Z) в полученной матрице. Если в строке или столбце нет звездного нуля, звездочка Z. Повторите для каждого элемента в матрице. Перейти к шагу 3.

Шаг 3 (coverColumnsOfStarredZeroes): покройте каждый столбец, содержащий ноль со звездочкой. Если покрыты K столбцов, отмеченные нулями нули описывают полный набор уникальных назначений. В этом случае перейдите к ВЫПОЛНЕНО, в противном случае перейдите к шагу 4.

Шаг 4 (primeSomeUncoveredZero): найдите непокрытый ноль и заполните его. Если в строке, содержащей этот загрунтованный ноль, звездного нуля нет, перейдите к шагу 5. В противном случае закройте эту строку и раскройте столбец, содержащий ноль со звездочкой. Продолжайте в том же духе, пока не останется никаких открытых нулей. Сохраните наименьшее раскрытое значение и перейдите к шагу 6.

Шаг 5 (incrementSetOfStarredZeroes): Постройте последовательность чередующихся начальных и помеченных звездочек следующим образом. Пусть Z0 представляет непокрытый штрихованный ноль, найденный на шаге 4. Пусть Z1 обозначает звездный ноль в столбце Z0 (если есть). Пусть Z2 обозначает загрунтованный ноль в строке Z1 (всегда будет один). Продолжайте до тех пор, пока ряд не завершится в загрунтованном нуле, который не имеет звездного нуля в своем столбце. Снимите звездочку с каждого звездного нуля ряда, пометите звездочкой каждый нулевой ряд, сотрите все простые числа и раскройте каждую строку в матрице. Вернитесь к шагу 3.

Шаг 6 (makeMoreZeroes): добавьте значение, найденное на шаге 4, к каждому элементу каждой покрытой строки и вычтите его из каждого элемента каждого непокрытого столбца. Вернитесь к шагу 4 без изменения звездочек, простых чисел или закрытых линий.

СОВЕРШЕНО: пары назначений обозначены позициями звездочек в матрице затрат. Если C(i,j) - звездный ноль, то элемент, связанный со строкой i, присваивается элементу, связанному со столбцом j.

Надеюсь это поможет.