books dynamic programming algorithm
If you do not find what you're looking for, you can use more accurate words.
خوارزم برمجة ديناميكية (Info)
لنفترض أننا بصدد إيجاد أقل تكلفة، أو أقل عدد من العمليات الحسابية، اللازمة لضرب المصفوفات. لو كنا بصدد ضرب مصفوفتين فقط فإن هناك طريقة واحدة لضربها ببعض، وعليه فإن أقل تكلفة هي تكلفة القيام بهذه العملية. يمكننا تحديد أقل تكلفة باتباع هذا الخوارزم التكراري:
- نأخذ المصفوفات المتعاقبة ونفصلها إلى تعاقبين فرعيين.
- نبحث عن أقل تكلفة لازمة لضرب هذين التعاقبين.
- نقوم بإضافة هذه التكاليف لبعضها، وبإضافة تكلفة ضرب نتيجة التعاقبين.
- نكرر هذه العملية لكل موضع قابل لفصل المصفوفات المتعاقبة، ونأخذ أقل تكلفة بين جميع المحاولات.
شفرة برمجية بلغة السي:
Matrix-Chain-Order(int p[]) { n = p.length - 1; for (i = 1; i <= n; i++) m[i,i] = 0; for (L=2; L<=n; L++) { // L is chain length for (i=1; i<=n-L+1; i++) { j = i+L-1; m[i,j] = MAXINT; for (k=i; k<=j-1; k++) { q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j];//Matrix Ai has the dimension p[i-1] x p[i]. if (q <m[i,j]) { m[i,j] = q; s[i,j] = k; } } } } }
