ماتریس خلوت (Sparse)
می‌دانیم که هر ماتریس با m سطر و n ستون دارای m×n عنصر است. در برخی کاربردها، ماتریس‌هایی داریم که بسیاری از درایه‌های آن فاقد مقدار هستند. مثلا فاصله‌ی جاده‌ی مستقیم بین هر دو شهر یک کشور را در نظر بگیرید. شهرها در ستون‌ها و سطرها توزیع شده‌اند و درایه‌ی سطر i-اُم و ستون j-اُم نشان دهنده‌ی طول جاده‌ی مستقیم بین دو شهر i-اُم و j-اُم است. بدیهی است که لزوما بین همه‌ی شهرها جاده‌ی مستقیم وجود ندارد که در این‌صورت درایه‌های متناظر مقداری نخواهند داشت (یا مقدار صفر دارند). چنین ماتریسی را که تعداد زیادی از درایه‌های آن فاقد مقدار هستند را ماتریس خلوت (Sparce) می‌گوییم.
در مسئله‌های مربوط به نظریه‌ی گراف، معمولا داده‌های گراف را با ماتریس مجاورت (Adjacency matrix) آن نشان می‌دهند که ماتریسی است مربعی با ابعاد n×n (n تعداد گره‌های گراف است). مقدار هر درایه، بیان‌گر وجود و کیفیت یال بین دو راسی است که در سر ستون و سر سطر قرار دارند. برای گراف‌هایی که تعداد راس آن زیاد و تعداد یال کمتر است، ماتریس مجاورت آن، یک ماتریس خلوت (Sparce) است.
در هنگام برنامه‌نویسی، ماتریس‌ها را با آرایه‌ها پیاده‌سازی می‌کنیم. بدون توجه به این‌که تخصیص فضای مورد نیاز آرایه بصورت ایستا (Static) انجام می‌گیرد یا به‌صورت پویا (Dynamic)، می‌توان به‌جای ذخیره‌ی همه‌ی درایه‌ها (با تعداد زیادی درایه‌ی صفر)، فقط درایه‌هایی که دارای مقدار هستند را ذخیره کنیم. به‌عنوان مثال، گراف زیر را در نظر بگیرید که جاده‌های مستقیم بین 5 شهر A، B، C، D و E را مدل‌سازی می‌کند:
ماتریس مجاورت این گراف مانند شکل زیر است. در این‌جا شهرهایی که در سر سطرها نوشته شده است، به‌عنوان شهر مبداء در نظر گرفته می‌شوند.
| A(0) | B(1) | C(2) | D(3) | E(4) | |
| A(0) | 0 | 35 | 0 | 50 | 0 |
| B(1) | 0 | 0 | 0 | 0 | 0 |
| C(2) | 0 | 0 | 0 | 0 | 0 |
| D(3) | 0 | 0 | 48 | 0 | 0 |
| E(4) | 0 | 0 | 0 | 0 | 0 |
اعداد داخل پارانتز، اندیس آرایه را نشان می‌دهند و همان‌طور که ملاحظه می‌کنید، از 25 درایه‌ی ماتریس بالا فقط 3 خانه (خانه‌های رنگی) دارای
مقدار هستند. به‌عبارت دیگر برای این گراف کوچک، 88% فضای اشغالی فاقد مقدار است و در مصرف حافظه اسراف شده است. برای
جلوگیری از اتلاف حافظه، همان‌طور که اشاره شد به‌جای ذخیره‌ی همه‌ی درایه‌ها (حتی صفرها)، فقط درایه‌هایی که دارای مقدار هستند را ذخیره می‌کنیم.
برای این‌کار از یک ماتریس 3 ستونی استفاده می‌کنیم. سطر اول ماتریس شامل 3 عدد با ترتیب زیر است:
- r تعداد سطرها
- c تعداد ستون‌ها
- m تعداد درایه‌های دارای مقدار
که برای ماتریس مجاورت گراف، مقادیر r و c
برابر تعداد رئوس گراف است. در m سطر بعدی یکی از مقادیر را با 3 عدد به شرح زیر می‌نویسیم:
- راس مبداء (اندیس سطر)
- راس مقصد (اندیس ستون)
- مقدار درایه
برای ماتریس بالا داریم:
| 0 | 1 | 2 | |
| 0 | 5 | 5 | 3 |
| 1 | 0 | 1 | 35 |
| 2 | 0 | 3 | 50 |
| 3 | 2 | 0 | 48 |
تگ ها
- پیشنهادی
- تازهها
- ویژهنامه
