نمايش پست تنها
قديمي ۰۸-۱-۱۳۸۸, ۱۲:۴۴ بعد از ظهر   #8 (لینک دائم)
Astaraki Female
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Thumbs up هشت وزير با روش بازگشت به عقب Backtracking

فرض کنید که در محله‌ای به دنبال یک کتاب فروشی خاص می‌گردیم. این کتاب فروشی در کوچه‌ای قرار دارد که نبش آن یک خواربار فروشی است و همچنین در ابتدای خیابانی که این کوچه قرار دارد یک مدرسه هست.

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

روالی که برای یافتن جواب در مثال بالا دنبال شد، روش بازگشت به عقب (Backtracking) نام دارد. در این روش همانطور که در مثال مشاهده کردید، در هر زمان که متوجه شدیم مسیر انتخاب شده به جواب نمی‌رسد، یک مرحله به عقب برگشته و مسیر دیگری را دنبال می کنیم.

روش بازگشت به عقب برای آن دسته از مسائلی قابل استفاده است که برای رسیدن به جواب بتوان یک جستجوی سیستماتیک را دنبال کرد. به عنوان نمونه می‌توان بهره‌گیری از این روش را در بازیهای کامپیوتری، سیستمهای اثبات تئوریها، شبکه‌های مفهومی، هایپرتکس و ... دید.


مثال 8 وزير:

چگونه هشت وزیر را بر روی صفحه شطرنج قرار دهیم به گونه‌ای که هیچ یک از آنها مورد تهدید دیگری قرار نگیرد؟

در مقاله زير اين مسئله با استفاده از روش عقبگرد همراه با سورس کد آن کاملاً توضيح داده شده
فايل ضميمه
نوع فايل: pdf att226_0_vazere8.pdf (292.4 كيلو بايت, 5700 نمايش)
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
arameshn (۱۲-۹-۱۳۸۹), arezoooo (۰۴-۱۱-۱۳۹۱), djmorteza (۰۲-۲۹-۱۳۹۲), elenorgt500 (۰۹-۳۰-۱۳۹۱), fereshte2 (۰۳-۱۹-۱۳۸۹), green_Dream (۱۱-۲۲-۱۳۸۸), hadijojo (۰۲-۲۳-۱۳۹۱), Mahdi67 (۱۱-۲۳-۱۳۸۹), mehrshadkiani (۰۲-۱۹-۱۳۹۲), sinarock (۰۹-۹-۱۳۹۲), soodeh1010 (۰۲-۲۱-۱۳۹۰), tohidsabunchi (۰۸-۱۰-۱۳۸۹)