كتب dynamic programming algorithm
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
خوارزم برمجة ديناميكية (معلومة)
لنفترض أننا بصدد إيجاد أقل تكلفة، أو أقل عدد من العمليات الحسابية، اللازمة لضرب المصفوفات. لو كنا بصدد ضرب مصفوفتين فقط فإن هناك طريقة واحدة لضربها ببعض، وعليه فإن أقل تكلفة هي تكلفة القيام بهذه العملية. يمكننا تحديد أقل تكلفة باتباع هذا الخوارزم التكراري:
- نأخذ المصفوفات المتعاقبة ونفصلها إلى تعاقبين فرعيين.
- نبحث عن أقل تكلفة لازمة لضرب هذين التعاقبين.
- نقوم بإضافة هذه التكاليف لبعضها، وبإضافة تكلفة ضرب نتيجة التعاقبين.
- نكرر هذه العملية لكل موضع قابل لفصل المصفوفات المتعاقبة، ونأخذ أقل تكلفة بين جميع المحاولات.
شفرة برمجية بلغة السي:
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; } } } } }
