طراحی الگوریتم ها جلسه پنجم
فصل پنجم:
راهبرد عقبگرد
- از تکنیک عقبگرد برای حل مسائلی استفاده می شود که در آن ها دنباله ای از اشیاء از یک مجموعه مشخص انتخاب می شود، به طوری که این دنباله ، ملا کی را در بر می گیرد.
- یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.
- هدف از مسئله n وزیر ، چیدن n مهره وزیر در یک صفحه شطرنج است ، به طوری که هیچ دو وزیری یکدیگر را گارد ندهند. یعنی هیچ دو مهره ای نباید در یک سطر، ستون یا قطر یکسان باشند.
- عقبگرد حالت اصلاح شده ی جست و جوی عمقی یک درخت است.
- الگوریتم عقبگرد همانند جست و جوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می شوند که گره امید بخش باشدو در آن گره حلی وجود نداشته باشد.
الگوریتم 1-5: الگوریتم عقبگرد برای مسئله n وزیر
void queens ( index i)
{
index j;
if ( promising(i))
if ( i == n)
cout << col [1] through col [n];
else
for ( j = 1 ; j ≤ n ; j++ ) {
col [ i +1 ] = j;
queens ( i + 1);
}
}
bool promising ( index i )
{
index k ;
bool switch;
k = 1;
switch = true ;
while ( k < i && switch ) {
if (col [i] == col[k] || abs(col[i] – col[k] == i-k)
switch = false;
k++;
}
return switch;
}
5-3 استفاده از الگوریتم مونت کارلو برای برآورد کردن کارایی یک
الگوریتم عقبگرد
- الگوریتم های مونت کارلو ، احتمالی هستند،یعنی دستور اجرایی بعدی گاه به طور تصادفی تعیین می شوند.
- در الگوریتم قطعی چنین چیزی رخ نمی دهد.
- همه ی الگوریتم هایی که تا کنون بحث شدند، قطعی هستند.
- الگوریتم مونت کارلو مقدار مورد انتظار یک متغیر تصادفی را که روی یک فضای ساده تعریف می شود ، با استفاده از مقدار میانگین آن روی نمونه تصادفی از فضای ساده بر آورد می کند.
- تضمینی وجود ندارد که این برآورد به مقدار مورد انتظار
واقعی نزدیک باشد، ولی احتمال نزدیک شدن آن، با افزایش زمان در دسترس برای الگوریتم، افزایش می یابد.
الگوریتم2-5 : برآورد مونت کارلو
int estimate ()
{
node v ;
int m, mprod , numnodes;
v = root of state space tree;
numnodes = 1;
m = 1;
mprod = 1;
while ( m != 0) {
t = number of children of v ;
mprod - mprod * m;
numnodes = numnodes + mprod * t;
m = number of promising children of v;
if ( m != 0)
v = randomly selected promising
child of v ;
}
return numnodes;
}
الگوریتم 3-5: بر آورد مونت کارلو برای الگوریتم 1-5 (الگوریتم
عقبگرد برای مسئلهn وزیر)
int ostimate _ n_ queens (int n)
{
index i , j , col [1..n];
int m , mprod , numnodes ;
set _of_ index prom _children;
i = 0;
numnodes =1 ;
m = 1;
mprod = 1 ;
while ( m != 0 && i != n ) {
mprod = mprod * m ;
numnodes = numnodes + mprod * n;
i ++;
m = 0 ;
prom_childern = Ø;
for ( j = 1 ; j ≤ n ; j++;) {
col [i] = j ;
if ( promising(i)) {
m++;
prom_children = prom _ children U {i};
}
}
if ( m != 0) {
j = random selection from prom _
children ;
col [i];
}
}
return numnodes;
}
الگوریتم 4-5: الگوریتم عقبگرد برای مسئله حاصل جمع زیر
مجموعه ها
مسئله : تعیین همه ی ترکیبات اعداد صحیح موجود در یک مجموعه n عدد صحیح ، به طوری که حاصل جمع آن ها مساوی مقدار معین W شود.
void sum _of _subsets ( index i ,
int weight , int total)
{
if (promising(i))
if ( weight == W )
cout << include [1] through include [i];
else {
include [i +1] = “yes” ;
sum_ of_subsets ( i +1 , weight + w [i +1],
total – w [ i + 1 ]);
}
}
bool promising ( index i);
{
return (weight + total ≥ W) &&( weight == W ||
weight + w [ i + 1 ] ≤ W );
}
5-5 رنگ آمیزی گراف
- مسئله رنگ آمیزی m ، عبارت از یافتن همه ی راه ها ی ممکن برای رنگ آمیزی یک گراف بدون جهت ، با استفاده از حداکثر m رنگ متفاوت است، به طوری که هیچ دو راس مجاوری هم رنگ نباشند.
الگوریتم5-5: الگوریتم عقبگرد برای مسئله رنگ آمیزی m
void m_coloring (index i )
{
int color ;
if ( promising (i))
if ( i == n)
cout << vcolor[1] through vcolor [n];
else
for (color = 1; color ≤ m; color ++) {
vcolor [ i + 1] = color ;
m_coloring (i + 1);
}
}
bool promising ( index i )
{
index j ;
bool switch ;
switch = true;
j = 1;
while ( j < i && switch ) {
if ( W [i] [j] && vcolor [i] == vcolor[j])
switch = false ;
j ++;
}
return switch ;
}
الگوریتم 6-5: الگوریتم عقبگرد برای مسئله مدارهای ها میلتونی
void hamiltonian ( index i )
{
index j ;
if ( promising (i)
if ( i == n - 1)
cout << vindex [0] through vindex [ n-1];
else
for ( j = 2 ; j ≤ n ; j ++) {
vindex [ i +1] = j ;
hamiltonian ( i +1 );
}
}
bool promising ( index i )
{
index j ;
bool switch ;
if( i == n -1 &&! W [vindex [ n-1 ]] [ vindex [0]])
switch = false ;
else {
switch = true ;
j = 1;
while ( j < i && switch ) {
if (vindex [i] == vindex [j])
switch = false ;
j++;
}
}
return switch;
}
5-7 مسئله کوله پشتی صفر و یک
- در این مسئله مجمو عه ای از قطعات داریم که هر یک دارای وزن و ارزش معین است.
- اوزان و ارزش ها اعداد مثبتی هستند.
- دزدی درنظر دارد قطعاتی که می دزدد درون یک کوله پشتی قرار دهد و اگر وزن کل قطعات قرار داده شده در آن کوله پشتی از یک عدد صحیح مثبتW فراتر رود،
کوله پشتی پاره می شود.
الگوریتم 7-5:الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک
void knapsack ( index i ,
int profit , int weight)
{
if ( weight ≤ W && profit > maxprofit ) {
maxprofit = profit ;
numbest = i ;
bestset = include;
}
if ( promising (i)) {
include [ i + 1 ] = “yes”;
knapsack ( i + 1, profit + p [ i + 1] , weight +
w [ i +1 ]);
include [ i +1] = “ no”;
knapsachk ( i +1 , profit , weight );
}
}
bool promising ( index i )
{
index j , k ;
int totweight ;
float bound;
if ( weight ≥ W)
return false ;
{
j = i +1 ;
bound = profit ;
totweight = weight ;
while ( j <= n && totweight + w[j] <= W) {
totweight = totweight + W [j];
bound = bound + p[j];
j++;
}
k = j;
if ( k <= n)
bound = bound + (W – totweight) * p [k]/w[k];
return bound > max profit ;
}
}
2-5-7 مقایسه الگوریتم برنامه نویسی پویا و الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک
- تعداد عناصری که توسط الگوریتم برنامه نویسی پویا برای مسئله کوله پشتی صفر و یک محاسبه می شود دربدترین حالت به O (minimum (2ⁿ , nW)) تعلق دارد.
- در بدترین حالت ، الگوریتم عقبگرد (ⁿ 2)θ گره را چک می کند.
- الگوریتم عقبگرد معمولا کارایی بیشتری نسبت به الگوریتم برنامه نویسی پویا دارد.
- هوروویتز و شانی ، روش تقسیم و حل را با روش برنامه نویسی پویا ترکیب کرده الگوریتمی برای مسئله کوله پشتی صفر و یک بسط داده اند که دربدترین حالت به O(2^n/2)
تعلق دارد.