Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 67, средняя оценка - 4.99
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
#1

Оптимизация алгоритма вычисления определителя матрицы - C++

29.01.2013, 15:39. Просмотров 9185. Ответов 27
Метки нет (Все метки)

Здравствуйте!
Написал я давеча программку, которая считает определитель. Только вот беда - он не считает определители матриц выше 10 порядка - тупо не хватает памяти. Я так понимаю, это из-за того, что мой алгоритм - рекурсивный. Так вот, можно ли больше оптимизировать мой код, или эта рекурсия - заведомо плохой вариант?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
//Определитель вычисляется по формуле det( A ) = a( i, j ) * ( -1 )^( i + j ) * M( i, j ) ( a^b - "а" в степени "b" )
//Минор ищется рекурсивно до тех пор, пока его порядок не стал равен 2 ( тогда в силу вступает формула a( 1, 1 ) * a( 2, 2 ) - a( 1, 2 ) * a( 2, 1 ) )
//На каждом шаге определитель находится путем разложения по наиболее "оптимизированной" строке ( в которой больше всего нулей ) данной на вход матрицы
 
//Примечание: в этих комментариях считается, что коэф. пробегают значения от 1 до n ( в самой программе они пробегают значения от 0 до n-1 )
 
#include <time.h>
#include <iostream>
#include <math.h>
 
using namespace std;
 
//Функция нахождения у матрицы порядка size минора M( str, stb ) ( возвращает минор в матричном представлении )
int **FIND_Minor( int **matrix, int size, int str, int stb )
{
    int **minor = new int *[ size - 1 ];
    
    //m_str, m_stb - коэффициенты, с помощью которых строится сам минор
    int m_str = 0;
    int m_stb;
    for( int i = 0; i < size; i++ )
    {
        //Элементы из строки с номером str не записываются в минор
        if( i != str )
        {
            m_stb = 0;
            minor[ m_str ] = new int[ size - 1 ];
            for( int j = 0; j < size; j++ )
            {
                //Элементы из столбца с номером stb не записываются в минор
                if( j != stb )
                {
                    minor[ m_str ][ m_stb ] = matrix[ i ][ j ];
                    m_stb++;
                }
            }
            m_str++;
        }
    }
 
    return minor;
}
 
int FIND_Det( int **matrix, int size )
{
    //Проверка условия выхода из рекурсии
    if( size == 2 )
    {
        return matrix[ 0 ][ 0 ] * matrix[ 1 ][ 1 ] - matrix[ 0 ][ 1 ] * matrix[ 1 ][ 0 ];
    }
    else if( size == 1 )
    {
        return matrix[ 0 ][ 0 ];
    }
 
    //Момент оптимизации - ищем строку, в которой больше всего нулей, чтобы по ней находить определитель
    //Работает в связи с условием разложения по строке, которое пояснено ниже
    int max_0, str_0 = 0, max_0_b = 0;
    for( int i = 0; i < size; i++ )
    {
        max_0 = 0;
        for( int j = 0; j < size; j++ )
        {
            if( matrix[ i ][ j ] == 0 )
            {
                max_0++;
            }
        }
        if( max_0 > max_0_b )
        {
            str_0 = i;
            max_0_b = max_0;
        }
    }
 
    //Само рекурсивное разложение по строке
    int result = 0;
    for( int j = 0; j < size; j++ )
    {
        //Небольшой момент оптимизации - если текущий элемент в строке равен нулю, то дальше продолжать рекурсию нету смысла 
        //( т.к. произведение будет равно нулю в любом случае )
        if( matrix[ str_0 ][ j ] )
        {
            result += matrix[ str_0 ][ j ] * ( unsigned )pow( -1.f, ( unsigned )j ) * FIND_Det( FIND_Minor( matrix, size, str_0, j ), size - 1 );
        }
    }
 
    return result;
}
 
int main()
{
    srand( ( unsigned )time( NULL ) );
 
    float begin, end;
 
    int size;
    cout << "Enter size: ";
    cin >> size;
    int **matrix = new int*[ size ];
 
    char sw;
    cout << "\n1 - Typing automatically\n2 - Typing manually\n";
    cin >> sw;
 
    switch( sw )
    {
    case '1':
        cout << "\nMatrix:\n";
        for( int i = 0; i < size; i++ )
        {
            matrix[ i ] = new int[ size ];
            for( int j = 0; j < size; j++ )
            {
                matrix[ i ][ j ] = rand()%10;
                cout << matrix[ i ][ j ] << " ";
            }
            cout << "\n";
        }
        break;
 
    case '2':
        cout << "\nYour matrix:\n";
        for( int i = 0; i < size; i++ )
        {
            matrix[ i ] = new int[ size ];
            for( int j = 0; j < size; j++ )
            {
                cin >> matrix[ i ][ j ];
            }
        }
        break;
 
    default:
        cout << "\n";
        system( "pause" );
        return 0;
    }
 
    cout << "\nDeterminant = ";
    begin = clock();
    cout << FIND_Det( matrix, size ) << endl;
    end = clock();
 
    cout << "\nTask time - ";
    cout << ( end - begin ) / 1000 << " seconds" << endl;
 
    system( "pause" );
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.01.2013, 15:39
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Оптимизация алгоритма вычисления определителя матрицы (C++):

Улучшение алгоритма вычисления определителя матрицы, порядка n>3 - C++
Всем доброго времени суток, я достаточно долго искал шаблон кода для вычисления определителя квадратной матрицы, нашел на просторах рунета...

Код вычисления определителя матрицы до 10-го порядка - C++
Мне очень нужен код программы для вычисления определителя матрицы до 10-го порядка.

Рекурсивный метод вычисления определителя матрицы - C++
суть в том, что не получается реализовать рекурсивный метод Determinant в классе Matrix. #include &lt;iostream&gt; using namespace std; ...

Написать функцию для вычисления определителя матрицы - C++
Нужна функция для вычисления ОПРЕДЕЛИТЕЛЯ матрицы, аргументами которой будет количество строк в матрице N и сама матрица. п.с. или ссылку...

Создать функцию для вычисления определителя матрицы 2х2 - C++
Создать функцию для вычисления определителя матрицы 2х2. (в C++) HELP ME PLEASE

Подстроение алгоритма определителя - C++
Доброго времени суток уважаемые форумчане! Мне уже надоело искать нормальный и рабочий алгоритм для вычисления определителя. Есть два кода:...

27
Smetanka
56 / 17 / 1
Регистрация: 14.05.2012
Сообщений: 134
29.01.2013, 17:16 #2
Lexp, ну сама по себе рекурсия есть не очень хорошо в плане скорости. Странно что не хватает памяти(а как вы поняли что ее не хватает?) ведь у компьютера сейчас например 2гб оперативной памяти + подкачка. Короче много. Плюс ко всему сам по себе ваш алгоритм поиск миноров( разложение Лапласа кажется правильно ) ну ооочень медленный. Работает аж за O(n!). Например у вас 10!=3628800. Может и можно как то оптимизировать,если хорошо проанализировать код(убрать какие нибудь ненужные действия,или как нибудь их объединить),но высокого прироста к производительности вы не получите
0
-=ЮрА=-
Заблокирован
Автор FAQ
29.01.2013, 17:30 #3
Lexp, посмотри 4.4.3 Матричный способ нахождения определителя
2
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.01.2013, 18:16 #4
У вашего алгоритма страшная сложность. Горадо лучше привести эту матрицу к треугольному виду гауссом, а там уже несложно посчитать детерминант за линию.
1
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 18:24  [ТС] #5
Цитата Сообщение от diagon Посмотреть сообщение
У вашего алгоритма страшная сложность. Гораздо лучше привести эту матрицу к треугольному виду гауссом, а там уже несложно посчитать детерминант за линию.
Да, сложность кошмарная, тут согласен. Видимо придется действительно Гаусса использовать, как-то сразу не додумался...
0
-=ЮрА=-
29.01.2013, 18:34
  #6

Не по теме:

Цитата Сообщение от Lexp Посмотреть сообщение
Да, сложность кошмарная, тут согласен. Видимо придется действительно Гаусса использовать, как-то сразу не додумался...
- ели считать по свойству определителя то Гассу нет! Гаусс может лишь рассматриваться как оптимизация да и то не из лучших, те кто пишут им определители просто идут по пути наименьшего сопротивления. Причём всегда надо пробовать идти по нелёгкому пути, чтобы потом сравнить с лёгким и выбрать лучшее для той или иной СЛАУ.

0
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 18:40  [ТС] #7
Самый нелегкий путь тут - нахождение определителя прямо по определению (сумма всевозможных комбинаций того-то и того-то). Там и сложность по идее меньше будет, только вот как реализовать...
0
-=ЮрА=-
Заблокирован
Автор FAQ
29.01.2013, 18:50 #8
Цитата Сообщение от Lexp Посмотреть сообщение
амый нелегкий путь тут - нахождение определителя прямо по определению (сумма всевозможных комбинаций того-то и того-то). Там и сложность по идее меньше будет, только вот как реализовать...
- ну так по линку в посте выше так его и нахожу

Не по теме:

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
При этом, с помощью миноров можно облегчать задачу вычисления определителя матрицы. Надо разложить определитель матрицы по некоторой строке и тогда определитель будет равен сумме всех элементов этой строки на их миноры. Разложение определителя матрицы 3 - его порядка будет выглядеть так:
знак перед произведением равен aij и Mij



Добавлено через 1 минуту
Причем ниже в 5.2 уже вообще сингл функция детерминанта идёт
Кликните здесь для просмотра всего текста
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//Функция возвращает детерминант матрицы
//В функции всё понятно кроме iShowStepsOfCalcs 
//iShowStepsOfCalcs - это флаг отвечающий за то чтобы
//светить или нет в консоли результаты промежуточных вычислений
//Вообще вывод промежуточных вычислений полезнаяя штука для понимания
//работы рекурсии, кому понтравится может перенаправить вывод
//промежуточных результатов в файл. Единственный минус промежуточной индика
//ции - существенное увелечиние времени вычислений
double Det(int m, double ** arr, int iShowStepsOfCalcs)
{
    int i, j = 0;
    double ret = 0;
    double A;
    double ** _arr;
    if(m == 2)//В случаем 2х2 вычисляем детерминант сразу
    {
        ret = 
            arr[0][0]*arr[1][1] - 
            arr[1][0]*arr[0][1];
        if(iShowStepsOfCalcs)
            printf("Det = %lf\n",ret);
        
    }
    else//Иначе находим детерминант рекурсивно
    //через алгебраическое дополнение элемента
    {
        for(j = 0; j < m; j++)
        {
            _arr = M(m, 0, j, arr);
            ret += (A = (arr[0][j])*pow(-1,j)*Det(m - 1, _arr, iShowStepsOfCalcs));
            if(iShowStepsOfCalcs)
                printf("A[%02d][%02d] = %lf\n",1, j + 1,A);
            for(i = m - 2; 0 < i; i--)
                free((void *)_arr[i]);
            free((void *)_arr);
        }
    }
    return ret;
}
0
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 19:06  [ТС] #9
Не-не-не, я имею в виду не рекурсивное разложение по строке, а именно сумма всех комбинаций элементов, взятых по одному из каждого столбца и каждой строки.
0
Smetanka
56 / 17 / 1
Регистрация: 14.05.2012
Сообщений: 134
29.01.2013, 19:25 #10
Lexp, считая определитель как говорится "в лоб", или раскладывая по строкам - ты получишь одну и ту же сложность - O(n!)
Метод Гауса дает более лучший результат - O(n3)
Так что используй метод Гауса. Быстрее ну точно не придумаешь.
p.s. Есть алгоритмы,которые работают быстрее, но они быстрее лишь на ОООООЧЕЕЕНЬ больших матрицах
0
Kgfq
74 / 37 / 2
Регистрация: 23.09.2012
Сообщений: 408
29.01.2013, 19:30 #11
Можно программно посчитать какие на какие элементы нужно перемножить (в индексах), что бы получить определитель и сохранить в файлик. А потом из файлика считать и в цикле посчитать. Чем не вариант?
0
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 19:34  [ТС] #12
Цитата Сообщение от Smetanka Посмотреть сообщение
Lexp, считая определитель как говорится "в лоб", или раскладывая по строкам - ты получишь одну и ту же сложность - O(n!)
Метод Гауса дает более лучший результат - O(n3)
Так что используй метод Гауса. Быстрее ну точно не придумаешь.
p.s. Есть алгоритмы,которые работают быстрее, но они быстрее лишь на ОООООЧЕЕЕНЬ больших матрицах
Да, я тоже подумал, кол-во слагаемых будет как раз n!
Наверно тупо сделаю Гаусса и сравню с текущим алгоритмом.

Добавлено через 2 минуты
Цитата Сообщение от Kgfq Посмотреть сообщение
Можно программно посчитать какие на какие элементы нужно перемножить (в индексах), что бы получить определитель и сохранить в файлик. А потом из файлика считать и в цикле посчитать. Чем не вариант?
Вот это "программно посчитать" как раз в n! и выйдет...если я правильно вашу идею понял
0
Kgfq
74 / 37 / 2
Регистрация: 23.09.2012
Сообщений: 408
29.01.2013, 19:36 #13
Lexp, для матрицы 2x2 это было бы:

00 01
10 11

00 * 11 - 01 * 10
в индексах. Ну или еще можно попробовать упростить матрицу до того, что бы большинство оказалось нулями
0
Smetanka
56 / 17 / 1
Регистрация: 14.05.2012
Сообщений: 134
29.01.2013, 19:38 #14
Kgfq, это и есть определение определителя. Математики уже соптимизировали и доказали все что можно) Метод Гауса-самый быстрый и вменяемый метод(вплане алгоритма).
С другой стороны,как вариант, можно распараллелить данную программу-но это уже не оптимизация алгоритма,а оптимизация программы.

Добавлено через 1 минуту
Lexp, Гаусом не тупо, Гаусом правильно) Ты на верном пути! И поверь быстрее ты не придумаешь)))
1
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 19:38  [ТС] #15
Цитата Сообщение от Kgfq Посмотреть сообщение
Lexp, для матрицы 2x2 это было бы:

00 01
10 11

00 * 11 - 01 * 10
в индексах. Ну или еще можно попробовать упростить матрицу до того, что бы большинство оказалось нулями
Для матрицы 3х3 уже 6 слагаемых. И т.д.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.01.2013, 19:38
Привет! Вот еще темы с ответами:

Сделать класс для вычисления определителя - C++
как сделать чтобы было универсально ? xотя - бы до 5 пока только до этого додумался :) double SolveDeterm(int ** Elements,int...

Метод Гаусса для вычисления определителя - C++
Вычисляю обратную матрицу методом Гаусса. После приведения к верхнетреугольному виду считаю определитель, однако значение выдается...

Оптимизация алгоритма - C++
#include&lt;iostream&gt; #include&lt;stdlib.h&gt; #include&lt;time.h&gt; #include&lt;iomanip&gt; using namespace std; #define jaba for(i=0; i&lt;k; i++)...

Оптимизация алгоритма - C++
Условие: Дана выборка (X_i, Y_i)_{i=1}^N. Предполагается, что она была построена по следующему закону: \begin{cases} Y=\beta \xi...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
29.01.2013, 19:38
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru