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

دانلود پاورپوینت روش حریصانه (Greedy Approach)

دانلود پاورپوینت روش حریصانه (Greedy Approach)

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

بنابراین اصطلاحا گفته می‌شود که تصمیم‌گیری بر اساس انتخاب‌هایی صورت می‌پذیرد که به صورت محلی بهینه هستند.

در این رویکرد حل مساله امیدواریم تا به راه حل بهینه برسیم. اما ...

این راه حل بهینه دربرخی موارد بدست نمی‌آید.

در این رویکرد برای هر الگوریتم پیشنهادی باید نشان داده شود که پاسخ همواره در تمامی موارد بهینه است.

مساله: می‌خواهیم باقی پول مشتری را با تعدادی سکه (اسکناس) پرداخت کنیم

while ( تازمانیکه سکه‌های بیشتری وجود دارد و مساله هنوز حل نشده است)

{

 بزرگترین سکه باقیمانده را بردار;//selection procedure

 If (اضافه کردن سکه سبب می‌شود مجموع سکه‌های برداشته‌شده از مبلغ بدهی بیشتر شود)//feasibility check

از اون سکه صرفنظر کن;

  else

سکه را اضافه کن;

If (اگر مجموع سکه‌های برداشته شده با بدهی برابری می‌کند)//solution check

مساله حل شده است;

}

روش حریصانه(Greedy Approach):

در حل مسائل با شیوه حریصانه هر تکرار از سه بخش تشکیل شده است:

الف) روال انتخاب (selection procedure)

ب) امکان‌سنجی (feasibility check)

ج) بررسی راه‌حل (solution check)

الف) روال انتخاب (selection procedure):

با معیاری آیتم بعدی را انتخاب می‌کند تا به مجموعه راه‌حل اضافه شود.

توجه شود که معیار انتخاب مسلما بر اساس اطلاعات تا هر مرحله است ...

هرچند سعی می‌شود تا بهینه باشد ولی چون ...

از اطلاعات فقط تا همان مرحله استفاده می‌کند گفته می‌شود که معیار بهینگی محلی است.

ب) امکان‌سنجی (feasibility check):

با اضافه شدن آیتم جدید به مجموعه پاسخ، کنترل می‌شود که آیا با تکمیل کردن این مجموعه می‌توان به پاسخ رسید یا خیر

ج) بررسی راه‌حل:

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

الف) درخت‌های پوشای کمینه(Minimum Spanning Trees):

فرض کنید که در برنامه‌ریزی احداث جاده بین شهرها، می‌خواهیم تعدادی شهر را با جاده به هم وصل کنیم تا امکان رفتن از هر شهر به شهر دیگر با جاده‌های احداث شده ممکن باشد.

چنانچه بحث محدودیت بودجه‌ای مطرح باشد، بنابراین در این برنامه‌ریزی می‌خواهیم حداقل جاده را از نظر طولی احداث کنیم.

در ادامه به دنبال الگوریتمی هستیم که مسائلی از این قبیل را حل کند.

اگر ارتباط بین شهرها را با گراف نمایش دهیم ...

گراف حاصل جهت‌دار (directed) نیست. چراکه با احداث یک جاده بین هر دو شهر امکان رفت‌وآمد از هر دو شهر در این جاده وجود دارد.

به گراف بدون جهت‌داری متصل (connected) گفته می‌شود که ...

مسیری بین هر دو جفت راس وجود داشته باشد.

چرخه ساده (simple cycle):

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

حداقل شامل سه راس باشد و ...

هیچ راس میانی تکراری نباشد.

گراف فاقدچرخه (Acyclic):

گرافی غیرجهت‌دار است که ...

هیچ چرخه ساده‌ای در آن وجود نداشته باشد.

درخت (Tree) گرافی است ...

غیرجهت‌دار (undirected)،

متصل (connected) و

فاقد چرخه (acyclic)

این مساله به این صورت بیان می‌شود:

حذف یال‌هایی از یک گرافِ ...

متصلِ

وزن‌دارِ

غیرجهت‌دار

تا زیرگرافی بدست آید تا ...

همچنان تمامی راس‌ها متصل به هم باقی بمانند و

مجموع وزن یال‌های باقی‌مانده کمینه گردد.

این مساله می‌تواند کاربردهای متعدد مانند:

ساخت جاده

در ایجاد شبکه‌های مخابراتی

در ایجاد شبکه‌های لوله‌گذاری و ...

برای اینکه زیرگرافی شرایط گفته‌شده را داشته باشد حتما بایستی ...

درخت باشد. چراکه ...

اگر زیرگرافی این شرایط را داشته باشد و درخت نباشد،

بنابراین در آن حداقل یک چرخه ساده وجود خواهد داشت که ...

می‌توانیم یکی از یال‌های چرخه را حذف کنیم و گراف حاصل همچنان ...

متصل با مجموع وزن یال‌های کمتر باقی بماند

تعریف:

گراف بدون جهتِ G شامل ...

مجموعه V از راس‌های G و همچنین ...

مجموعه E  شامل یالها (که به صورت دو راس نشان داده می‌شود) می‌باشد.

به اعضای V با vi اشاره می‌کنیم و همچنین ...

یال بین vi و vj را با ...

(vi , vj ) نشان می‌دهیم.

 شامل 62  اسلاید POWERPOINT


اشتراک بگذارید:


پرداخت اینترنتی - دانلود سریع - اطمینان از خرید

پرداخت هزینه و دریافت فایل

مبلغ قابل پرداخت 8,500 تومان

درصورتیکه برای خرید اینترنتی نیاز به راهنمایی دارید اینجا کلیک کنید


فایل هایی که پس از پرداخت می توانید دانلود کنید

نام فایلحجم فایل
Ravesh_harisane_1963508_2742.zip2.1 MB





آخرین محصولات فروشگاه