| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск подмножества строк матрицы |
| Автор: Vitkaz 13.11.2009, 08:34 |
| Привет! Подскажите пожалуйста алгоритм для нахождения подмножества строк матрицы, чья сумма является 0-вектором (mod 2). |
| Автор: esperanto 13.11.2009, 13:52 |
| Перебором Перебераешь все двойки векторов Потом все тройки векторов И так далее |
| Автор: Vitkaz 13.11.2009, 14:53 | ||
А это не будет полным перебором ? Возможно я ошибаюсь, но по-моему этот алгоритм носит экспоненциальную сложность. Может существует более быстрый алгоритм. |
| Автор: maxim1000 13.11.2009, 22:48 |
| можно попробовать посмотреть процедуру Гаусса если до конца добираемся - значит, матрица невырожденная, и никакая комбинация не даст нуля если нет - значит, обнаружили линейно зависимое подмножество, из которого можно выбирать слагаемые для нулевой суммы |
| Автор: esperanto 13.11.2009, 23:10 | ||||
А количество решений разве не может быть эспоненциальным? Конечно может. Возьмите все строки одинаковые. Тогда будет экспоненциальное количествое решений. И для их распечатывания понадобиться экспоненциальное время |
| Автор: maxim1000 14.11.2009, 10:03 |
| для вывода всех решений, конечно, понадобится экспоненциальное время, а вот одно, похоже, можно найти за O(n^3): можно попробовать немного модифицированную процедуру Гаусса:
в конце концов останется один вектор если он ненулевой, строки линейно независимы (т.к., по сути получилась немодифицированная процедура Гаусса с точностью до перестановки столбцов), если нулевой, то нужно посмотреть, какие строки к нему добавлялись в процессе, это подмножество и будет ответом |
| Автор: Vitkaz 14.11.2009, 14:17 | ||
Спасибо за высказанные идеи. Буду разбираться. Может кто-то ещё что-нибудь может посоветовать, пишите свом мысли, буду очень рад. 
Ничего не имею против, просто думаю, что может существует более эффективный алгоритм. |