تصف هذه المقالة خوارزمية مضاعفة مصفوفة Java (البرمجة الديناميكية). شاركه للرجوع إليه ، على النحو التالي:
وصف المشكلة: مُعطى مصفوفات n: A1 و A2 و ... و AN ، حيث AI و AI+1 متعددة ، I = 1 ، 2 ... ، N-1. تحديد ترتيب حساب حساب المنتج المستمر المصفوفة ، بحيث يكون عدد الضربات المطلوبة لحساب المنتج المستمر المصفوفة في هذا الترتيب هو الأقل. بيانات الإدخال هي عدد المصفوفات وحجم كل مصفوفة ، ونتيجة الإخراج هي ترتيب الحساب والحد الأدنى لعدد الضربات للمنتج المستمر للمصفوفة.
تحليل المشكلات: نظرًا لأن مضاعفة المصفوفة تلبي قانون الارتباط ، يمكن أن يكون هناك العديد من أوامر الحساب المختلفة لحساب المنتج المستمر للمصفوفة. يمكن تحديد ترتيب الحساب هذا عن طريق إضافة قوسين. إذا تم تحديد ترتيب حساب المنتج المستمر المصفوفة بالكامل ، فهذا هو أن المنتج المستمر قد تم تقسيمه بالكامل ، فيمكن استدعاء الخوارزمية القياسية لضرب اثنين من المصفوفات بشكل متكرر في هذا الترتيب لحساب المنتج المستمر المصفوفة.
يمكن تعريف منتج مصفوفة من أقواس تمامًا على النحو التالي:
(1) المصفوفة المفردة قوس بالكامل ؛
(2) تم تمثيل منتج المصفوفة A بالكامل ، ثم يمكن تمثيل A كمنتج لـ 2 منتجات مصفوفة بالكامل B و C وأقواس إضافية ، أي A = (BC)
على سبيل المثال ، هناك 5 طرق مختلفة لقواعد منتج المصفوفة A1A2A3A4: (A1 (A2 (A3A4)))) ، (A1 ((A2A3) A4)) ، ((A1A2) (A3A4)) ، ((A1 (A2A3)) A4). تتوافق كل طريقة في التقدم بالكامل مع ترتيب الحساب لمنتج متصل بالمصفوفة ، والذي يحدد مقدار الحساب المطلوب لصنع المنتج.
انظر المثال التالي ، احسب مضاعفة المصفوفة الثلاثة {A1 ، A2 ، A3} ؛ الأبعاد هي 10*100 ، 100*5 ، 5*50 على التوالي. احسب العدد المطلوب من المرات في هذا الترتيب ((A1*A2)*A3): 10x100x5+10x5x50 = 7500 مرة ، احسب العدد المطلوب من المرات في هذا الترتيب (A1*(A2*A3)): 10*5*50*100*50 = 75000 مرة
لذا فإن السؤال هو: كيفية تحديد ترتيب العمليات بحيث يمكن تقليل مبلغ الحساب.
أفكار الخوارزمية:
مثال: افترض أنك تريد حساب منتج Matrix Murblication A1A2A3A4A5A5 ، حيث تكون أبعاد كل مصفوفة:
A1: 30*35 ؛ A2: 35*15 ؛ A3: 15*5 ؛ A4: 5*10 ؛ A5: 10*20 ؛ A6: 20*25
العلاقة العودية:
حساب التصميم A [i: j] ، 1≤I≤J≤N ، والحد الأدنى لعدد الضربات المطلوبة m [i ، j] ، ثم القيمة المثلى للمشكلة الأصلية هي m [1 ، n].
عندما i = j ، a [i: j] = ai ، لذلك ، m [i] [i] = 0 ، i = 1،2 ، ... ، n
عندما أكون <J ، إذا تم فصل الترتيب الأمثل لـ A [i: j] بين AK و AK+1 ، I <= K <J ، ثم: M [i] [j] = m [i] [k]+m [k+1] [j]+pi-1pkpj. نظرًا لأن موضع نقطة الانفصال K غير معروف أثناء الحساب ، لم يتم تحديد K بعد. ومع ذلك ، لا يوجد سوى JI الممكن لموقف K. لذلك ، K هو الموضع الذي يقلل فيه موضع JI من كمية الحساب.
باختصار ، هناك علاقات متكررة على النحو التالي:
بناء الحل الأمثل:
إذا تم الإشارة إلى موضع الانزلاق k من m [i] [j] [j] على أنه s [i] [j] ، بعد حساب القيمة المثلى m [i] [j] ، يمكن بناء الحل الأمثل المقابل بشكل متكرر من s [i] [j]. يوضح الرقم الموجود في S [i] [j] أن أفضل طريقة لحساب سلسلة المصفوفة A [i: j] يجب فصلها بين المصفوفة AK و AK+1 ، أي أن الأقواس المثلى يجب أن تكون (a [i: k]) (a [k+1: j). لذلك ، من المعلومات المسجلة بواسطة S [1] [n] ، يمكننا أن نرى أن الأقواس المثلى لحساب A [1: n] هي (a [1: s [1] [n]]) (a [s [1] [n] +1: n]). بشكل متكرر ، الأقواس المثلى لـ A [1: S [1] [S [1] [S [1] [N]]) هي (A [S [1] [S [1] [N]]+1: S [1] [S [1] [S [1] [S [1] [N]]). وبالمثل ، يمكن تحديد أن الأقواس المثلى لـ A [S [1] [n] +1: n] يتم كسرها في s [s [1] [n] +1] [n] ... إذا واصلنا إعادة توحيد هذا ، يمكننا أخيرًا تحديد الأقواس الكاملة الأمثل لـ A [1: n] وبناء حل مثالي للمشكلة.
Package Matrix ؛ Public Class Matrix {public static void matrixchain (int [] p ، int n ، int [] m ، int [] [] s) {for (int i = 1 ؛ i <= n ؛ i ++) {m [i] [i] = 0 ؛ } لـ (int r = 2 ؛ r <= n ؛ r ++) {for (int i = 1 ؛ i <= n-r+1 ؛ i ++) {int j = i+r-1 ؛ m [i] [j] = m [i + 1] [j] + p [i-1]*p [i]*p [j] ؛ s [i] [j] = i ؛ لـ (int k = i+1 ؛ k <j ؛ k ++) {int t = m [i] [k]+m [k+1] [j]+p [i-1]*p [k]*p [j] ؛ if (t <m [i] [j]) {m [i] [j] = t ؛ s [i] [j] = k ؛ }}}}} تتبع الفراغ الثابت العام (int i ، int j ، int [] [] s) {if (i == j) return ؛ Traceback (i ، s [i] [j] ، s) ؛ Traceback (s [i] [j] + 1 ، j ، s) ؛ System.out.println ("multiply a" + i + "،" + s [i] [j] + "و a" + (s [i] [j] + 1) + "،" + j) ؛ } public static void main (string [] args) {system.out.println ("نتائج اختبار wulin.com:") ؛ Matrix MC = New Matrix () ؛ int n = 7 ؛ int p [] = {30 ، 35 ، 15 ، 5 ، 10 ، 20 ، 25} ؛ int m [] [] = new int [n] [n] ؛ int s [] [] = new int [n] [n] ؛ int l = p.length-1 ؛ MC.Matrixchain (P ، L ، M ، S) ؛ لـ (int i = 1 ؛ i <n ؛ i ++) {for (int j = 1 ؛ j <n ؛ j ++) {system.out.print (m [i] [j]+"/t") ؛ } system.out.println () ؛ } system.out.println () ؛ لـ (int i = 1 ؛ i <n ؛ i ++) {for (int j = 1 ؛ j <n ؛ j ++) {system.out.print (s [i] [j]+"") ؛ } system.out.println () ؛ } mc.traceback (1 ، 6 ، s) ؛ }}نتائج التشغيل:
لمزيد من المعلومات حول خوارزميات Java ، يمكن للقراء المهتمين بهذا الموقع عرض الموضوعات: "بنية بيانات Java وبرنامج تعليمي الخوارزمية" ، "ملخص" Tips Java ".
آمل أن يكون هذا المقال مفيدًا لبرمجة Java للجميع.