بحث کاربر:B.k1369: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
←روش ها و راهبرها در طراحی الگوریتم: بخش جدید |
←روش برنامهنویسی پویا: بخش جدید |
||
خط ۶۱:
البته لازم به دکر است که راهبرد ها و روش های دیگری نیز وجود دارند. مواردی که بیان شد از مهمترین موارد و راهبردها می باشد.<br />
[[کاربر:B.k1369|B.k1369]] ([[بحث کاربر:B.k1369#top|بحث]]) ۲۵ ژوئن ۲۰۱۲، ساعت ۰۷:۵۳ (UTC)
== روش برنامهنویسی پویا ==
یکی از روشهای پرکاربرد و مشهور طراحی الگوریتم روش برنامهنویسی پویا (یا برنامهریزی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مساله بر زیرمسالهها کار میکند. اما تفاوتهای چشمگیری با آن دارد.<br />
زمانی که یک مساله به دو یا چند زیرمساله تقسیم میشود، دو حالت ممکن است پیش بیاید:<br />
1- دادههای زیرمسالهها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونه چنین مواردی مرتبسازی آرایهها با روش ادغام یا روش سریع است که دادهها به دو قسمت تقسیم شده و به صورت مجزا مرتب میشوند. در این حالت دادههای یکی از بخشها هیچ ارتباطی با دادههای بخش دیگر نداشته و در نتیجه حاصل از آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارآیی خوبی دارد.<br />
2- دادههای زیرمساله وابسته به هم بوده و یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمسالهها همپوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله اعداد فیبوناچی است.<br />
اصل بهینگی: اصل بهینگی یعنی حل مساله به صورت بهینه، حاوی حل بهینه تمامی زیرمسائل آن نیز باشد.
به عبارت دیگر، مساله باید به گونهای باشد که با یافتن حل بهینه آن، حل بهینه همه زیرمسالهها نیز به دست آمده باشد. به عنوان مثال، در یافتن کوتاهترین مسیر بین دو شهر، مسیر بین مبدا و هر گرهی که در مسیر بهینه وجود دارد، بهینهترین مسیر بین آن دو نیز هست.
[[کاربر:B.k1369|B.k1369]] ([[بحث کاربر:B.k1369#top|بحث]]) ۲۷ ژوئن ۲۰۱۲، ساعت ۱۴:۰۰ (UTC)
|