Алгоритм выбора точек из матрицы

Question

Кажется, это простая проблема, но я застрял в этой проблеме. Проблема в том, что у меня матрица размером X x Y. Там может быть несколько точек в (I, J). Однако не обязательно, чтобы все местоположения (i, j) имели точку (то есть

Answer 1

Это проблема максимальное совпадение , которая разрешима по времени.Учитывая пример вашей проблемы, постройте двудольный граф с узлами a ₁ ,…, a _X , b ₁ ,…, b _Y и ребра a _i b _j для всех (i, j), где есть точка.Возьмите точки, соответствующие ребрам в максимальном соответствии.

Answer 2

Построить график.Точки - вершины графа.Каждая вершина связана со всеми вершинами в одной строке и одном и том же столбце - ребрах графа.Ваша задача - выбрать максимум независимый набор вершин (без общих ребер).

Independent_set

Эта проблема эквивалентна проблеме максимального клика в графе дополнения, поэтому можно использовать алгоритм Брон-Кербоша.

http://en.wikipedia.org/wiki/Clique_problem#Finding_maximum_cliques_in_arbitrary_graphs

http://en.wikipedia.org/wiki/Complement_graph

Алгоритм Брон-Кербоша