درخت و صف خیالی اما بدرد بخور!

فهرست مطالب

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

پاسخ: حل مساله را با یک مثال شروع می کنیم تا مطمین شویم آن را خوب درک کرده ایم. اگر مقدار شروع 2, مقدار انتها 9 و لیست داده شده [3,4] باشند آنگاه می توان به روشهای مختلف از 2 به 9 رسید. مثلا ابتدا 3 را با 2 جمع بزنیم تا به حاصل میانی3 + 2 = 5 برسیم. سپس 4 را به آن می افزاییم تا به مقدار پایانی 4+5 = 9 برسیم. بنابر این حداقل 2 بار باید از عملگر جمع استفاده نماییم تا از ابتدا به انتها برسیم.

به عنوان مثالی دیگر، اگر مقدار شروع 999 و مقدار پایان 42 باشد و لیست داده شده [40, 3] باشد آنگاه می توانیم 40 را به مقدار شروع اضافه کنیم. با توجه به اینکه حاصل میانی 1039 می باشد باید باقیمانده آن را بر 1000 حساب می کنیم. به این ترتیب به مقدار جدید 1000%(40+999) = 39 می رسیم. با یک بار افزودن 3 به مقدار 42 می رسیم.  اگر راههای دیگر را نیز امتحان نماییم می فهمیم که برای مقادیر شروع، پایان، و لیست داده شده تعداد 2 کمترین تعداد عمل جمع مورد نیاز می باشد. به عنوان مثالی دیگر اگر مقدار ابتدا 1، مقدار انتها 7، و مقدار لیست [10, 5] باشند آنگاه نمی توان با استفاده از لیست و عملگر جمع از مقدار ابتدا به انتها رسید. در این صورت برنامه باید مقدار 1- را برگرداند.

به عنوان اولین الگوریتم سراغ جستجوی کامل می رویم. در چنین الگوریتمی تمام حالتهایی که از مقدار شروع به مقدار پایان می رسند را می سازیم. سپس حالتی که کمترین تعداد عمل جمع را بکار می برد به عنوان نتیجه برگردانیم.

برای واضح شدن نحوه کارکرد الگوریتم جستجوی کامل یک مثال می زنیم. در مثال بالا یک حالت شامل شروع از 999, افزودن 3, سپس 3، سپس 3, سپس 3, ... است که در این بین مجموع میانی از 1000 رد می شود و به مجموع میانی 2 می رسد و سپس در نقطه ای به مجموع میانی41 می رسیم. در مرحله بعد با افزودن مقدار 3 به 44 می رسیم. با افزودن تعداد زیادی 3 تا مقدار میانی 1001 می رسیم و با افزودن تعداد دیگری 3 به مقدار 43 می رسیم. نهایتا با یکبار دیگر رد شدن از 1000 به مقدار 42 می رسیم. این حالت شامل تعداد وحشتناکی عمل جمع بود. در ایجاد حالت بعدی به جای یکی از این 3 ها از مقدار 40 استفاده می کنیم. در واقع با رسیدن به یک مجموع میانی هر دو حالت استفاده از 3 و استفاده از 4 را امتحان می کنیم.

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

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

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

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

حتی با این بهینه سازی، روش جستجوی کامل دارای پیچیدگی محاسباتی نمایی است.

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

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

این کار براحتی توسط یک روش شناخته شده به نام جستجوی اول سطح (breadth-first search یا به اختصار bfs -- بخوانید بی-اف-اس) انجام می شود.

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

برای نگه داشتن حالتها و ادامه دادن آنها بصورت سطح به سطخ از ساختمان داده صف استفاده می کنیم. برای این کار هر عنصر صف آخرین مقدار یک حالت را نگه می دارد. هر بار یک عنصر از ابتدای صف برمی داریم (در واقع مجموع میانی یکی از حالتها) و به ازای هر عنصر لیست یک حاصل جمع میانی (حاصل جمع عنصری که از صف برداشتیم و یک عنصر لیست) می سازیم. هر حاصل جمع میانی جدید را به انتهای صف اضافه می کنیم. البته این کار را در صورتی انجام می دهیم که مقدار حاصل جمع تاکنون دیده نشده باشد.  این کار را تا دیدن مقدار پایانی ادامه می دهیم. شکل زیر مقادیر داخل صف را برای مثال دوم (یعنی عدد ابتدا 999، انتها 42، و لیست اعداد [40, 3]) از مثال های فوق نشان می دهد.

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

۱- علاوه بر مقدار حاصل جمع میانی شماره سطح آن را نیز همراه آن نگه داریم. به عنوان مثال به همراه 999 شماره سطح یعنی 0 را نیز نگه داریم. با استفاده از این مقدار می توانیم شماره سطح مقدار میانی بعدی منتج از آن را محاسبه کنیم.

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

۳- مقادیر ایجاد شده در جمع های میانی بین 0 تا 999 می باشند و این مقادیر در صف قرار می گیرند. در این روش از یک لیست (که از اینجا به بعد به آن لیست سطح ها می گوییم) استفاده می کنیم. طول این لیست 1000 است و مقدار آن مشخص می کند که آن مقدار در چه سطحی تولید شده است. مقدار اولیه همه عناصر 1- می باشد به این معنا که هنوز در پیمایش سطحی مشاهده نشده است. تنها در اندیس مقدار شروع ( 999 در مثال فوق) مقدار 0 را قرار می دهیم که نشان می دهد در سطح صفر ایجاد شده است. هرگاه یک مقدار X از صف بیرون می کشیم (۱) اگر مقدار X برابر عنصر پایان باشد آنگاه مقدار عنصر X ام در لیست سطح ها تعداد عملیات جمع مورد نیاز را مشخص می کند، و (۲) در غیر این صورت حاصل جمع های میانی جدید را محاسبه می کنیم و در لیست سطح ها مقدار مشخصه کننده سطح آن ها از ریشه را برابر سطح عنصر Xام بعلاوه یک قرار می دهیم.

روش سوم بدون توجه به اندازه لیست ورودی 1000 عنصر خواهد داشت و برای لیست های طولانی ورودی حافظه کمتری استفاده خواهد نمود. بنابر این روش برای دنبال کردن سطح مربوط به مقادیر ایجاد شده استفاده می کنیم.

با این اوصاف شروع به پیاده سازی الگوریتم می کنیم. برای اینکه از ساختمان داده صف آماده استفاده کنیم ماژول deque را به برنامه اضافه می کنیم (خط 1). سپس نام و پارامترهای مناسب برای تابع استفاده می کنیم (خط 2). در خط 3 یک اسم برای مقدار پیمانه تقسیم تعریف می کنیم. این کار برای بهبود خوانایی و قابلیت استفاده مجدد برنامه انجام می شود. چنانچه عدد پایانی (یعنی مقدار end) از پیمانه بیشتر یا از صفر کمتر باشد نمی توانیم از عدد شروع به پایان برسیم. بنابر این مقدار 1- را برمی گردانیم (خطوط 5 و 6).

برای دنبال کردن سطحی که مقدار میانی (یا پایانی) در آن قرار دارد از یک لیست سطح ها به نام step به طول 1000 با مقدار اولیه 1- برای هر عنصر تعریف می کنیم (خط 8).

سپس یک صف تعریف می کنیم و عنصر شروع را در آن قرار می دهیم (خط 10). از آنجا که هیچ کاری برای رسیدن به عدد شروع لازم نیست، مقدار مربط به آن در لیست سطح ها را برابر صفر تنظیم می کنیم (خط 11).  سپس در یک حلقه تکرار تا زمانی که به عدد انتها برسیم یا صف خالی شود (یعنی دیگر عدد جدیدی در بازه 0 تا 999 در دنباله ها ظاهر نشود) کارهایی را انجام می دهیم. این کارها شامل برداشتن یک عنصر از ابتدای صف، مقایسه آن با عدد پایان (خط 15) و افزودن تک تک مقادیر لیست به آن برای ایجاد مقادیر میانی جدید، و نهایتا افزودن آن به صف می باشد (خطوط 13 تا 21). تکه برنامه زیر این الگوریتم را پیاده سازی می کند.

برای تحلیل پیچیدگی محاسباتی الگوریتم فوق باید به این نکته توجه کنیم:

در هر مرحله از این الگوریتم تنها یک عدد از مقادیر ممکن در بازه 0 تا mod_value-1 محاسبه می شود و در هر مرحله به طول لیست (یعنی nums) مقدار جدید محاسبه می شود. اگر طول لیست را با n نشان دهیم، آنگاه پیچیدگی محاسباتی این الگوریتم برابر با (O(n خواهد بود.