Венгерский алгоритм - метод Wikipedia для этого примера не работает
Я пытаюсь реализовать венгерский алгоритм в C.
У меня есть матрица:
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
И я дошел до стадии, когда мне нужно найти минимальное количество строк, чтобы покрыть все нули (выполняя как можно больше назначений). Очевидно, что при проверке это столбцы 1 и 3 и строка 1.
Википедия предлагает следующий метод:
- Строка 1 имеет три нуля: выбрать любой (я выбираю первый) и назначить его
- Строка 2: присвоить первый ноль
- Ряд 3: назначить третий ноль
- Строка 4 не назначена (так как единственный ноль находится в столбце, который уже имеет назначенный ноль)
Если я следую этому для моей матрицы выше, я получаю:
35 0' 0 0
0' 30 0 5
55 5 0' 10
0 45 30 45
Где нулевое простое число - назначенный ноль. Затем, следуя приведенным ниже инструкциям Википедии, я отмечаю строку 4 (нулевой неназначенный), столбец 1 (столбец с нулевым нулем), затем строку 2 (строка с нулем в отмеченном столбце).
Так что можно предположить, что минимальные строки для попадания во все нули:
+--------
|
+--------
|
Но это не ноль в (2, 3), Соответствующий код C:
for (i = 0; i < M->size; i++) {
for (j = 0; j < M->size; j++) {
if (M->values[i][j] == 0) {
if (assigned_cols[j] == 0) {
assigned_cols[j] = 1; // We've assigned something in this col
assigned_rows[i] = 1; // We've assigned something in this row.
marked_rows[i] = 0;
total--;
break; // Go to the next row
} else {
marked_cols[j] = 1; // Then there exists a zero in this col in an unassigned row
mark_col(M, j); // marks all elements in column j
total++;
}
}
}
}
Этот код выбирает, какие нули являются нулевыми простыми (присваивает нули).
Затем этот код отмечает все строки, имеющие присвоения во вновь помеченных столбцах:
for (i = 0; i < M->size; i++) {
if (marked_cols[i] == 1) {
for (j = 0; j < M->size; j++) {
//iterating through rows
if (M->values[j][i] == 0) {
// then (j,i) is a zero in a marked col
// mark the row
if (marked_rows[j] != 1) {
total++;
marked_rows[j] = 1;
}
break; // no need to continue more
}
}
}
}
Но это (и объяснение Википедии) не работает для моей матрицы выше. Как так?
1 ответ
В Википедии отсутствует объяснение алгоритма, задания будут выполнены на последнем шаге!
ШАГ 0
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
ШАГ 1-2 все строки-столбцы имеют по крайней мере один 0, поэтому шаг 1 оставляет массив одинаковым
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
ШАГ 3
Все нули в матрице должны быть покрыты маркировкой как можно меньшего числа строк и / или столбцов.
- - - -
| |
| |
| |
Обратите внимание, что до сих пор не сделано никаких заданий, и вам необходимо all zeros, Ваше покрытие оставило ноль (2,3) непокрытым!!
Теперь возьмите минимальный элемент, который не покрыт, например, 5 (возьмите 5 в позиции (2,4))
-Уменьшить (на 5) все элементы, которые не покрыты.
-Увеличить (на 5) все элементы, пересекаемые двумя линиями.
- отдых остается таким же
Итак, массив:
40 0 5 0
0 25 0 0
55 0 0 5
0 40 30 40
Теперь проверьте еще раз минимальные обязательные строки: теперь вам нужно 4 строки (равных размеру n=4 строк массива, поэтому мы остановимся).
Наконец, назначение: начинайте со строк только с одним нулем, это обязательно будет назначено:
40 0 5 _
0 25 _ 0
55 _ 0 5
_ 40 30 40
Существует несколько назначений (я использую _ для назначения).
Более конкретно, два задания мы получаем: (одно указано выше с общей стоимостью 5) и:
40 _ 5 0
0 25 0 _
55 0 _ 5
_ 40 30 40
С также стоит 5!
РЕДАКТИРОВАТЬ
На основании комментариев кажется, что я не получил точную часть, которую запрашивал op, поэтому я отвечу на эту конкретную часть, оставив общее описание алгоритма выше.
Ошибка (из-за плохого описания Википедии) здесь:
Где нулевое простое число - назначенный ноль. Затем, следуя приведенным ниже инструкциям Википедии, я отмечаю строку 4 (нулевой неназначенный), столбец 1 (столбец с нулевым нулем), затем строку 2 (строка с нулем в отмеченном столбце).
Полностью согласен до сих пор, но... это не завершено!!!
При правильной маркировке строки 2 необходимо перейти к шагу 2 (из Википедии) и еще раз проверить наличие столбцов с нулями, в этом случае также должен быть отмечен столбец 3, это также приводит к тому, что строка 3 также будет отмечена (из-за назначенного нуля в вновь отмеченный столбец 3) и там вы останавливаетесь (никакие другие строки или столбцы не должны быть отмечены)!!
Итак, в целом отмеченные столбцы и строки:
+ +
35 0' 0 0
0' 30 0 5 +
55 5 0' 10 +
0 45 30 45 +
И строки, которые вы получите, выбрав отмеченные столбцы и немаркированные строки:
- - - -
| |
| |
| |
который является правильным, как описано в первой части ответа, и приводит к правильным результатам на следующих этапах (также объяснено выше).
Один очень похожий пост, в котором говорится, что буквально то же самое можно найти на mathstackexchange:
найти минимальное количество строк для покрытия всех нулей в задании