یکی از الگوریتم هایی که با استفاده از روش تقسیم و حل کار می کنه روش ضرب ماتریس ها به روش استراسن هستش .شاید مطالب زیادی در مورد این الگوریتم خونده باشید اما بد نیست کد سی شارپ مربوط به این الگوریتم رو هم ببینید .کل الگوریتم شاید به نظر پیچیده بیاد ولی وقتی با دقت به اجزای اون نگاه کنید متوجه میشید که هر کدوم از اجزا خیلی ساده هستند :
using System;
class Program
{
static void Main(string[] args)
{
}
static void Display(int[,] arr)
{
for (int i = 0; i < arr.GetLength(0); i++)
{
for (int j = 0; j < arr.GetLength(1); j++)
Console.Write(" {0} ", arr[i, j]);
Console.WriteLine();
}
}
static int[,] Add(int[,] A, int[,] B)
{
int[,] AB = (int[,])A.Clone();
for (int i = 0; i < AB.GetLength(0); i++)
for (int j = 0; j < AB.GetLength(1); j++)
AB[i, j] += B[i, j];
return AB;
}
static int[,] Subtract(int[,] A, int[,] B)
{
int[,] AB = (int[,])A.Clone();
for (int i = 0; i < AB.GetLength(0); i++)
for (int j = 0; j < AB.GetLength(1); j++)
AB[i, j] -= B[i, j];
return AB;
}
static int[,] Multiply(int[,] A, int[,] B)
{
int length = A.GetLength(0);
int[,] answer;
answer = new int[length, length];
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++)
{
int sum = 0;
for (int k = 0; k < length; k++)
sum += A[i, k] * B[k, j];
answer[i, j] = sum;
}
return answer;
}
/*
*
* A11 A12
* A21 A22
*
*
*/
static void Divide(int[,] Big, ref int[,] S11, ref int[,] S12, ref int[,] S21, ref int[,] S22)
{
int length = Big.GetLength(0);
int MidIndex = length / 2;
S11 = new int[MidIndex, MidIndex];
S12 = new int[MidIndex, MidIndex];
S21 = new int[MidIndex, MidIndex];
S22 = new int[MidIndex, MidIndex];
for (int i = 0; i < length; i++)//Traversing Rows
for (int j = 0; j < length; j++)//Traversing Columns
//Detecting Position
if (i >= 0 && i < MidIndex) //left Side
if (j >= 0 && j < MidIndex)//Top Side
S11[i, j] = Big[i, j];
else//Bottom Side
S21[i, j - MidIndex] = Big[i, j];
else//Right Side
if (j >= 0 && j < MidIndex)//Top Side
S12[i - MidIndex, j] = Big[i, j];
else//Bottom Side
S22[i - MidIndex, j - MidIndex] = Big[i, j];
}
/*
*
* A11 A12
* A21 A22
*
*
*/
static int[,] Putting_Together(int[,] A11, int[,] A21, int[,] A12, int[,] A22)
{
int MidIndex = A11.GetLength(0);
int length = 2 * MidIndex;
int[,] A = new int[length, length];
for (int i = 0; i < length; i++)//Traversing Rows
for (int j = 0; j < length; j++)//Traversing Columns
//Detecting Position
if (i >= 0 && i < MidIndex) //left Side
if (j >= 0 && j < MidIndex)//Top Side
A[i, j] = A11[i, j];
else//Bottom Side
A[i, j] = A12[i, j - MidIndex];
else//Right Side
if (j >= 0 && j < MidIndex)//Top Side
A[i, j] = A21[i - MidIndex, j];
else//Bottom Side
A[i, j] = A22[i - MidIndex, j - MidIndex];
return A;
}
static int[,] Strassen(int[,] A, int[,] B)
{
int length = A.GetLength(0);
int[,] answer;
if (length > 8)//Using Strassen for Big Matris
{
int[,] A11 = null, A12 = null, A21 = null, A22 = null;
int[,] B11 = null, B12 = null, B21 = null, B22 = null;
Divide(A, ref A11, ref A21, ref A12, ref A22);
Divide(B, ref B11, ref B21, ref B12, ref B22);
//m1 = (A11 + A22)(B11 + B22)
int[,] M1 = Strassen(Add(A11, A22), Add(B11, B22));
//m2 = (A21,A22) * B11
int[,] M2 = Strassen(Add(A21, A22), B11);
//m3 = A11 * (B12-B22)
int[,] M3 = Strassen(A11, Subtract(B12, B22));
//m4 = A22 * (B21-B11)
int[,] M4 = Strassen(A22, Subtract(B21, B11));
//m5 = (A11 + A12) * B22
int[,] M5 = Strassen(Add(A11, A12), B22);
//m6 = (A21 - A11) * (B11 + B12)
int[,] M6 = Strassen(Subtract(A21, A11), Add(B11, B12));
//m7 = (A12 - A22) * (B21 + B22)
int[,] M7 = Strassen(Subtract(A12, A22), Add(B21, B22));
int[,] C11, C12, C21, C22;
C11 = Add(Subtract(Add(M1, M4), M5), M7);
C12 = Add(M3, M5);
C21 = Add(M2, M4);
C22 = Add(Subtract(M1, M2), Add(M3, M6));
answer = Putting_Together(C11, C21, C12, C22);
}
else//Normal Mulipulation
answer = Multiply(A, B);
return answer;
}
static int[,] CreateSamleMatrix(int k)
{
int dim = (int)Math.Pow(2, k);
int[,] sample = new int[dim, dim];
Random r = new Random();
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++)
sample[i, j] = r.Next(11, 33);
return sample;
}
}
1- متد نمایش ماتریس یا Display :
این متد یک آرایه دو بعدی از ورودی دریافت می کند و آن را روی صفحه نمایش میدهد .
شیوه ی عملکرد آن هم خیلی ساده است فقط از دو تا حلقه For ساخته شده که تمام سطر ها و ستون های ماتریس یا همون آرایه دو بعدی رو پیمایش می کنه و عناصر رو تک تک روی صفحه چاپ می کنه .
static void Display(int[,] arr)
{
for (int i = 0; i < arr.GetLength(0); i++)
{
for (int j = 0; j < arr.GetLength(1); j++)
Console.Write(" {0} ", arr[i, j]);
Console.WriteLine();
}
}
2-متد جمع کردن دو ماتریس یا Add :
دو تا ماتریس به عنوان پارامتر ورودی دریافت می کند و آن دو را با هم جمع کرده و پاسخ را return می کند .
static int[,] Add(int[,] A, int[,] B)
{
int[,] AB = (int[,])A.Clone();
for (int i = 0; i < AB.GetLength(0); i++)
for (int j = 0; j < AB.GetLength(1); j++)
AB[i, j] += B[i, j];
return AB;
}
3-متد تفریق کردن دو ماتریس از هم یا Subtract :
این متد دو ماتریس به عنوان پارامتر وردی دریافت می کند و آن دو را از هم تفریق کرده و در نهایت پاسخ را return می کند .
static int[,] Subtract(int[,] A, int[,] B)
{
int[,] AB = (int[,])A.Clone();
for (int i = 0; i < AB.GetLength(0); i++)
for (int j = 0; j < AB.GetLength(1); j++)
AB[i, j] -= B[i, j];
return AB;
}
4-متد ضرب کردن دو ماتریس در هم به روش معمولی یا Multiply :
این متد دو تا آرایه ی دو بعدی (یا ماتریس) از ورودی دریافت می کند و با استفاده از سه تا حلقه ی For مرتبه زمانی O(n3)d در هم ضرب می کند .الگوریتم استراسن وقتی به ماتریس های کوچک تر از 23 برسه به جای فراخوانی خودش این متد رو فراخوانی می کنه .
static int[,] Multiply(int[,] A, int[,] B)
{
int length = A.GetLength(0);
int[,] answer;
answer = new int[length, length];
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++)
{
int sum = 0;
for (int k = 0; k < length; k++)
sum += A[i, k] * B[k, j];
answer[i, j] = sum;
}
return answer;
}
5-متدی که یک آرایه را به چهار قسمت تقسیم می کند یا Divide :
تمام الگوریتم های تقسیم و غبله یک قسمتی تحت عنوان Divide دارند که ورودی رو به قسمت های کوچکتر تقسیم می کند .همون طور که می دونید الگوریتم استراسن در حین انجام محاسبات یک ماتریس رو به چهار ماتریس تبدیل می کند .یعنی یک ماتریس 2k × 2k را تبدیل می کند به چهار ماتریس 2k-1 × 2k-1 و با استفاده از یک سری فرمول کارش رو ادامه میده .این متد یک آرایه ی دو بعدی به نام Big دریافت می کند و چهار تا آرایه ی s11 ,s12,s21,s22 رو که چهار تا ماتریس کوچکتر هستند بعد از استخراج از داخل ماتریس Big با استفاده از پارامتر های ref بر میگرداند .
توی این شکل یک مثال از نحوه ی تقسیم به چهار کردن ماتریس می تونید مشاهده کنید :
%EA%B7%B8%EB%A6%BC5.jpg
/*
*
* A11 A12
* A21 A22
*
*
*/
static void Divide(int[,] Big, ref int[,] S11, ref int[,] S12, ref int[,] S21, ref int[,] S22)
{
int length = Big.GetLength(0);
int MidIndex = length / 2;
S11 = new int[MidIndex, MidIndex];
S12 = new int[MidIndex, MidIndex];
S21 = new int[MidIndex, MidIndex];
S22 = new int[MidIndex, MidIndex];
for (int i = 0; i < length; i++)//Traversing Rows
for (int j = 0; j < length; j++)//Traversing Columns
//Detecting Position
if (i >= 0 && i < MidIndex) //left Side
if (j >= 0 && j < MidIndex)//Top Side
S11[i, j] = Big[i, j];
else//Bottom Side
S21[i, j - MidIndex] = Big[i, j];
else//Right Side
if (j >= 0 && j < MidIndex)//Top Side
S12[i - MidIndex, j] = Big[i, j];
else//Bottom Side
S22[i - MidIndex, j - MidIndex] = Big[i, j];
}
6- متدی که با در کنار هم قرار دادن چهار ماتریس کوچک یک ماتریس بزرگ درست می کند یا Putting_Together :
این متد درست بر عکس متد بالا عمل می کند و چهار ماتریس کوچک یعنی چهار ماتریس 2k-1 × 2k-1 رو در کنار هم قرار میدهد و یک ماتریس بزرگ یعنی 2k × 2k ایجاد می کند و در نهایت آن را return می کند .
این دو متد به همراه متد های جمع و تفریق و ضرب در عملیات مربوط به استراسن استفاده می شوند .
/*
*
* A11 A12
* A21 A22
*
*
*/
static int[,] Putting_Together(int[,] A11, int[,] A21, int[,] A12, int[,] A22)
{
int MidIndex = A11.GetLength(0);
int length = 2 * MidIndex;
int[,] A = new int[length, length];
for (int i = 0; i < length; i++)//Traversing Rows
for (int j = 0; j < length; j++)//Traversing Columns
//Detecting Position
if (i >= 0 && i < MidIndex) //left Side
if (j >= 0 && j < MidIndex)//Top Side
A[i, j] = A11[i, j];
else//Bottom Side
A[i, j] = A12[i, j - MidIndex];
else//Right Side
if (j >= 0 && j < MidIndex)//Top Side
A[i, j] = A21[i - MidIndex, j];
else//Bottom Side
A[i, j] = A22[i - MidIndex, j - MidIndex];
return A;
}
7-خود متد استراسن که با استفاده از متد های 2 تا 6 حاصل ضرب دو ماتریس بسیار بزرگ رو برای ما به دست میاره .
این متد از بخش های زیر تشکیل شده :
بخش اول :
int length = A.GetLength(0);
int[,] answer;
if (length > 8)//Using Strassen for Big Matris
توی خط اول اندازه ماتریس ورودی رو داخل length قرار دادیم . توی خط دوم یک آرایه دو بعدی درست کردیم که قرار هست بعدا جواب داخلش قرار بگیره .
و توی خط سوم بررسی کردیم اگر اندازه ی ماتریس ورودی از 23 بزرگتر است اون رو با روش استراسن حساب کنیم در غیر این صورت قسمت else اجرا میشه و با روش معمولی محاسبه می شه .
بخش دوم :
اگر ماتریس های ورودی بزرگتر از 23 بودند باید عملیات استراسن روی اون ها انجام بشه برایا اینکار اول از همه باید هر کدوم از ماتریس ها به چهار ماتریس کوچیک تر تبدیل بشند که زحمت این کار به عهده ی متد Divide هستش :
int[,] A11 = null, A12 = null, A21 = null, A22 = null;
int[,] B11 = null, B12 = null, B21 = null, B22 = null;
Divide(A, ref A11, ref A21, ref A12, ref A22);
Divide(B, ref B11, ref B21, ref B12, ref B22);
بخش سوم :
استراسن یک سری فرمول داره که با استفاده از اون ها یک سری ماتریس دیگه میسازه بعد اون ماتریس ها رو کنار هم قرار میده تا در نهایت جواب بدست بیاد توی این قسمت ما اون چهار تا ماتریس نهائی رو حساب کردیم یعنی C11 C12 C21 C22 به شکل زیر :
//m1 = (A11 + A22)(B11 + B22)
int[,] M1 = Strassen(Add(A11, A22), Add(B11, B22));
//m2 = (A21,A22) * B11
int[,] M2 = Strassen(Add(A21, A22), B11);
//m3 = A11 * (B12-B22)
int[,] M3 = Strassen(A11, Subtract(B12, B22));
//m4 = A22 * (B21-B11)
int[,] M4 = Strassen(A22, Subtract(B21, B11));
//m5 = (A11 + A12) * B22
int[,] M5 = Strassen(Add(A11, A12), B22);
//m6 = (A21 - A11) * (B11 + B12)
int[,] M6 = Strassen(Subtract(A21, A11), Add(B11, B12));
//m7 = (A12 - A22) * (B21 + B22)
int[,] M7 = Strassen(Subtract(A12, A22), Add(B21, B22));
int[,] C11, C12, C21, C22;
C11 = Add(Subtract(Add(M1, M4), M5), M7);
C12 = Add(M3, M5);
C21 = Add(M2, M4);
C22 = Add(Subtract(M1, M2), Add(M3, M6));
بخش چهارم :
حالا که جواب ماتریس های C رو داریم میتونیم با استفاده از متد Putting_Together به شکل زیر ماتریس جواب رو به دست بیاریم :
answer = Putting_Together(C11, C21, C12, C22);
اون قسمت Else که بعد از این هست مربوط به همون if اول متده یعنی اگر ماتریس های ورودی از 8 در 8 کوچیکتر بودند با روش معمولی محاسبه انجام میشه .
8-متد تولید ماتریس نمونه برای تست کردن برنامه :
قطعا اگر بخوایم این برنامه رو تست کنیم باید ماتریس های بزرگی برای این کار داشته باشیم این متد زحمت میکشه و با استفاده از اعداد رندم به ما ماتریس هایی به بزرگی 2k میده .که k رو هم از پارامتر های ورودی دریافت می کنه .
خیلی طولانی بود امیدوارم مفید هم باشه .
محیط بهتر ، آموزش بهتر
نمایش نتایج: از شماره 1 تا 3 , از مجموع 3
-
11-09-2012, 02:08 PM #1مدیرکل
- تاریخ عضویت
- Nov 2011
- نوشته ها
- 554
- تشکر
- 617
- تشکر شده 529 بار در 302 ارسال
کد سی شارپ الگوریتم استراسن برای ضرب ماتریس های مربعی در هم به صورت غیر شی گرا
به یک دوست جهت انجام امور طراحی وب سایت نیاز دارم .
آموزش از من
همراهی و کمک از شما
3 کاربر مقابل از Mahdi عزیز به خاطر این پست مفید تشکر کرده اند.
mahan (11-12-2012), miss parisa (12-06-2012), mountainous (11-28-2012)
-
12-06-2012, 01:11 AM #2مدیر
- تاریخ عضویت
- Oct 2012
- نوشته ها
- 121
- تشکر
- 121
- تشکر شده 152 بار در 112 ارسال
درس طراحی الگوریتم را هنوز برنداشتم.باطر همین وقتی کد را یک دور خوندم سرم گیج رفت!!!
شوخی کردم یه چیزایی (با دید برنامه نویسی که بهش نگاه کردم) فهمیدم.
ایشالا طراحی الگوریتم برداشتم حتما دوباره میام به این صفحه سری میزنم.
گــر نشان زندگی جنبدگیست / خار در صحرا سراسر زندگیست
هم جُـــعل زنده است و هم پروانه/ فــــرقـها از زندگی تا زندگیـــست
کاربر مقابل از miss parisa عزیز به خاطر این پست مفید تشکر کرده است:
Mahdi (12-06-2012)
-
01-17-2013, 08:34 PM #3مدیرکل
- تاریخ عضویت
- Nov 2011
- نوشته ها
- 554
- تشکر
- 617
- تشکر شده 529 بار در 302 ارسال
یک مثال از نحوه ی عملکرد این الگوریتم با استفاده از کد بالا :
using System;
class Program
{
static void Main(string[] args)
{
****//Creating Sample Matrix
int[,] m1 = CreateSamleMatrix(4);//Matrix 16 * 16
****int[,] m2 = CreateSamleMatrix(4);//Matrix 16 * 16
****
****//Displaying Sample Matrix
****Console.WriteLine("Matrix 1 : ");
****Display(m1);
****Console.WriteLine("Matrix 2 : ");
****Display(m2);
****
****//Calculating Muliply with Standard Method (using Three nested for loop)
****int[,] StandardAnswer = Multiply(m1,m2);
****//Displaying Answer of Standard Method
****Display(StandardAnswer);
****//Calculating Muliply with Strassen Method
****int[,] StrassenAnswer = Strassen(m1,m2);
****//Displaying Answer of Strassen Method
****Display(StrassenAnswer);
****//Finish
****Console.Write("Press Any Key To Close.....");
****Console.ReadKey();
}
static void Display(int[,] arr)
{
for (int i = 0; i < arr.GetLength(0); i++)
{
for (int j = 0; j < arr.GetLength(1); j++)
Console.Write(" {0} ", arr[i, j]);
Console.WriteLine();
}
}
static int[,] Add(int[,] A, int[,] B)
{
int[,] AB = (int[,])A.Clone();
for (int i = 0; i < AB.GetLength(0); i++)
for (int j = 0; j < AB.GetLength(1); j++)
AB[i, j] += B[i, j];
return AB;
}
static int[,] Subtract(int[,] A, int[,] B)
{
int[,] AB = (int[,])A.Clone();
for (int i = 0; i < AB.GetLength(0); i++)
for (int j = 0; j < AB.GetLength(1); j++)
AB[i, j] -= B[i, j];
return AB;
}
static int[,] Multiply(int[,] A, int[,] B)
{
int length = A.GetLength(0);
int[,] answer;
answer = new int[length, length];
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++)
{
int sum = 0;
for (int k = 0; k < length; k++)
sum += A[i, k] * B[k, j];
answer[i, j] = sum;
}
return answer;
}
/*
*
* A11 A12
* A21 A22
*
*
*/
static void Divide(int[,] Big, ref int[,] S11, ref int[,] S12, ref int[,] S21, ref int[,] S22)
{
int length = Big.GetLength(0);
int MidIndex = length / 2;
S11 = new int[MidIndex, MidIndex];
S12 = new int[MidIndex, MidIndex];
S21 = new int[MidIndex, MidIndex];
S22 = new int[MidIndex, MidIndex];
for (int i = 0; i < length; i++)//Traversing Rows
for (int j = 0; j < length; j++)//Traversing Columns
//Detecting Position
if (i >= 0 && i < MidIndex) //left Side
if (j >= 0 && j < MidIndex)//Top Side
S11[i, j] = Big[i, j];
else//Bottom Side
S21[i, j - MidIndex] = Big[i, j];
else//Right Side
if (j >= 0 && j < MidIndex)//Top Side
S12[i - MidIndex, j] = Big[i, j];
else//Bottom Side
S22[i - MidIndex, j - MidIndex] = Big[i, j];
}
/*
*
* A11 A12
* A21 A22
*
*
*/
static int[,] Putting_Together(int[,] A11, int[,] A21, int[,] A12, int[,] A22)
{
int MidIndex = A11.GetLength(0);
int length = 2 * MidIndex;
int[,] A = new int[length, length];
for (int i = 0; i < length; i++)//Traversing Rows
for (int j = 0; j < length; j++)//Traversing Columns
//Detecting Position
if (i >= 0 && i < MidIndex) //left Side
if (j >= 0 && j < MidIndex)//Top Side
A[i, j] = A11[i, j];
else//Bottom Side
A[i, j] = A12[i, j - MidIndex];
else//Right Side
if (j >= 0 && j < MidIndex)//Top Side
A[i, j] = A21[i - MidIndex, j];
else//Bottom Side
A[i, j] = A22[i - MidIndex, j - MidIndex];
return A;
}
static int[,] Strassen(int[,] A, int[,] B)
{
int length = A.GetLength(0);
int[,] answer;
if (length > 8)//Using Strassen for Big Matris
{
int[,] A11 = null, A12 = null, A21 = null, A22 = null;
int[,] B11 = null, B12 = null, B21 = null, B22 = null;
Divide(A, ref A11, ref A21, ref A12, ref A22);
Divide(B, ref B11, ref B21, ref B12, ref B22);
//m1 = (A11 + A22)(B11 + B22)
int[,] M1 = Strassen(Add(A11, A22), Add(B11, B22));
//m2 = (A21,A22) * B11
int[,] M2 = Strassen(Add(A21, A22), B11);
//m3 = A11 * (B12-B22)
int[,] M3 = Strassen(A11, Subtract(B12, B22));
//m4 = A22 * (B21-B11)
int[,] M4 = Strassen(A22, Subtract(B21, B11));
//m5 = (A11 + A12) * B22
int[,] M5 = Strassen(Add(A11, A12), B22);
//m6 = (A21 - A11) * (B11 + B12)
int[,] M6 = Strassen(Subtract(A21, A11), Add(B11, B12));
//m7 = (A12 - A22) * (B21 + B22)
int[,] M7 = Strassen(Subtract(A12, A22), Add(B21, B22));
int[,] C11, C12, C21, C22;
C11 = Add(Subtract(Add(M1, M4), M5), M7);
C12 = Add(M3, M5);
C21 = Add(M2, M4);
C22 = Add(Subtract(M1, M2), Add(M3, M6));
answer = Putting_Together(C11, C21, C12, C22);
}
else//Normal Mulipulation
answer = Multiply(A, B);
return answer;
}
static int[,] CreateSamleMatrix(int k)
{
int dim = (int)Math.Pow(2, k);
int[,] sample = new int[dim, dim];
Random r = new Random();
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++)
sample[i, j] = r.Next(11, 33);
return sample;
}
}
به یک دوست جهت انجام امور طراحی وب سایت نیاز دارم .
آموزش از من
همراهی و کمک از شما
کاربر مقابل از Mahdi عزیز به خاطر این پست مفید تشکر کرده است:
zare69 (01-18-2013)
پاسخ با نقل قول
کلمات کلیدی این موضوع
مجوز های ارسال و ویرایش
- شما نمیتوانید موضوع جدیدی ارسال کنید
- شما امکان ارسال پاسخ را ندارید
- شما نمیتوانید فایل پیوست کنید.
- شما نمیتوانید پست های خود را ویرایش کنید