الگوریتم Backtracking (بازگشت به عقب)

سلام دوستان. اینجا من می‌خوام تجربه‌های خودم رو از برنامه نویسی باهاتون به اشتراک بزارم.

اخیرا یه پروژه با استفاده از بک ترک انجام دادم که توی این مقاله بک ترک رو توضیح می‌دم و توی مقاله‌های بعدی راجب پروژه صحبت می‌کنیم.

الگوریتم Backtrack (پس‌گرد-بازگشت به عقب)، یک الگوریتم حل مساله است به این صورت که تمام راه حل‌های ممکن رو آزمایش می‌کنه و هرکجا راه حل مناسب نبود (با قید‌های مساله هم‌خوانی نداشت) به عقب بر‌میگرده و خودش را اصلاح و راه جدیدی را امتحان می‌کنه. (بر خلاف ‌Brute Force که تمام راه ها رو آزمایش کرده و بعد جواب رو بین اونا پیدا می‌کنیم)

معمولا تو مسائلی از این الگوریتم استفاده می‌شه که یا دنبال اولین جواب احتمالی می‌گردیم (یک جواب برای مساله پیدا می‌کنه) و یا دنبال تمام جواب‌های ممکن برای مساله هستیم (با پیدا کردن یک جواب،اون رو به لیست جواب‌ها اضافه کرده و مسیرهای دیگه رو هم برای جواب‌های دیگه طی می‌کنیم)

مثال اول: به عنوان مثال این سودوکوی 4 در 4 رو در نظر بگیرید:

در هر خونه از این جدول اعداد 1 تا 4 می‌تونن قرار بگیرن به طوری که (قید های مساله):

• در هر سطر نباید عدد تکراری وجود داشته باشه
• در هر ستون نباید عدد تکراری وجود داشته باشه
• در مربع‌های کوچک 2 در 2 نباید عدد تکراری وجود داشته باشه

برای پیدا کردن جواب این مساله به ترتیب زیر عمل می‌کنیم:

در هر خونه اعداد 1 تا 4 رو قرار می‌دیم

اگه عدد وارد شده در سطر، ستون و یا مربع 2 در 2 وجود داشت، اون رو پاک کرده و عدد بعدی رو قرار می‌دیم، در غیر این صورت به خونه بعدی میریم.

اگه تمام اعداد رو برای یک خونه امتحان کردیم و هیچ‌کدوم مناسب اون خونه نبودن، به خونه‌ی قبل بر‌می‌گردیم.

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

مثال بالا برای زمانی بود که فقط یکی از جواب‌های مساله برای ما مهمه.

حالا یه مساله دیگه رو بررسی میکنیم که تموم جواب‌های ممکن رو لازم داریم:

مثال دوم: احمد و اصغر و اکبر (اسم بهتر نبود آخه!?) با هم رفیق هستن. اصغر و اکبر بخاطر یه مساله ای که بینشون پیش اومده باهم صحبت نمی‌کنن. احمد بی خبر از این ماجرا برای هر سه تاشون بلیط سینما گرفته. اکبر و اصغر هم چون نمی‌خوان دل احمد رو بشکنن باهاش به سینما میان? ولی دوست ندارن کنار هم بشینن.

میخوایم تعداد حالت‌هایی که امکان داره اکبر و اصغر کنار هم نشینند رو بررسی کنیم:

قید مساله اینه که اکبر و اصغر کنار هم نباشن.

در هر مسیر حل، یکی از اونا روی صندلی اول میشینه و نفر بعدی کنار اون.

اگر دو نفر کنار هم نشستن چک می کنیم ببینیم این دو نفر اکبر و اصغر هستند یا نه.

اگه هستند راه مناسب با قید مساله نیست، پس بر‌می‌گردیم (Backtrack) و مسیر دیگه‌ای رو می‌ریم.

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

تو این gif می‌تونید ببینید که چطور با استفاده از روش بازگشتی این مساله حل شده و هر جا مسیر با قیدهای مساله نخونده اون مسیر رو کنار گذاشتیم و مسیر تازه‌ای رو پیش گرفتیم.

این مقاله، تمرینات و پروژه‌ها رو به همراه دوستم z9776m انجام می‌دیم که بدون کمکش انجام دادن اینا غیر ممکن بود. در پروژه‌ی بعدی می‌خوایم یکی از پازل‌های Sudoku و یا Nonogram رو با روش بک‌ترک حل کنیم.

لطفا لایک ❤️ و کامنت یادتون نره و حتما صفحه ایشون رو هم دنبال کنید چون احتمالا پروژه بعدی (که با زبون پایتون نوشته شده) رو اونجا می‌بینید.