Мне нужно найти алгоритм (предпочтительно на Java) для решения следующей проблемы (в надежде, что она будет четко выражена):
Учитывая матрицу (не обязательно квадратную) из значений 1 и 0, например,следующее:
Я должен иметь возможность определить максимальное количество ячеек, чтобы не было пар ячеек среди выбранных, имеющих общую строку или столбец.
Например, если была выбрана ячейка (Row_A, Col_Y), то ячейки (Row_A, Col_V), (Row_A, Col_S), (Row_C, Col_Y), (Row_G, Col_Y) должны быть исключены.
Проблема должна быть решенав виде двудольного графа, где разделение узлов представлено строками, а столбцы - другими.Существует связь только между узлами, которые имеют 1 в соответствующих ячейках.
Таким образом, у нас будет раздел Part_Row, который будет содержать следующие узлы: A, B, C, D, E, F, G.В то время как раздел Part_Col будет содержать узлы: Z, Y, X, W, V, T, S, R, Q. Арки будут:
A->Y, A->S
B->Z, B->D
C->Y, C->X, C->S,
etc., etc.
Как определить максимальное количество ячеек?Имеет ли смысл решать проблему максимального соответствия как проблему максимального потока?