Комментарии 6
Вот что непонятно, а что делать с тождественными уравнениями? Это же нигде не проверяется.
В простейшем случае линейных уравнений, может быть так, что одно уравнение есть линейная комбинация других. Если случайно взять их все, то одно из них будет бесполезным. И может так получится, что выбранный набор недостаточен для нахождения нужной переменной.
И вообще очень странно описано. Сначала у вас граф двудольный, с вершинам уравнениями и вершинами переменными. В этом графе вообще компонент сильной связности нет (кроме тривиальных). А потом вы отождествляете вершину-уравнение и вершину-переменную и уже в этом графе ищите КСС. Почему это работает вообще?
Кстати, ваш наивный алгоритм перестановки строк будет очень медленным. Там фактически O(n^n). Можно заметить, что эта задача эквивалентна задаче поиска максимального паросочетания в двудольном графе и решается за O(n^3) алгоритмом Куна.
Не вникал в код и пока вообще не понял что здесь и о чем.
Просто возникла мысль, что если матрицу сделать в стиле С++, то перестановку строк можно будет делать очень быстро через перестановку ссылок на строки.
Мысль интересная, но на практике не важная.
Во-первых, перестановка строк - это доли процента от основной работы (перебор перестановок у автора. И даже если реализовать паросочетания, то все равно, перестановка O(n^2), когда как основная часть будет O(n^3)).
Во-вторых, если массив не расплющивать в один линейный, то любое обращение к нему будет через 2 адресации, вместо одной, что заметно медленнее. Так что не факт что ваша оптимизация вообще в плюс, хоть и минимальный.
Во-вторых, если массив не расплющивать в один линейный, то любое обращение к нему будет через 2 адресации, вместо одной, что заметно медленнее. Так что не факт что ваша оптимизация вообще в плюс, хоть и минимальный.
В моих тестах на алгоритме Гаусса (решение системы линейных уравнений) сравнение двойной адресации и расплющивания в линейный массив дают:
на clang: производительность одинаково высокая (как в варианте с двойной адресацией на msvc).
на msvc: "расплющивание" мешает компилятору применять SSE / AVX векторизацию из-за чего вариант с двойной адресацией работает в 2-3 раза быстрее.
И это тесты без использования выигрыша от возможности быстрой перестановки строк.
Пруфы выложу позже, когда наиграюсь с этими эффектами и оформлю их в статью.
Дана система, состоящая из большого количества уравнений (необязательно линейных), где вам необходимо найти всего лишь несколько переменных.
А можно привести примеры, где такое можно встретить на практике? Зачем оно может понадобиться?
Алгоритм Тарьяна для поиска минимального набора уравнений