فرهنگ و هنر ورزش

تکنیک عقب گرد

تکنیک عقب گرد(back traching) شیوه ای در حل مسائل است که از علامت های خاصی برای بیان اینکه راه حل کاندیدی به حل مسئله می انجامد یا خیراستفاده می کند.این رویکردبرای حل مسائل درخت فضای آن مسئله راایجاد کرده و تعیین میکند کدام گره امید بخش است. الگوریتم های عقب گردی از تابلوها یا علامت هایی برای بیان اینکه یک راه حل کاندید به حل مسئله نمی‌انجامد استفاده میکند. عقبگرد، حالت اصلاح شده ی جستجوی عمقی یک درخت می باشد.

مثال اول در روش عقب گرد مسئله قفل رمزی می باشد.یک قفل رمزی شامل n کلید دیجیتالی است که هر کلید فقط دو حالت بسته(۱) یا حالت باز (۰) دارد. می دانیم که n کلید دیجیتالی تعداد ۲nحالت مختلف را پدید می آورند و این قفل تنها با یک حالت که همان رمز است باز می شود.

مثال دوم در روش عقب گرد مسئله چند وزیر میباشد.هدف این مسئله چیدن n وزیر در یک صفحه شطرنج n*n است به گونه ای که هیچ دو وزیری یکدیگر را تهدید نکنند.

مثال سوم در حل مسئله رنگ آمیزی گراف می باشد.در این مسأله می خواهیم تمام راه های ممکن جهت رنگ آمیزی گره های یک گراف بدون جهت را با استفاده از حداکثر m رنگ متفاوت پیدا کنیم، به گونه ای که هیچ دو رأس مجاوری هم رنگ نباشند.

مثال چهارم مسأله حاصل جمع زیر مجموعه ها می باشد .در این مسئله، n عدد صحیح مثبت wi و یک عدد صحیح مثبت w داریم . هدف پیدا کردن تمامی زیر مجموعه هایی از این اعداد صحیح می باشد که حاصل جمع آنها بربر w است.

250px-Schap 8804101084683096173

 

(Visited 153 times, 1 visits today)
  
کانال گردشگری

درباره نویسنده

14p.ir

Leave a Comment