تکنیک عقب‌گرد

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

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

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

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

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

منابع

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.