اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.
پرسش: یک ماتریس دوبعدی باینری (مقادیر عناصر صفر یا یک می باشند) داده شده است. مساحت بزرگتری مربعی در آن که تنها از 1 تشکیل شده است را بیابید.
توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.
زمان بندی: ارسال پاسخ ها تا پایان روز 20 آوریل
یادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.
توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.
اولین فردی که الگوریتم رو نوشت مهدی بود اما برای نوشتن راه حل نتونست وقت بگذاره. بنابر این توحید و ایمان دست به دست هم دادن و شرح مساله را خیل زیبا نوشتن. من هم ویرایش کردم.
به هر سه نفر تبریک می گم و می گم: عالی هستید! ادامه بدید!
برای حل مسئله با یک مثال شروع می کنیم تا مطمئن شویم که مسئله را درست درک کرده ایم.اگر ماتریس 5x6 زیر را در نظر بگیریم:
در درون آن 12 مربع 1x1 (همه خانه های با مقدار 1) و دو مربع 2x2 (.دو مربع آبی و سبز) مشاهده می کنیم. هیچ مربعی با اندازه بزرگتر وجود ندارد. بنابراین مساحت بزرگترین مربع 4 می باشد. این مثال و مشاهده ایده حل مسئله به ساده ترین روش یعنی جستجوی کامل را می دهد.
برای جستجوی کامل در واقع باید تمام مربع های ممکن با اندازه های از 1 تا بزرگترین مربع ممکن (یعنی حداکثر اندازه کوچکترین ضلع ماتریس) را بسازیم. برای این منظور به ازای هر خانه A (یا خانه مرجع) که مقدارش 1 می باشد بزرگتری مربعی که A گوشه سمت راست-پایین آن (جنوب شرقی) قرار می گیرد را می سازیم. مثلا برای خانه سطر 3 و ستون 3 (که با ستاره مشخص شده است) بزرگترین مربع با رنگ آبی نشان داده شده است.
گامهای این الگوریتم بصورت زیر است:
گام اول: عنصر بعدی A از عناصر ماتریس که مقدار آن 1 می باشد را به عنوان خانه مرجع در نظر میگیریم. اگر چنین عنصری وجود نداشت به گام پنجم الگوریتم می رویم.
گام دوم: از طول 2=L شروع می کنیم و بررسی می کنیم که آیا می توان مربعی با این اندازه درست کرد که A جنوب شرقی آن باشد.
گام دوم: هر بار L را یک واحد افزایش می دهیم و دوباره بررسی می کنیم تا زمانی که دیگر نتوانیم مربع با اندازه L تشکیل دهیم.
گام سوم: مقدار 1-L بزرگتری مربعی است که A جنوب شرقی اش قرار می گیرد .
گام چهارم: پاسخ به دست آمده را با اندازه بزرگترین مربعی که در کل به دست آمده مقایسه می کنیم. در صورت بزرگتر بودن از بزرگترین پاسخ به دست آمده، اندازه مربع اخیر را جایگزین می کنیم و بعد به گام اول می رویم.
گام پنجم: بزرگتری مربع بدست آمده پاسخ صحیح می باشد..
قطعه کد زیر الگوریتم جستجوی کامل را پیاده سازی می کند.
اگر اندازه ماتریس MxN باشد، آنگاه پیچیدگی زمانی این الگوریتم ( O((MxN)^2 می باشد. پیچیدگی حافظه ای( O(1 می باشد.
اشکال این روش آن است که محاسبات برای بدست آوردن اندازه بزرگترین مربع که A در سمت جنوب شرقش می باشد تکرار می کند. اما بر اساس مشاهده زیر می توان از تکرارهای محاسبه بیجا خودداری کرد. به عنوان مثال اگر ماتریس زیر به عنوان ماتریس ورودی باشد:
و محاسبه اندازه بزرگتری مربع متشکل از 1 برای خانه ها از (0, 0) تا خانه (2, 2) محاسبه کرده باشیم،
آنگاه می توانیم به صورت انتزاعی مربع های زیر را ببینیم:
که در آن مربع سبز مربوط به بزرگتری مربع خانه شمال A، مربع قرمز مربوط به بزرگتری مربع خانه غرب A، و خانه نارنجی برای خانه شمال غرب A می باشد. همانطور که می توان دید:
1- اندازه ضلع بزرگترین مربع مربوط به A حداقل به اندازه کوچکترین ضلع مربوط به سه مربع دیگر است.
2- اندازه ضلع بزرگترین مربع مربوط به A نمی تواند بزرگتر از کوچکترین ضلع مربوط به سه مربع دیگر نمی تواند بزرگتر باشد.
3- از 1 و 2 نتیجه میگیریم که بزرگترین ضلع مربوط به خانه A برابر است با مینیمم اندازه ضلع مربوط به سه مربع شمال، غرب، و شمال غربی.
این نتیجه در واقع یک الگوریتم استقرایی را پیشنهاد می دهد که در آن مقدار عنصر (j, i) بر اساس محاسبات مربوط به خانه های (i-1, j) و (i, j-1) و (i-1, j-1) می تواند بر اساس فرمول ساده زیر محاسبه شود:
dp[i, j] = min(dp[i-1, j], dp[i-1, j-1], dp[i, j-1])+1
در فرمول فوق از اسم dp برای جدول جدیدی که محاسبات مربوط به بزرگترین مربع ممکن را در خود نگه می دارد استفاده کرده ایم. این اسم اختصار Dynamic Programming می باشد و یادآوری می کند که در ساختن آن از مفهوم برنامه نویسی پویا استفاده کرده ایم.
مثال زیر یک ورودی و جدول تکمیل شده با روش الگوریتم استقرایی را نشان می دهد.
Input:
dp:
با توجه با این الگوریتم، شروع به نوشتن برنامه می کنیم. ابتدا حالت خاص ماتریس خالی را بررسی می کنیم (خط 2). این کار برای این خوب است که از خطاهای احتمالی در ورودی پارامتر جلوگیری کنیم. سپس ابعاد ماتریس ورودی را بدست می آوریم (خط 3). آنگاه یک ماتریس کمکی به اسم dp در نظر می گیریم که قرار است اندازه بزرگترین مربع ممکن را در خود نگه دارد (خط 5). در این خط از یک ترفند استفاده شده است که نیاز به بررسی حالت خاص برای سطر اول و ستون اول نباشد. بنابر این یک سطر و ستون جعلی با مقادیر 0 در نظر می گیریم که نوشتن برنامه را سر راست کند.
سپس بصورت سطری از بالای گوشه راست ماتریس اصلی شروع می کنیم و مقدار مربوط به عنصر dp متناظر آن را مطابق با فرمول استقرایی فوق محاسبه می کنیم (سطرهای 6 تا 10). نهایتا مقدار نهایی را به عنوان پاسخ بر می گردانیم.
با توجه به اینکه همه عناصر ماتریس را یکبار برریس می کنیم، پیچیدگی زمانی این الگوریتم (O(MxN می باشد. پیچیدگی حافظه این الگوریتم( O(MxN می باشد.
در این راه حل برای محاسبه سطر i ام ما از مقدار عنصر قبلی و سطر i-1 ام استفاده می کردیم، بنابراین نیازی به ماتریس دو بعدی نداریم و می توان مسئله را با یک بردار ستونی حل کرد.
بردار dp خود را با صفر مقدار دهی می کنیم، همانگونه که عناصر ماتریس ورودی را به صورت ردیفی می خوانیم، درایه های ماتریس را با استفاده از فرمول زیر محاسبه می کنیم. برای هر ردیف prev به مقدار قدیمی dp[j- 1]ارجاع می دهد.
dp[j]= min(dp[j-1], dp[j], prev)+1
Input:
dp:
قطعه برنامه زیر پیاده سازی بهینه سازی شده الگوریتم بروش برنامه نویسی پویا می باشد.
این روش میزان حافظه اجرایی را به سایز تعداد سطرهای ماتریس کاهش می دهد.
دنباله خروجی زیر جزییات اجرای الگوریتم را نشان می دهد.
