PDA

View Full Version : تکنیکهای طراحی الگوریتم - روش برنامه نویسی پویا



Kambiz
یک شنبه 13 مهر 1382, 17:35 عصر
پیش از خواندن این مطلب، دانستن مطالب زیر ضروری است:
تحلیل مقدماتی الگوریتمها (http://www.barnamenevis.org/forum/viewtopic.php?t=2909)
تکنیکهای طراحی الگوریتم - مقدمه (http://www.barnamenevis.org/forum/viewtopic.php?t=2796)
تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر (http://www.barnamenevis.org/forum/viewtopic.php?t=2874)_____________________________ __________________________________________

روش برنامه نویسی پویا (Dynamic Programming) غالبا" برای الگوریتمهایی بکار برده می‌شود که در پی حل مسئله‌ای بصورت بهینه می‌باشند.

در روش تقسیم و تسخیر ممکن است برخی از زیرمسائل کوچکتر با هم برابر باشند که در این صورت زیرمسائل برابر بطور تکراری چندین مرتبه حل می‌شوند که این یکی از معایب روش تقسیم و تسخیر است.

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

روش برنامه نویسی پویا یک روش پایین به بالا است (Bottom-Top Technique) به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. در حالیکه از نظر ساختاری روش تقسیم و تسخیر روشی است از بالا به پایین (Top-Down Technique) یعنی بطور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و بسمت پایین و حل مسائل کوچکتر به پیش می‌رود.

برای دریافت بهتر مفهوم روش برنامه نویسی پویا، در ادامه الگوریتم یافتن تعداد تبدیلهای (Combinations) تعداد k عضو از یک مجموعه n عضوی را با استفاده از دو روش برنامه نویسی پویا و تقسیم و تسخیر ارائه و سپس با هم مقایسه می کنیم.

فرمول محاسبه تعداد تبدیلهای k از n بصورت زیر است:


C(n,k) = n! / (k! * (n - k)!) (0 <= k <= n)
فرمول بالا را می توان با روابط زیر بگونه‌ای دیگر بیان نمود:


1 (k = 0 یا k = n)
C(n,k) =
C(n-1,k-1) + C(n-1,k) (0 < k < n)
بدین ترتیب الگوریتم تقسیم و تسخیری که برای حل این مسئله حاصل می‌شود بصورت زیر است:


function C(n : integer; k : integer) return integer
begin
if k = 0 or k = n then
return 1;
else
return C(n-1, k-1) + C(n-1, k);
end if;
end C;
وش برنامه نویسی پویا از همان رابطه بالا استفاده می کند با این تفاوت که در این روش جدولی به ابعاد (n+1)*(k+1) تبدیل ممکن لازم است تا تعداد تبدیلهای j از i را برای هر i از صفر تان n و هر j از صفر تا k ذخیره کرد.

محاسباتی که باید به ترتیب انجام شوند عبارتند از:
خانه‌های هم ارز جدول با تبدیلهای 0 از i و 1 از 1 مقدار ثابت 1 پر می‌شوند.
خانه‌های باقیمانده جدول با افزایش i+j به ازای تبدیلهای j از i محاسبه و پر می‌شوند.یادآوری می‌کنم که چون برای محاسبه تبدیل j از i تنها لازم است که حاصل تبدیلهای j-1 از i-1 و j از i-1 را داشته باشیم، محاسبه مقادیر خانه‌های جدول به ترتیب صعودی i+j تضمین می کند که خانه‌های مورد نیاز جدول برای محاسبه تبدیل j از i از پیشتر محاسبه شده‌اند.

الگوریتم حل این مسئله با روش برنامه نویسی پویا بصورت زیر است:


function C(n : integer; k : integer) return integer
type table is array (0..n, 0..k) of integer;
bc : table;
i, j, k : integer;
sum : integer;
begin
{ Initializes fixed table entries }
for i in 0..n loop
bc(i,0) := 1;
end loop;
bc(1,1) := 1;
{ Calculates the rest of table entries }
sum := 3; i := 2; j := 1;
while sum <= n+k loop
bc(i,j) := bc(i-1,j-1) + bc(i,j-1);
i := i-1; j := j+1;
if i < j or j > k then
sum := sum + 1;
if sum <= n+1 then
i := sum-1; j := 1;
else
i := n; j := sum-n;
end if;
end if;
end loop;
return bc(n,k);
end C;
حال به مقایسه دو الگوریتم می‌پردازیم:

در الگوریتم پیاده سازی شده در روش تقسیم و تسخیر، در بدترین حالت ورودی (k=n/2) زمان اجرای الگوریتم تقریبا" برابر خواهد بود با <span dir=ltr>O((2^n)/n)</span>. با وجود اینکه شرح الگوریتم بسیار ساده است (چون مستقیما" رابطه شرح داده شده برای صورت مسئله پیاده سازی شده است) اما با وجود چنین زمان اجرایی استفاده از این الگوریتم برای nهای بزرگ کاملا" غیر عملی است.

در روش برنامه نویسی پویا چون الگوریتم دقیقا" تنها یک بار تعداد تبدیلهای k از n را محاسبه می‌کند بسیار بهره‌ور‌تر و بهینه‌تر است. زمان اجرای این الگوریتم <span dir=ltr>O(n*k)</span> است که برای بدترین حالت (k=n/2) برابر <span dir=ltr>O(n^2)</span> خواهد بود.

مثال یافتن تعداد تبدیلهای k از n مثالی است که تمام خصوصیات کلیدی الگوریتمهای برنامه نویسی پویا را به نمایش می گذارد:
یک جدول از تمام نتایج زیر مسائل ساخته می‌شود.
خانه‌های جدول برای کوچکترین زیر مسائل مقدار دهی اولیه می شود.
خانه های باقیمانده جدول با ترتیبی دقیق (یعنی مطابق با افزایش اندازه زیر مسئله) با استفاده از خانه‌هایی که از پیشتر مقدار دهی شده‌اند، محاسبه و مقدار دهی می‌شوند.
هر خانه دقیقا" فقط یک بار محاسبه می‌شود.
آخرین مقداری که محاسبه می‌شود پاسخ مسئله اولیه است.
پیاده سازی بر اساس ساختار تکرار است (هیچوقت از ساختار بازگشت استفاده نمی‌شود، حتی اگر تحلیل یک مسئله بطور طبیعی راه حلی بازگشتی پیشنهاد دهد).

(امید)
یک شنبه 13 مهر 1382, 18:50 عصر
10 امتیاز اهدایی تقدیم به آقا کامبیز بخاطر مطالب مفیدی که در این بخش می نویسه :دلار:

Kambiz
یک شنبه 13 مهر 1382, 19:24 عصر
ممنون امید جان. :oops:

Mohammad_Mnt
یک شنبه 13 مهر 1382, 22:45 عصر
منم تا حالا از اهدا استفاده نکرده بودم ، دیدم این دفعه دیگه نمی شه 8) 10 امتیاز به آقا کامبیز :oops:

Kambiz
دوشنبه 14 مهر 1382, 00:44 صبح
محمد جان از تو هم ممنونم. :)

ناصرقلی
شنبه 18 بهمن 1382, 07:15 صبح
آقا کامبیز من یه چند وقتیه دنبال یه راه حل بسیار سریع برای محاسبه دترمینان یک ماتریس بسیار بزرگ هستم و سوال من اینه که آیا اصلا با استفاده از برنامه سازی پویا می شه این کار را انجام داد یا نه من خیلی روی این قضیه فکر کردم ولی راهی به نظرم نرسیده.

Kambiz
سه شنبه 21 بهمن 1382, 02:47 صبح
ببخشید، سوال رو خوندم ولی گذاشتم برای وقتی که فرصت دارم جواب بدم که یادم رفت. :oops:

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

من خودم به شخصه ترجیح می‌دم در این موارد بجای اینکه الگوریتم رو خودم بنویسم٬ با یک جستجو روی اینترنت الگوریتم به درد بخوری پیدا کنم. دلیل این امر هم اینه که برای نوشتن الگوریتمهای بهینه ریاضی باید یک پشتوانه خوب ریاضی داشت که من ندارم. :(

lotfi_javad
سه شنبه 18 آبان 1389, 10:40 صبح
پیش از خواندن این مطلب، دانستن مطالب زیر ضروری است:

تحلیل مقدماتی الگوریتمها (http://www.barnamenevis.org/forum/viewtopic.php?t=2909)
تکنیکهای طراحی الگوریتم - مقدمه (http://www.barnamenevis.org/forum/viewtopic.php?t=2796)
تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر (http://www.barnamenevis.org/forum/viewtopic.php?t=2874)

__________________________________________________ _____________________


سلام
ميدونم كه اين مطلب خيلي وقته از ايجادش گذشته اما لينكهاي بالا متاسفانه باز نميشه امكان داره راهنمايي بفرماييد.


باتشكر

مسعود اقدسی فام
چهارشنبه 19 آبان 1389, 00:13 صبح
آقا کامبیز من یه چند وقتیه دنبال یه راه حل بسیار سریع برای محاسبه دترمینان یک ماتریس بسیار بزرگ هستم و سوال من اینه که آیا اصلا با استفاده از برنامه سازی پویا می شه این کار را انجام داد یا نه من خیلی روی این قضیه فکر کردم ولی راهی به نظرم نرسیده.

روش‌های متفاوتی برای محاسبه‌ی دترمینان یک ماتریس وجود داره. روش گاوس - جردن رو امتحان کردید؟

kh_rouhi
سه شنبه 07 دی 1389, 11:47 صبح
کد ها خراب شدن.لطفا اگه کسی میدونه درست منه.

cancer140
یک شنبه 01 دی 1392, 18:55 عصر
سلام .اگه ميشه توي نوشتن اين برنامه به من كمك كنيد:
فرض کنید شما قرار است در تیمی کار کنید که یک بازی کامپیوتری را می نویسند. در اولین مرحله این بازی، قرار است انسان ها، تانک ها، و ... حرکت کنند. نقطه شروع حرکت و مقصد آنها مشخص است. اما اعضای این تیم، ایده ای در مورد نحوه پیدا کردن مسیر حرکت آنها ندارند. از شما خواسته شده است که برنامه ای بنویسید و آرایه مسیر را چاپ کنید.
در واقع قرار است شما متد findPath را پیاده سازی کنید. پارامترهای این متد، ماتریس m*n نقشه بازی، x1,y1 به عنوان مختصات فعلی فرد و x2,y2 به عنوان مختصات مقصد بازیکن می باشند و خروجی یک Array List از زوج مقادیر (xi,yi) نقاط مسیر است.

روش حل:حريصانه

amirebra
یک شنبه 08 دی 1392, 14:07 عصر
این برنامه را استاد ما قبلا به ما گفته بود یه نفر هست فامیلش هاشمیه می دونم الان نجف آباد درس می خونه کد را اون برام نوشت متاسفانه شماره ازش ندارم وگرنه بهت میدادم