پاورپوینت درباره روش حریصانه

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

فرمت فایل :powerpoint (لینک دانلود پایین صفحه) تعداد صفحات 65  صفحه

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

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

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

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

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

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

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

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

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

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

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

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

متصلِ

وزن‌دارِ

غیرجهت‌دار

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

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

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

الگوریتم پرایم (Prime) با مجموعه تهی از F کار را شروع می‌کند.

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

در ابتدا Y با راس دلخواهی مثلا {v1} مقداردهی اولیه می‌شود.

نزدیکترین راس به Y راسی است که

(1) عضو V-Y است و همچنین ...

(2) به راسی که عضو Y است متصل است و

(3) این اتصال با راسی است که ...

حداقل وزن را دارد.

کوئیز از جلسه قبل)

گراف وزن دار زیر مفروض است. درخت پوشای کمینه حاصل از اجرای الگوریتم Prime بر روی این گراف را رسم کنید. برای این کار در شش گام مقادیر بردارهای instances و nearest را که در الگوریتم آمده است را نشان دهید.