بخشی از پاورپوینت
اسلاید 2 :
روش حریصانه(Greedy Approach)
رویکردی که روش حریصانه برای حل مسائل بهینهسازی دارد شامل تصمیمگیریهای پشتسرهم است که برای هر تصمیمگیری تنها از اطلاعات بدست آمده تا آن مرحله استفاده میکند.
بنابراین اصطلاحا گفته میشود که تصمیمگیری بر اساس انتخابهایی صورت میپذیرد که به صورت محلی بهینه هستند.
در این رویکرد حل مساله امیدواریم تا به راه حل بهینه برسیم. اما .
این راه حل بهینه دربرخی موارد بدست نمیآید.
در این رویکرد برای هر الگوریتم پیشنهادی باید نشان داده شود که پاسخ همواره در تمامی موارد بهینه است.
اسلاید 3 :
روش حریصانه(Greedy Approach)
مساله: میخواهیم باقی پول مشتری را با تعدادی سکه (اسکناس) پرداخت کنیم
while ( تازمانیکه سکههای بیشتری وجود دارد و مساله هنوز حل نشده است)
{
بزرگترین سکه باقیمانده را بردار;//selection procedure
If (اضافه کردن سکه سبب میشود مجموع سکههای برداشتهشده از مبلغ بدهی بیشتر شود)//feasibility check
از اون سکه صرفنظر کن;
else
سکه را اضافه کن;
If (اگر مجموع سکههای برداشته شده با بدهی برابری میکند)//solution check
مساله حل شده است;
}
اسلاید 4 :
روش حریصانه(Greedy Approach)
در حل مسائل با شیوه حریصانه هر تکرار از سه بخش تشکیل شده است:
الف) روال انتخاب (selection procedure)
ب) امکانسنجی (feasibility check)
ج) بررسی راهحل (solution check)
اسلاید 5 :
روش حریصانه(Greedy Approach)
در حل مسائل با شیوه حریصانه هر تکرار از سه بخش تشکیل شده است:
الف) روال انتخاب (selection procedure)
با معیاری آیتم بعدی را انتخاب میکند تا به مجموعه راهحل اضافه شود.
توجه شود که معیار انتخاب مسلما بر اساس اطلاعات تا هر مرحله است .
هرچند سعی میشود تا بهینه باشد ولی چون .
از اطلاعات فقط تا همان مرحله استفاده میکند گفته میشود که معیار بهینگی محلی است.
ب) امکانسنجی (feasibility check)
با اضافه شدن آیتم جدید به مجموعه پاسخ، کنترل میشود که آیا با تکمیل کردن این مجموعه میتوان به پاسخ رسید یا خیر
ج) بررسی راهحل
کنترل میشود که با بدست آمدن مجموعه جدید آیا پاسخ پیدا شده یا باید تکرار بعدی هم انجام شود.
اسلاید 6 :
الف) درختهای پوشای کمینه(Minimum Spanning Trees)
فرض کنید که در برنامهریزی احداث جاده بین شهرها، میخواهیم تعدادی شهر را با جاده به هم وصل کنیم تا امکان رفتن از هر شهر به شهر دیگر با جادههای احداث شده ممکن باشد.
چنانچه بحث محدودیت بودجهای مطرح باشد، بنابراین در این برنامهریزی میخواهیم حداقل جاده را از نظر طولی احداث کنیم.
در ادامه به دنبال الگوریتمی هستیم که مسائلی از این قبیل را حل کند.
اسلاید 7 :
الف) درختهای پوشای کمینه
اگر ارتباط بین شهرها را با گراف نمایش دهیم .
گراف حاصل جهتدار (directed) نیست. چراکه با احداث یک جاده بین هر دو شهر امکان رفتوآمد از هر دو شهر در این جاده وجود دارد.
به گراف بدون جهتداری متصل (connected) گفته میشود که .
مسیری بین هر دو جفت راس وجود داشته باشد.
اسلاید 8 :
الف) درختهای پوشای کمینه
چرخه ساده (simple cycle): .
در هر گراف بدون جهت، مسیری از یک راس به خودش است چنانچه .
حداقل شامل سه راس باشد و .
هیچ راس میانی تکراری نباشد.
گراف فاقدچرخه (Acyclic): گرافی غیرجهتدار است که .
هیچ چرخه سادهای در آن وجود نداشته باشد.
درخت (Tree) گرافی است .
غیرجهتدار (undirected)،
متصل (connected) و
فاقد چرخه (acyclic)
اسلاید 9 :
گراف متصل، غیرجهتدار و وزندار
اگر (v4,v5) را حذف کنیم این گراف همچنان متصل میماند.
درختی پوشا برای گراف بالا
درخت پوشای کمینه
اسلاید 10 :
الف) درختهای پوشای کمینه
این مساله به این صورت بیان میشود:
حذف یالهایی از یک گرافِ .
متصلِ
وزندارِ
غیرجهتدار
تا زیرگرافی بدست آید تا .
همچنان تمامی راسها متصل به هم باقی بمانند و
مجموع وزن یالهای باقیمانده کمینه گردد.
اسلاید 11 :
الف) درختهای پوشای کمینه
این مساله میتواند کاربردهای متعدد مانند:
ساخت جاده
در ایجاد شبکههای مخابراتی
در ایجاد شبکههای لولهگذاری و .
اسلاید 12 :
الف) درختهای پوشای کمینه
برای اینکه زیرگرافی شرایط گفتهشده را داشته باشد حتما بایستی .
درخت باشد. چراکه .
اگر زیرگرافی این شرایط را داشته باشد و درخت نباشد،
بنابراین در آن حداقل یک چرخه ساده وجود خواهد داشت که .
میتوانیم یکی از یالهای چرخه را حذف کنیم و گراف حاصل همچنان .
متصل با مجموع وزن یالهای کمتر باقی بماند
اسلاید 13 :
الف) درختهای پوشای کمینه
تعریف:
گراف بدون جهتِ G شامل .
مجموعه V از راسهای G و همچنین .
مجموعه E شامل یالها (که به صورت دو راس نشان داده میشود) میباشد.
اسلاید 14 :
الف) درختهای پوشای کمینه
به اعضای V با vi اشاره میکنیم و همچنین .
یال بین vi و vj را با .
(vi , vj ) نشان میدهیم.
اسلاید 15 :
الف) درختهای پوشای کمینه
اسلاید 16 :
الف) درختهای پوشای کمینه
درخت پوشای T برای G تعداد راسهای یکسان V همانند راسهای G دارد
ولی .
مجموعه یالهای آن (F)، زیر مجموعه E است.
بنابراین درخت پوشا را میتوانیم به صورت زیر نشان دهیم:
T=(V, F)
اسلاید 17 :
الف) درختهای پوشای کمینه
الگوریتم حریصانه سطح بالا
F = Ø // مجموعه یالها را با تهی مقدار دهی کن
while (the instance is not solved){
select an edge according to locally optimal consideration;
// روال انتخاب
if (adding the edge to F does not create a cycle)
add it; // امکانسنجی
if (T = (V, F) is a spanning tree) // بررسی راه حل
the instance is solved;
}
اسلاید 18 :
الف) درختهای پوشای کمینه- الگوریتم Prime
الگوریتم پرایم (Prime) با مجموعه تهی از F کار را شروع میکند.
مجوعه Y در این الگوریتم شامل راسهایی خواهد بود که به درخت پوشای کمینه اضافه شدهاند و
در ابتدا Y با راس دلخواهی مثلا {v1} مقداردهی اولیه میشود.
نزدیکترین راس به Y راسی است که
(1) عضو V-Y است و همچنین .
(2) به راسی که عضو Y است متصل است و
(3) این اتصال با راسی است که .
حداقل وزن را دارد.
اسلاید 19 :
الف) درختهای پوشای کمینه- الگوریتم Prime
در گراف شکل بالا، v2 نزدیکترین راس به Y، زمانیکه Y = {v1} میباشد.
نزدیکترین راس به Y و یال مربوطه به F اضافه میشود.
بنابراین در این حالت، v2 به Y و (v1, v2) به F افزوده میشود.
این فرایند افزودن نزدیکتر راس تا زمانیکه .
Y==V شود ادامه مییابد.
اسلاید 20 :
الف) درختهای پوشای کمینه- الگوریتم Prime
