Привет! Подскажите пожалуйста алгоритм для нахождения подмножества строк матрицы, чья сумма является 0-вектором (mod 2).

Перебором

Перебераешь все двойки векторов

Потом все тройки векторов

И так далее

А это не будет полным перебором ? Возможно я ошибаюсь, но по-моему этот алгоритм носит экспоненциальную сложность. Может существует более быстрый алгоритм. 

можно попробовать посмотреть процедуру Гаусса
если до конца добираемся - значит, матрица невырожденная, и никакая комбинация не даст нуля
если нет - значит, обнаружили линейно зависимое подмножество, из которого можно выбирать слагаемые для нулевой суммы

А количество решений разве не может быть эспоненциальным?
Конечно может. Возьмите все строки одинаковые. Тогда будет экспоненциальное количествое решений. И для их распечатывания понадобиться экспоненциальное время

Это сообщение отредактировал(а) esperanto - 13.11.2009, 23:18

для вывода всех решений, конечно, понадобится экспоненциальное время, а вот одно, похоже, можно найти за O(n^3):

можно попробовать немного модифицированную процедуру Гаусса:

• находим вектор у которого раньше всего начинаются единицы, перемещаем его на первую строчку (меняем с первой строчкой для простоты)
• если есть несколько таких векторов, то добавляем этот выбранный вектор к каждому из них
• повторяем эту операцию, исключая из рассмотрения первый вектор

в конце концов останется один вектор
если он ненулевой, строки линейно независимы (т.к., по сути получилась немодифицированная процедура Гаусса с точностью до перестановки столбцов), если нулевой, то нужно посмотреть, какие строки к нему добавлялись в процессе, это подмножество и будет ответом

     Спасибо за высказанные идеи. Буду разбираться. Может кто-то ещё что-нибудь может посоветовать, пишите свом мысли, буду очень рад.   



     Ничего не имею против, просто думаю, что может существует более эффективный алгоритм.