# مهندسی نرم افزار > مباحث مرتبط با مهندسی نرم‌افزار > الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها >  ضرب ماتریس اسپارس

## zeinab03

سلام دوستان عزیز
اگه ممکنه الگوریتم ضرب دو ماتریس اسپارس رو توضیح بدین..ممنون :چشمک:

----------


## yoosof_145

ماتریس اسپارسو واسم تعریف کن تا الگوریتمش رو بتونم بگم.

_==============
اخوی فارسی تایپ کن 
وگرنه دفعه بعد طبق مقررات پستت حذف میشه.
ممنون

سپیدار_

----------


## Golden Galaxy

سلام دوست عزیز 
در ماتریس های اسپارس همانطور که می دانید تعداد خانه های صفر ( یک مدل ) زیاد است پس صرفه به استفاده از روش معمولی نیست . 
حتما با روش ذخیره سازی این نوع ماتریس ها آشنا هستید .
باید در هر مرحله عنصر k ام سطر i ام از ماتریس اول را در عنصر k ام از ستون j ام از ماتریس دوم را در هم ضرب کرد و حاصل را به عنوان عنصر در مکان i , j از ماتریس سوم قرار داد .
نکته مهم این است که حاصل ضرب دو ماتریس اسپارس حتما یک ماتریس اسپارس نخواهد بود .
عمل بالا را می توان با سه حلقه for تو در تو پیاده سازی کرد و برای جستجو هم از جستجوی خطی ساده استفاده کرد .
برای اطلاعات بیشتر : کتاب ساختمان داده ها در ++ C مهندس جعفر نژاد قمی

----------


## اَرژنگ

> matrise spars ro baram tarif kon ta algoritmesho behetun begam


http://www.nist.gov/dads/HTML/sparsematrix.html

----------


## bahman_asham

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int **arr,**bb,*t,*p;
int main()
 { clrscr();
  int i,j,x,y,a=2,b=1,z=0,u=3;
  cout<<"enter x:";
  cin>>x;
  cout<<"enter y:";
  cin>>y;
    p=(int *)malloc(sizeof(int)* x);
    for(i=1;i<=x;i++)
     arr[i]=(int *)malloc(y * sizeof(int));
    for(i=1;i<=x;i++)
     for(j=1;j<=y;j++)
     {
     cout<<"enter arr["<<i<<"]["<<j<<"]=";
     cin>>arr[i][j];
     }
     for(i=1;i<=x;i++)
     for(j=1;j<=y;j++)
      if(arr[i][j]!=0 )z++;
    t=(int *)malloc(u * sizeof(int));
     for(i=1;i<x;i++)
     bb[i]=(int *) malloc(z * sizeof(int));

    bb[1][1]=x;
    bb[1][2]=y;
    bb[1][3]=z;
     for(i=1;i<=x;i++)
      for(j=1;j<=y;j++)
        if(arr[i][j]!=0)
        {
          bb[a][b]=i;
          b++;
          bb[a][b]=j;
          b++;
          bb[a][b]=arr[i][j];
          b=1;
          a++;
        }
        for(i=1;i<=(z+1);i++)
         for(j=1;j<=3;j++)
         {
          cout<<bb[i][j];
          if (j==3)
          cout<<endl;
          }
      getch();
      return 0;
  }

----------


## Sepidar

اگه مطمئن بودم برای پروژه دانشجویی ازشون استفاده نمیشه، کتابخانه های ماتریسم رو رو سایت آپلود میکردم...

ضرب ماتریس اسپارس هیچ فرقی با ضرب ماتریس های معمولی نداره. تنها تفاوت در روش ذخیره سازی این ماتریسهاست. اینجا میتونین یه سری از روشهای معروف ذخیره سازی این ماتریس رو ببینین. اگر چه من خودم از هیچکدوم از روشهای اون مقاله استفاده نمیکنم و عوضش از یه درخت برای نگهداری ساختار این ماتریسها استفاده میکنم.

----------


## kh1387

میشه کسی طریقه ضرب رو توضیح بده؟
متشکرم

----------


## saba_v

سلام 
برای ضرب دو ماتریس اسپارس باید ماتریس دومی را ترانهاده اش را بدست آورد و سپس در ماتریس اول ضرب کرد. همان طور که برای جمع دو ماتریس اسپارس باید 2 ماتریس را ترانهاده آنها را بدست آورد و سپس جمع کرد .

----------


## h_math

سلام
دوست عزيز آقای bahman_asham ممنون از برنامه ضرب ماتریس اسپارس
متاسفانه من آشنایی کاملی به دستورات حرفه ای زبان C ندارم و از این الگوریتم های طولانی چیزی سردر نمیارم
ممنون میشم اگه سطر چهارم از برنامه یعنی int **arr,**bb,*t,*p رو برام توضیح بدین نفهمیدم چی تعریف کردین؟
فقط من تا 2روز وقت دارم اینو بفهمم
ممنونم اگه زود...

----------


## csharpprogramer88

> نکته مهم این است که حاصل ضرب دو ماتریس اسپارس حتما یک ماتریس اسپارس نخواهد بود .
> عمل بالا را می توان با سه حلقه for تو در تو پیاده سازی کرد و برای جستجو هم از جستجوی خطی ساده استفاده کرد .
> برای اطلاعات بیشتر : کتاب ساختمان داده ها در ++ C مهندس جعفر نژاد قمی


 سلام

دوست عزیز لطفا در این باره برام توضیح بدید و یک مثال هم بگید 
در باره حاصل جمع هم حرف شما صادقه؟

----------


## soorena

> اگه مطمئن بودم برای پروژه دانشجویی ازشون استفاده نمیشه، کتابخانه های ماتریسم رو رو سایت آپلود میکردم...


هر کی ندونه فکر ميکنه طرف يه کتابخونه پيچيده نوشته که الان ناسا هم برای پرتاب موشک جديدش داره ازش استفاده ميکنه.....
بابا تو خيلی خيلی ... خفنی.....خفن....خوف....خف..

----------


## amir_saniyan

این هم ماتریس اسپارس که خودم نوشتم :)

#include <cstdlib>
#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;
template <class T>
class sparse_matrix_element
{
public:
 sparse_matrix_element(int _row, int _column, T _value)
 {
  if(_row < 0)
  {
   throw invalid_argument("_row");
  }
  if(_column < 0)
  {
   throw invalid_argument("_column");
  }
  m_row = _row;
  m_column = _column;
  m_value = _value;
 }
 int row(void) const
 {
  return m_row;
 }
 int column(void) const
 {
  return m_column;
 }
 T value(void) const
 {
  return m_value;
 }
 void value(T _val)
 {
  m_value = _val;
  return;
 }
private:
 int m_row;
 int m_column;
 T m_value;
};
template <class T>
class sparse_matrix
{
public:
 sparse_matrix(int _rows_length, int _columns_length)
 {
  if(_rows_length <= 0)
  {
   throw invalid_argument("_rows_length");
  }
  if(_columns_length <= 0)
  {
   throw invalid_argument("_columns_length");
  }
  m_rows_length = _rows_length;
  m_columns_length = _columns_length;
 }
 int rows_length(void) const
 {
  return m_rows_length;
 }
 int columns_length(void) const
 {
  return m_columns_length;
 }
 T element(int _row, int _column) const
 {
  if(_row < 0 || _row >= m_rows_length)
  {
   throw invalid_argument("_row");
  }
  if(_column < 0 || _column >= m_columns_length)
  {
   throw invalid_argument("_column");
  }
  for(vector<sparse_matrix_element<T>>::size_type i = 0; i < m_elements.size(); i++)
  {
   if(m_elements[i].row() == _row && m_elements[i].column() == _column)
   {
    return m_elements[i].value();
   }
  }
  return 0;
 }
 void element(int _row, int _column, T _value)
 {
  if(_row < 0 || _row >= m_rows_length)
  {
   throw invalid_argument("_row");
  }
  if(_column < 0 || _column >= m_columns_length)
  {
   throw invalid_argument("_column");
  }
  for(vector<sparse_matrix_element<T>>::size_type i = 0; i < m_elements.size(); i++)
  {
   if(m_elements[i].row() == _row && m_elements[i].column() == _column)
   {
    if(_value != 0)
    {
     m_elements[i].value(_value);
    }
    else
    {
     m_elements.erase(m_elements.begin() + i);
    }
    return;
   }
  }
  if(_value != 0)
  {
   sparse_matrix_element<T> element(_row, _column, _value);
   m_elements.push_back(element);
  }
  return;
 }
 sparse_matrix<T> transpose(void) const
 {
  sparse_matrix<T> result(columns_length(), rows_length());
  for(int row = 0; row < rows_length(); row++)
  {
   for(int column = 0; column < columns_length(); column++)
   {
    T e = element(row, column);
    result.element(column, row, e);
   }
  }
  return result;
 }
 sparse_matrix<T> add(const sparse_matrix& _matrix) const
 {
  if(rows_length() != _matrix.rows_length() || columns_length() != _matrix.columns_length())
  {
   throw logic_error("Matrices of the same size can be added or subtracted.");
  }
  sparse_matrix<T> result(rows_length(), columns_length());
  for(int row = 0; row < rows_length(); row++)
  {
   for(int column = 0; column < columns_length(); column++)
   {
    T element1 = element(row, column);
    T element2 = _matrix.element(row, column);
    T sum = element1 + element2;
    result.element(row, column, sum);
   }
  }
  return result;
 }
 sparse_matrix<T> subtract(const sparse_matrix& _matrix) const
 {
  if(rows_length() != _matrix.rows_length() || columns_length() != _matrix.columns_length())
  {
   throw logic_error("Matrices of the same size can be added or subtracted.");
  }
  sparse_matrix<T> result(rows_length(), columns_length());
  for(int row = 0; row < rows_length(); row++)
  {
   for(int column = 0; column < columns_length(); column++)
   {
    T element1 = element(row, column);
    T element2 = _matrix.element(row, column);
    T sum = element1 - element2;
    result.element(row, column, sum);
   }
  }
  return result;
 }
 sparse_matrix<T> scalar_multiply(T _x) const
 {
  sparse_matrix<T> result(rows_length(), columns_length());
  for(int row = 0; row < rows_length(); row++)
  {
   for(int column = 0; column < columns_length(); column++)
   {
    T e = _x * element(row, column);
    result.element(row, column, e);
   }
  }
  return result;
 }
 sparse_matrix<T> multiply(const sparse_matrix& _matrix) const
 {
  if(columns_length() != _matrix.rows_length())
  {
   throw logic_error("Two matrices can be multiplied only when the number of columns in the first equals the number of rows in the second.");
  }
  sparse_matrix<T> result(rows_length(), _matrix.columns_length());
  for(int row = 0; row < rows_length(); row++)
  {
   for(int column = 0; column < _matrix.columns_length(); column++)
   {
    T sum = 0;
    for(int i = 0; i < columns_length(); i++)
    {
     T element1 = element(row, i);
     T element2 = _matrix.element(i, column);
     sum += element1 * element2;
    }
    result.element(row, column, sum);
   }
  }
  return result;
 }
private:
 int m_rows_length;
 int m_columns_length;
 vector<sparse_matrix_element<T>> m_elements;
};
template <class T>
sparse_matrix<T> read_sparse_matrix(void)
{
 int rows_length;
 cout << "Please enter rows length (eg. 10): ";
 cin >> rows_length;
 int columns_length;
 cout << "Please enter columns length (eg. 15): ";
 cin >> columns_length;
 sparse_matrix<T> matrix(rows_length, columns_length);
 while(true)
 {
  char confirm;
  cout << "Do you want to enter an element? [y|n]: ";
  cin >> confirm;
  if(confirm != 'y' && confirm != 'Y')
  {
   break;
  }
  int row;
  cout << "Please enter zero base row (eg. 5): ";
  cin >> row;
  int column;
  cout << "Please enter zero base column (eg. 10): ";
  cin >> column;
  T value;
  cout << "Please enter zero element value: ";
  cin >> value;
  matrix.element(row, column, value);
 }
 return matrix;
}
template <class T>
void print_sparse_matrix(const sparse_matrix<T>& _matrix)
{
 for(int row = 0; row < _matrix.rows_length(); row++)
 {
  cout << "[";
  for(int column = 0; column < _matrix.columns_length(); column++)
  {
   cout << _matrix.element(row, column);
   if(column < (_matrix.columns_length() -1))
   {
    cout << ", ";
   }
  }
  cout << "]" << endl;
 }
 return;
}
int main()
{
 sparse_matrix<double> m1(10, 10);
 sparse_matrix<double> m2(10, 10);
 while(true)
 {
  try
  {
   cout << "Commands:" << endl;
   cout << "1)  Read sparse matrix m1." << endl;
   cout << "2)  Read sparse matrix m2." << endl;
   cout << "3)  Print sparse matrix m1." << endl;
   cout << "4)  Print sparse matrix m2." << endl;
   cout << "5)  Print transpose of matrix m1." << endl;
   cout << "6)  Print transpose of matrix m2." << endl;
   cout << "7)  Print m1 + m2." << endl;
   cout << "8)  Print m1 - m2." << endl;
   cout << "9)  Print scalar * m1." << endl;
   cout << "10) Print scalar * m2." << endl;
   cout << "11) Print m1 * m2." << endl;
   cout << "12) Exit." << endl;
   int command;
   cout << "Please enter command number: ";
   cin >> command;
   switch(command)
   {
   case 1:
    {
     m1 = read_sparse_matrix<double>();
    }
    break;
   case 2:
    {
     m2 = read_sparse_matrix<double>();
    }
    break;
   case 3:
    {
     print_sparse_matrix<double>(m1);
    }
    break;
   case 4:
    {
     print_sparse_matrix<double>(m2);
    }
    break;
   case 5:
    {
     sparse_matrix<double> transpose = m1.transpose();
     print_sparse_matrix<double>(transpose);
    }
    break;
   case 6:
    {
     sparse_matrix<double> transpose = m2.transpose();
     print_sparse_matrix<double>(transpose);
    }
    break;
   case 7:
    {
     sparse_matrix<double> result = m1.add(m2);
     print_sparse_matrix<double>(result);
    }
    break;
   case 8:
    {
     sparse_matrix<double> result = m1.subtract(m2);
     print_sparse_matrix<double>(result);
    }
    break;
   case 9:
    {
     double scalar;
     cout << "Please enter a scalar: ";
     cin >> scalar;
     sparse_matrix<double> result = m1.scalar_multiply(scalar);
     print_sparse_matrix<double>(result);
    }
    break;
   case 10:
    {
     double scalar;
     cout << "Please enter a scalar: ";
     cin >> scalar;
     sparse_matrix<double> result = m2.scalar_multiply(scalar);
     print_sparse_matrix<double>(result);
    }
    break;
   case 11:
    {
     sparse_matrix<double> result = m1.multiply(m2);
     print_sparse_matrix<double>(result);
    }
    break;
   case 12:
    {
     exit(0);
    }
    break;
   default:
    {
     cout << "Invalid command." << endl;
    }
    break;
   }
  }
  catch(exception e)
  {
   cout << "Error: " << e.what() << endl;
  }
  cout << endl;
 }
 return 0;
}

----------

