ضرب المصفوفات في الخوارزميات وهياكل البيانات: شرح عملي مبسّط
ضرب المصفوفات في مجال الخوارزميات هو العملية التي تدمج مصفوفتين لتنتج مصفوفة ثالثة، وفيها يُحسب كل عنصر في الناتج بجمع حاصل ضرب صفٍّ من المصفوفة الأولى في عمودٍ من الثانية. شرطها الوحيد الذي لا يمكن تجاوزه: عدد أعمدة المصفوفة الأولى يجب أن يساوي عدد صفوف الثانية. فإذا كانت A بحجم m×n وB بحجم n×p، فإن الناتج C يكون بحجم m×p. هذه العملية ليست مجرد تمرين رياضي، بل هي العمود الفقري للرسوميات وتعلّم الآلة وكثير من خوارزميات الرسوم البيانية، ولهذا يُخصَّص لها هذا الشرح من زاوية المبرمج لا زاوية الرياضيات البحتة.
كيف تُحسب نتيجة ضرب مصفوفتين؟
لنفترض أن لديك المصفوفتين A وB، وتريد حساب العنصر الموجود في الصف i والعمود j من الناتج C:
- خذ الصف رقم i كاملًا من المصفوفة A.
- خذ العمود رقم j كاملًا من المصفوفة B.
- اضرب أول عنصر في الصف بأول عنصر في العمود، والثاني بالثاني، وهكذا حتى النهاية.
- اجمع كل هذه الحواصل، والمجموع هو قيمة العنصر C[i][j].
- كرِّر الخطوات لكل خانة في المصفوفة الناتجة.
في الكود، تُترجَم هذه الفكرة عادةً إلى ثلاث حلقات متداخلة: حلقة للصفوف، وحلقة للأعمدة، وحلقة داخلية للجمع التراكمي. هذه هي «الطريقة الساذجة» (Naive)، وهي صحيحة تمامًا لكنها ليست الأسرع للمصفوفات الضخمة.
لماذا تهم هذه العملية في علم الخوارزميات؟
أهمية ضرب المصفوفات تأتي من أنه لغةٌ موحَّدة تُختصَر بها عمليات معقّدة. في الرسوميات ثلاثية الأبعاد، يُمثَّل التدوير والتحجيم والإزاحة كضربِ نقاطٍ في مصفوفات تحويل. وفي الشبكات العصبية، كل طبقة ليست إلا ضربَ مصفوفة المدخلات في مصفوفة الأوزان، ولهذا صار أداء ضرب المصفوفات هو ما يحدِّد سرعة تدريب النماذج فعليًا.
الأهم من منظور الخوارزميات أن رفع مصفوفة المجاورة (Adjacency Matrix) لرسمٍ بيانيٍّ إلى الأس k يعطيك عدد المسارات ذات الطول k بين كل زوج من العُقد. هذه الحيلة تفتح الباب لحلّ مسائل كانت تبدو بعيدة عن الجبر الخطي تمامًا.
التعقيد الزمني وخوارزميات التسريع
الطريقة الساذجة لمصفوفتين مربّعتين بحجم n×n تكلّف O(n³)، لأن لكل خانة من n² خانة نجمع n حاصل ضرب. ومع تضخُّم n يصبح هذا الرقم مؤلمًا، فظهرت خوارزميات أذكى تقسِّم المصفوفة وتقلِّل عدد عمليات الضرب.
| الخوارزمية | التعقيد الزمني التقريبي | متى تُستخدم عمليًا؟ |
|---|---|---|
| الساذجة (Naive) | O(n³) | المصفوفات الصغيرة والمتوسطة؛ الأبسط والأوضح |
| Strassen | ≈ O(n^2.81) | المصفوفات الكبيرة جدًا حيث يُبرِّر التوفير تعقيد التنفيذ |
| Coppersmith–Winograd وما تلاها | ≈ O(n^2.37) نظريًا | بحثية فقط؛ لا تُستعمل في الواقع لضخامة ثوابتها |
نقطة يخطئ فيها كثيرون: التعقيد النظري المنخفض لا يعني بالضرورة سرعةً حقيقية. خوارزميات مثل Coppersmith–Winograd تُسمَّى «خوارزميات مجرّية» لأن الحجم الذي تتفوّق عنده يكون أكبر من أي مصفوفة تُستخدم عمليًا. لهذا تعتمد المكتبات الحقيقية مثل BLAS على تحسينات على مستوى الذاكرة المؤقتة (Cache) وتعليمات المعالج المتوازية (SIMD) أكثر من اعتمادها على خفض الأس النظري.
ضرب المصفوفات وهياكل البيانات
في هياكل البيانات، أبرز استخدام عملي هو الأس السريع للمصفوفات (Matrix Exponentiation). لحساب الحدّ رقم n في متتالية خطية مثل فيبوناتشي، بدلًا من حلقةٍ بطول n، يمكن رفع مصفوفة 2×2 إلى الأس n باستخدام تقنية التربيع المتكرِّر، فينخفض الزمن من O(n) إلى O(log n). هذه القفزة تُحدث فرقًا هائلًا حين يكون n بحجم مليارات.
كذلك تُستخدَم مصفوفة المجاورة لتمثيل الرسوم البيانية، ويُبنى عليها حساب الإغلاق التعدّي (Transitive Closure) وعدّ المسارات. أما في مسائل البرمجة الديناميكية ذات العلاقات التكرارية الثابتة، فيُعاد صوغ الانتقالات على هيئة ضرب مصفوفات لتسريعها لوغاريتميًا.
نصيحة عملية وخطأ شائع
الفخّ الأكثر شيوعًا للمبتدئين هو الخلط بين ضرب المصفوفات والضرب عنصرًا بعنصر (Hadamard). في أدوات مثل NumPy، الرمز * يعني ضربًا عنصريًا لا مصفوفيًا، بينما @ أو np.dot هو ضرب المصفوفات الحقيقي. خطأٌ بسيطٌ هنا يعطي أرقامًا تبدو معقولة لكنها مغلوطة تمامًا، خصوصًا في كود تعلّم الآلة. تذكَّر أيضًا أن ضرب المصفوفات غير تبادلي: A×B لا يساوي B×A في العموم، والترتيب جزءٌ من المعنى لا مجرد تفصيل.
الأسئلة الشائعة
هل يمكن ضرب أي مصفوفتين معًا؟ لا. يجب أن يساوي عدد أعمدة المصفوفة الأولى عدد صفوف الثانية، وإلا فالعملية غير مُعرَّفة أصلًا.
ما الفرق بين O(n³) وخوارزمية Strassen عمليًا؟ Strassen أسرع نظريًا وتوفِّر عند الأحجام الكبيرة جدًا، لكنها أعقد تنفيذًا وأقل استقرارًا عدديًا، لذا تظل الطريقة الساذجة المحسَّنة كافيةً وأوضح لأغلب الحالات.
هل ضرب المصفوفات عملية تبادلية؟ كلا. غالبًا A×B ≠ B×A، بل قد لا يكون أحد الاتجاهين مُعرَّفًا أساسًا بسبب اختلاف الأبعاد.
لماذا يهتم مطوّرو الذكاء الاصطناعي بسرعة هذه العملية تحديدًا؟ لأن كل طبقة في الشبكة العصبية تُختزَل إلى ضرب مصفوفات، فيصبح تحسين هذه العملية هو المفتاح المباشر لتسريع التدريب وخفض تكلفة الحوسبة.