Как через n-вложенный цикл посчитать умножение матриц за методом Шимбелла
У меня курсовая работа по программированию.Нужно реализовать на С++ или С# алгоритм Шимбелла ,применяя классы и графику.
Про программную реализацию этого метод в интернете почти ничего не нашел.Есть конечно какие-то наброски но так как я 2 курс плюс не очень понимаю программировании эти наброски мне ничего не дали.
Просьба если есть у кого-то реализация этого метода ,прошу помочь.Но если нет то объясните мне хотя бы как перемножить матрицы.
По методу нужно перемножать каждый элемент строки матрицы А на каждый элемент столбца матрицы В.
Умножение заменяем суммированием .
Пример:ищем 1 элемент матрицы С.
(a1.1+b1.1) (a1.2 +b2.1) (a1.3+b3.1) суммируем эти пары элементов и ищем минимальную суму которая заносится в новую матрицу C в эл. c1.1.
и так для всех остальных 8 эл.
a1.1 a1.2 a1.3
a2.1 a2.2 a2.3
a3.1 a3.2 a3.3
x
b1.1 b1.2 b1.3
b2.1 b2.2 b2.3
b3.1 b3.2 b3.3
Про программную реализацию этого метод в интернете почти ничего не нашел.Есть конечно какие-то наброски но так как я 2 курс плюс не очень понимаю программировании эти наброски мне ничего не дали.
Просьба если есть у кого-то реализация этого метода ,прошу помочь.Но если нет то объясните мне хотя бы как перемножить матрицы.
По методу нужно перемножать каждый элемент строки матрицы А на каждый элемент столбца матрицы В.
Умножение заменяем суммированием .
Пример:ищем 1 элемент матрицы С.
(a1.1+b1.1) (a1.2 +b2.1) (a1.3+b3.1) суммируем эти пары элементов и ищем минимальную суму которая заносится в новую матрицу C в эл. c1.1.
и так для всех остальных 8 эл.
a1.1 a1.2 a1.3
a2.1 a2.2 a2.3
a3.1 a3.2 a3.3
x
b1.1 b1.2 b1.3
b2.1 b2.2 b2.3
b3.1 b3.2 b3.3
Строку умножаешь на столбец подобно скалярному произведению векторов (в школе должны были объяснять), т.е. вычисляешь скалярное произведение вектор-строки первой матрицы на вектор-столбец второй матрицы. Результат - элемент результирующей матрицы с индексами [номер строки, номер столбца] исходных. Например, для матриц 3x3:
c[1,1] = a[1,1]*b[1,1] + a[1,2] *b[2,1] + a[1,3]*b[3,1]
остальные 8 аналогично.
В общем случае длина строк первой матрицы должна быть равна длине столбцов второй.
Так в математике (линейная алгебра). См. здесь. В методе возможно имеется ввиду что-то другое, какое-нибудь псевдоумножение.
Умножение по методу Шимбелла не такое, как в линейной алгебре.
Ниже написан код для вычисления одного элемента произведения с индексами i и k.
Нулевые элементы матриц обрабатываются особым образом, поскольку в этом случае в теории графов обычно имеют в виду не нулевой, а бесконечно большой вес ребра. Вы, вроде, должны немножко представлять, зачем это нужно.
Ниже написан код для вычисления одного элемента произведения с индексами i и k.
Нулевые элементы матриц обрабатываются особым образом, поскольку в этом случае в теории графов обычно имеют в виду не нулевой, а бесконечно большой вес ребра. Вы, вроде, должны немножко представлять, зачем это нужно.
Код:
double minsum = Double.MaxValue; // любая допустимая сумма будет меньше этой величины
for (j = 0; j < m; ++j) // перебираем элементы, как при обычном перемножении матриц
{
if ((a[i][j] != 0.0) && (b[j][k] != 0.0)) // суммы с хотя бы одним нулём пропускаются
minsum = Math.Min(minsum, a[i][j] + b[j][k]); // ищем минимальную сумму
}
c[i][k] = (minsum == Double.MaxValue) ? 0.0 : minsum; // если ни одной допустимой суммы не найдено, то пишем 0
for (j = 0; j < m; ++j) // перебираем элементы, как при обычном перемножении матриц
{
if ((a[i][j] != 0.0) && (b[j][k] != 0.0)) // суммы с хотя бы одним нулём пропускаются
minsum = Math.Min(minsum, a[i][j] + b[j][k]); // ищем минимальную сумму
}
c[i][k] = (minsum == Double.MaxValue) ? 0.0 : minsum; // если ни одной допустимой суммы не найдено, то пишем 0