بیخیال مرغ و تخم مرغ، خودت تولید کن!

پرسش: یک کلمه شروع، یک کلمه پایان، و یک مجموعه از کلمات که همگی هم طولند داده شده اند. هدف، تبدیل کلمه شروع به کلمه پایان با استفاده از دنباله ای از تغییرات است با این محدودیت که در هر تغییر تنها یک حرف از یک کلمه عوض می شود. کلمات میانی دنباله باید متعلق به لیست مجموعه کلمات داده شده باشند. برنامه ای بنویسید که طول کوتاهترین دنباله تبدیل برای رسیدن از کلمه شروع به پایان را برگرداند.

پاسخ: طبق معمول کار را با یک مثال آغاز می کنیم تا مطمین شویم که مساله را درست درک کرده ایم. به عنوان مثال اگر کلمه شروع tell و کلمه پایان book باشد و مجموعه کلمات داده شده cool, bell, tool, wool, wage, rage,cook, toll, cage باشند، آنگاه دنباله tell ->toll-> tool-> cool-> cook->book کوتاه ترین دنباله تبدیل می باشد.

قبل از اینکه در مورد راه حل این مساله بحث کنیم بگذارید روی یک اصطلاح توافق کنیم: اگر کلمه ای با کلمه ی دیگر تنها در یک حرف متفاوت باشد آنها را 'مجاور' هم می نامیم. مثلا toll و tool دو کلمه مجاورند.

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

برای ساخت هر دنباله باید از کلمه شروع آغاز کرد، یک کلمه مجاور از لیست کلمات یافت، و به انتهای دنباله اضافه نمود. در واقع در هر نقطه از یک دنباله باید w (تعداد کل کلمات) را با کلمه کنونی مقایسه کنیم تا بررسی کنیم که آیا مجاور هستند؟ اگر طول کلمات L باشد، حداکثر طول دنباله کلمات L می باشد. با توجه به اینکه هر یک از کلمات مجاور ممکن تا رسیدن به کلمه پایان بکاربرده شوند، پیچیدگی این الگوریتم (O(W^L می باشد که یک تابع نمایی است.

این الگوریتم دو مشکل دارد که آن را اینچنین کند می کنند: (ا) آن که هر مسیر تبدیل را باید تا آخر برویم تا همه مسیرهای ممکن تبدیل را بیابیم، تا اینکه نهایتا بتوانیم کوتاهترین آنها را انتخاب کنیم، و (اا) اینکه هر بار باید همه کلمات را با آخرین کلمه ای که در دنباله تبدیلات به آن رسیده مقایسه کنیم تا کلمات مجاور بعدی در دنباله را انتخاب نماییم. این کار بنظر تکراری می رسد.

در ادامه فکر می کنیم که چگونه این مشکلات را حل کنیم.

برای واضح تر شدن مشکل این الگوریتم مرتبط با دنبال کردن مسیرهای تبدیل، ساختار مجاورت کلمه ها در مثال بالا را ترسیم کنیم.

شکل بالا یک ساختمان داده گراف را تداعی می کند که در آن کلمات گره ها را می سازند و خط بین آنها ارتباط 'مجاور بودن' (یعنی تفاوت تنها در یک حرف) دو کلمه را نشان می دهد.

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

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

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

اما برای ساختن چنین گرافی هر کلمه باید با کلمه دیگر مقایسه شود. این یعنی w^2 مقایسه که هزینه هر مقایسه L است. بنابر این هزینه ساختن این گراف (O(L*w^2 می باشد.

این ساختار هزینه های آتی یافتن مجاورها را بشدت کم می کند، اما ممکن است بسیار غیر بهینه باشد. در گراف مثال فوق این ایراد عیان می شود: ممکن است که گراف یک مولفه (زیر گرافی متصل از گره ها) داشته باشد که به هیچ وجه نتوانیم از کلمه شروع به آن ها برسیم. مثلا از کلمه شروع هیچ مسیری به کلمات cage, wage, rage وجود ندارد. بنابر این دلیلی برای لحاظ کردن آنها در ساختن گراف مجاورت وجود ندارد. اما قبل از پیمایش گراف نمی توانیم این را بفهمیم. این شبیه مساله مرغ و تخم مرغ است و یک وابستگی حلقه مانند بین این دو مرحله الگوریتم وجود دارد.

برای شکستن مساله مرغ و تخم مرغ باید از روش دیگری برای پیمایش گراف استفاده کنیم. جرقه این ایده جدید بر اساس تعریف مجاورت به ذهن می رسد. کلمه مجاور در دنباله تغییرات را می توان مستقیما با جایگزین کردن یک حرف الفبا از L موقعیت حروف در یک کلمه ایجاد نمود. مثلا کلمات aell، bell, cell، … و غیره با جایگزین کردن حرف اول، و کلمات tall، tbll، tcll ، … با جایگزین کردن در محل دوم کلمه tell ایجاد می شوند. کلماتی که با این ترتیب ایجاد می شوند مجاور کلمه اول می باشند.

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

مشکل کوچک آن است که همه کلمات ایجاد شده الزاما در مجموعه کلمات داده شده وجود ندارند. برای حل این مشکل قبل از استفاده از یک کلمه ایجاد شده برای توسعه به سطح بعد، ابتدا باید بررسی کنیم که آیا آن در لیست کلمات داده شده می باشد؟ خبر خوب آن است که ساختمان داده مجموعه (set) خیلی سریع می تواند پاسخ دهد که آیا یک کلمه تولید شده در مجموعه کلمات داده شده می باشد.

اگر از روش ایجاد کلمات و جستجوی سطح به سطح استفاده نماییم، برای هر کلمه 26*L کلمه مجاور تولید می کنیم. از آنجا که w کلمه داریم، هزینه کل یافتن کوتاه ترین تبدیل حداکثر w*L*26خواهد بود که برای مقادیر بزرگ L و W نسبت به الگوریتم جستجوی کامل عمقی بسیار سریع تر است. الگوریتم جستجوی سطح به سطح که از گراف اتصالات پیش پردازش شده استفاده می کند در بدترین حالت دارای پیچیدگی محاسباتی (O(w*L + W^2 می باشد. قسمت W^2 این فرمول مربوط به محاسبه اولیه اتصالات گراف است.

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

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

می توانیم این موارد را با مصاحبه کننده در میان بگذاریم و ببینیم کدام الگوریتم برای سناریویی که او می خواهد مفید تر است. در اینجا فرض می کنیم که مصاحبه کننده از الگوریتم ایجاد کلمات و جستجوی سطح به سطح استقبال می کند.

در این صورت این الگوریتم روی یک داده ورودی تست می کنیم که مطمین شویم درست کار می کند. سپس شروع به پیاده سازی الگوریتم می کنیم.

نام مناسب برای تابع با پارامترهای مناسب در نظر می گیریم (خط 1). سپس لیست کلمات داده شده  را به همراه کلمه پایان در یک ساختمان داده مجموعه (set) می ریزیم (خط 2). یک شمارنده گام یا سطحی که در مسیرها تا بحال رسیده ایم در نظر می گیریم (خط 3). سپس لایه صفر را با قرار دادن کلمه شروع در آن می سازیم (خط 4). سپس در یک حلقه تکرار که تا رسیدن به آخرین لایه پیش می رویم (خط 5). یک لیست برای قرار دادن عناصر لیست بعد در نظر می گیریم (خط 6). به ازای هر عنصر در لایه کنونی (خط 7) هر بار آن کلمه را با کلمه پایان مقایسه می کنیم. در صورتی که به کلمه پایان برسیم شماره لایه را به عنوان تعداد مراحل رسیدن به آن برمی گردانیم (خط 8 و 9). در غیر این صورت تمام کلمات ممکن مشتق از این کلمه را می سازیم و چک می کنیم که آیا در لیست کلمات داده شده هستند (خط 11 تا 14). در صورتی که کلمه جدید در لیست کلمات باشد آن را به لایه بعد اضافه می کنیم (خط 15) و از لیست کلمات حذف می کنیم (خط 16) تا از مشاهده تکراری این کلمه در مسیرهای طولانی تر جلوگیری کنیم. هنگامی که تمام کلمات مشتق از لایه کنونی را در لایه جدید گذاشتیم، شمارنده لایه را یک واحد می افزاییم (خط 17) و لایه جدید را به عنوان لایه کنونی در نظر می گیریم (خط 18). اگر تمام لایه ها پیمایش و به کلمه پایان نرسیدیم آنگاه مقدار 1- را به نشان عدم وجود پاسخ بر میگردانیم (خط 19).