مقالات و جزوه های درسی رشته کامپیوتر

فصل سوم:

برنامه نویسی پویا

برنامه نویسی پویا، از این لحاظ که نمونه به نمونه های کوچکتر تقسیم می شود ، مشابه روش تقسیم و حل است ولی در این روش ، نخست نمونه های کوچک تر را حل می کنیم ، نتایج را ذخیره می کنیم و بعدا هر گاه به یکی از آن ها نیاز پیدا شد، به جای محاسبه دوباره کافی است آن را بازیابی کنیم.

 

مراحل بسط یک الگوریتم برنامه نویسی پویا به شرح زیر است:

 1- ارائه یک ویژگی بازگشتی برای حل نمونه ای از مسئله .

 2- حل نمونه ای از مسئله به شیوه جزء به کل با حل نمونه های کوچک تر.

الگوریتم 3-1: ضریب دو جمله ای با استفاده از تقسیم و حل

 int bin ( int n , int k)

 {

 if ( k == 0 || n ==k )

 return 1 ;

 else

 return bin (n – 1 , k -1 ) + bin ( n-1 , k);

 }

الگوریتم 2-3: ضریب دو جمله ای با استفاده از برنامه نویسی پویا

 int bin2 ( int n , int k )

 {

 index i , j ;

 int B [0..n][0..k]

 for ( i = 0; i ≤ n ; i ++)

 if ( j == 0 || j == i )

 B [i] [j] = 1;

 else

  B [i] [j] = B [ i – 1 ] [ j -1 ] + B [ i -1 ] [j];

 return B[n] [k]:

}

 

الگوریتم 3-3: الگوریتم فلوید برای یافتن کوتاه ترین مسیر

 void floyd ( int n

 const number W [][],

 number D [][],

 { 

 index i , j , k ;

 D = W ;

 for ( k = 1 ; k ≤ n ; k ++)

 for ( i = 1; i ≤ n ; i++)

 for ( j = 1 ; j ≤ n ; j ++)

 D [i] [j] = minimum ( D [i][j], D[i][k] + D[k][j]);

 }

تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم3-3
(الگوریتم فلوید برای یافتن کوتاهترین مسیر)

 

 

عمل اصلی: دستورهای موجود در حلقه for .

اندازه ورودی:n  ، تعداد رئوس گراف.

 

 

T (n) = n × n × n = n³ Є θ (n³)

 

الگوریتم 4-3:الگوریتم فلوید برای یافتن کوتاهترین مسیر 2

 void floyd2 ( int n,

 const number W [][],

 number D [][],

 index P [][])

 {

 index i , j , k ;

 for ( i = 1 ; i ≤ n ; i ++)

 for ( j = 1 ; j ≤ n ; j++)

 

 

 P [i] [j] = 0;

 D = W;

 for ( k = 1 ; k <= n ; k ++)

 for ( i = 1 ; i <= n ; i ++)

 for ( j = 1 ; j <= n ; j ++)

 if ( D [i] [k] + D [k] [j] < D [i] [j] ) {

 P [i] [j] = k;

 D [i] [j] = D [i] [k] + D [k] [j];

  }

 }

 

الگوریتم 5-3:چاپ کوتاهترین مسیر

مسئله: چاپ رئوس واسطه روی کوتاه ترین مسیر از راسی به راس دیگر در یک گراف موزون.

 void path ( index q , r)

 {

 if (P [q] [r] != 0 ) {

 path (q , P [q] [r] );

 cout << “v” << P [q] [r];

  path (P [q] [r] , r );

 }

 }

3-3 برنامه نویسی پویا و مسائل بهینه سازی

 

حل بهینه ، سومین مرحله از بسط یک الگوریتم برنامه نویسی پویا برای مسائل بهینه سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:

 

1- ارائه یک ویژگی بازگشتی که حل بهینه ی نمونه ای از مسئله را به دست می دهد.

 

 2- محاسبه مقدار حل بهینه به شیوه ی جزء به کل.

 

 3- بنا کردن یک حل نمونه به شیوه ی جزء به کل.

 

 

هر مسئله بهینه سازی را نمی توان با استفاده از برنامه نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.

 

اصل بهینگی در یک مسئله صدق می کند اگریک حل بهینه برای نمونه ای از مسئله ، همواره حاوی حل بهینه برای همه ی زیر نمونه ها باشد.

 

4-3 ضرب زنجیره ای ماتریس ها

هدف بسط الگوریتمی است که ترتیب بهینه را برای n  ماتریس معین کند.

ترتیب بهینه فقط به ابعاد ماتریس ها بستگی دارد.

علاوه بر n ، این ابعاد تنها ورودی های الگوریتم هستند.

این الگوریتم حداقل به صورت نمایی است.

 

الگوریتم 6-3: حداقل ضرب ها

int minimult ( int n,

 const int d [],

 index P [][] )

 {

 index  i , j , k , diagonal;

 int M [1..n] [1..n];

 for ( i = 1 ; i ≤  n ; i ++)

 M [i] [i] = 0:

 for (diagonal = 1; diagonal ≤ n -1 ; diagonal ++)

 for ( i = 1 ; i ≤ n – diagonal ; i ++) {

 j = i + diagonal ;

 M[i][j] = minimum (M[i][k] + M[k +1 ][j] +

 d [ i – 1] * d [k] * d [j]);

 P [i][j] = a value of k that gave the minimum;

 }

 return M[1][n];

 }

 

تحلیل پیچیدگی زمانی حالت معمول برای ا لگوریتم6-3( حداقل ضرب ها)

 

 عمل اصلی: می توان دستورات اجرا شده برای هر مقدار k را عمل اصلی در نظر بگیریم. مقایسه ای را که برای آزمون حداقل انجام می شود، به عنوان عمل اصلی در نظر می گیریم.

 اندازه ورودی: n  ، تعداد ماتریس ها که باید ضرب شوند.

 

N (n -1) (n + 1) / 6 Є θ (n³)

 

الگوریتم 7-3: چاپ ترتیب بهینه

مسئله:  چاپ ترتیب بهینه برای ضرب n ماتریس.

  void order ( index i, index j)

 {

 if ( i == j)

 cout << “A” << i ;

 else {

 k = P [i] [j];

 cout << “(“;

 order ( i , k);

 order ( k +1 , j );

 cout << “)”;

 }

 }

5-3 درخت های جست و جوی دودویی بهینه

 

درخت جست و جوی دودویی یک دودویی از عناصر( که معمولا کلید نامیده می شوند)است که از یک مجموعه مرتب حاصل می شود، به قسمی که:

 

 1- هر گره حاوی یک کلید است.

 

 

2- کلید های موجود در زیردرخت چپ یک گره مفروض، کوچک تر یا مساوی کلید آن گره هستند.

 

3- کلیدهای موجود درزیردرخت راست یک گره مفروض، بزرگ تر یا مساوی کلید آن گره هستند.

 

الگوریتم 8-3: درخت جست و جوی دودویی

 void search ( node _ pointer tree ,

 keytype keyin,

 node _ poiner & p)

 {

 bool found ;

 p = tree;

 found = false;

 while (! found)

 

 if ( p - > key == keyin )

  found = true ;

 else if ( keyin < p - > key )

 p = p -> left ;

 else

 p = p - > right ;

 }

 

الگوریتم 9-3 : درخت جست و جوی بهینه

مسئله: تعیین یک درخت جست وجوی بهینه برای مجموعه ای از کلید ها، هر یک با احتمالی مشخص.

 void optsearchtree ( int n ,

 const float p[];

 float & minavg,

 index R[][])

 {

 index i , j , k , diagonal ;

 float A [1..n + 1] [0..n];

 for ( i = 1 ; i ≤ n ; i ++) {

 A [i] [i -1] = 0

 A [i] [i] = p [i];

 R [i] [i] = i ;

 R [i] [ i – 1 ] = 0;

 }

 A[ n + 1 ] [n] = 0 ;

 R[ n + 1 ] [n] = 0 ;

  for (diagonal = 1;diagonal ≤ n – 1; diagonal++)

 for ( i = 1; i ≤ n – diagonal ; i ++) {

 j = i + diagonal ;

 A[i][j] = minimum(A[i][k-1]+A[k+1][j])+∑pm 

 R[i][j] = a value of k that gave the minimum;

 }

 minavg = A [1][n];

 }

تحلیل پیچیدگی زمانی حالت معمول برای ا لگوریتم درخت جستجوی دودویی بهینه

 

عمل اصلی: دستورات اجرا شده به ازای هر مقدار از k .این دستورات شامل یک مقایسه برای آزمون حداقل است.

 اندازه ورودی: n ، تعداد کلید.

 

 

T(n) = n ( n -1) ( n + 4 ) / 6 Є θ ( n³ )

 

الگوریتم 10 -3: ساخت درخت جست و جوی دودویی بهینه

 node _ pointer tree ( index i , j )

 {

 index k ;

 node _ pointer p ;

 k = R [i] [j];

 if ( k == 0 )

 return NULL;

 else {

 

 p = new nodetype ;

 p - > key = key [k] ;

 p - > left = tree (i , k – 1);

 p - > right = tree ( k+1 , j);

 return P;

 }

 } 

 

الگوریتم11-3:الگوریتم برنامه نویسی پویا برای مسئله فروشنده دوره گرد

 void tarvel ( int , n

 const number W[ ][ ] ,

 index P[ ] [ ] ,

 number & minlength)

 {

 index i , j , k ;

 number D[1..n][subset of V - { v1 } ] ;

 for ( i = 2 ; i ≤ n ; i ++)

 D[i] [Ø] = W [i] [1] ;

 

 for (k = 1 ; k ≤ n - 2 ; k ++)

 

 for (all subsets A Ç V – { v1 } containing k vertices)

 

 for (i such that i != 1 and vi is not inA){

 

  D[i] [A] = minimum ( W [i] [j] + D [j] [A – {vj}]);

 

 P [i] [A] = value of j that gave the minimum;

 

 

 

 D [1] [ V – { v1 } ] = minimum ( W [1] [j] + 

 D [j] [ V – { v1 – v j } ] );

 P [1] [ V – { v1 } ] = value of j that gave the minimum;

 minlength = D [1] [ V – { v1 } ];

 }

تحلیل پیچیدگی فضا و زمان در حالت معمول برای ا لگوریتم 11-3 ( الگوریتم برنامه نویسی پویا برای مسئله فروشنده دوره گرد)

 

 عمل اصلی: زمان در هر دو حلقه ی اول و آخر ، در مقایسه با زمان در حلقه میانی چشمگیر نیست، زیرا حلقه میانی حاوی سطوح گوناگون تودر تویی است . دستورات اجرا شده برای هر مقدار v j را می توان عمل اصلی در نظر گرفت.

 اندازه ورودی : n  ، تعداد رئوس موجود در گراف.

 

 

T (n) = n 2ⁿ Є θ ( n 2ⁿ )