پاورپوینت رهيافت حريصانه

توضیحات محصول

دانلود پاورپوینت رهيافت حريصانه با فرمت ppt ودر 79 اسلاید قابل ویرایش

قسمتی از متن پاورپوینت رهيافت حريصانه

ايده

•رهيافت اسكروج
•عناصر داده اي را به ترتيب انتخاب كن، هر بار «بهترين» انتخاب را انجام بده، بدون توجه به انتخاب هاي قبلي و انتخاب هايي كه در آينده انجام خواهند گرفت.
•اغلب در مسائل بهينه سازي بكار مي رود. (مانند برنامه نويسي پويا)
•تقسیم به نمونه های کوچکتر صورت نمی گیرد.
•بايد مشخص شود كه با دنباله اي از راه حل هاي بهينه محلي، يك راه حل بهينه سراسري بدست مي آيد.

اضافه كردن يك عنصر به مجموعه
•روال انتخاب، عنصر بعدي را كه بايد به مجموعه اضافه شود، انتخاب مي كند. انتخاب براساس يك ملاك حريصانه انجام مي شود كه برخي شرايط بهينه محلي را در زمان انتخاب برآورده مي سازد.
•بررسي امكان سنجي، تعيين مي كند كه آيا مجموعه جديد براي رسيدن به حل نمونه عملي است يا خير.
•بررسي راه حل، بررسي مي كند كه آيا مجموعه جديد، راه حلي براي نمونه مساله مي باشد يا خير.

درخت هاي پوشاي كمينه (MST)

•برخي اصطلاحات:
–گراف بدون جهت
–مسير
–گراف همبند(متصل)
–دور ساده
–گراف بدون دور
–درخت
–درخت ريشه دار

درخت پوشاي كمينه
•درخت پوشا
•درخت پوشاي كمينه
•تعريف رسمي گراف بدون جهت
تعريف:

يك گراف بدون جهت G شامل يك مجموعه متناهي و غير تهي V مي باشد كه عناصر آن را رئوس گراف G مي ناميم، به همراه مجموعه E كه شامل مجموعه اي از زوج رئوس (يال) در V مي باشد.

G = (V, E)

پيچيدگي زماني براي همه حالات

•عمل اصلي: در حلقه repeat دو حلقه وجود دارد كه هر يك از آنها (n – 1) بار تكرار مي شود، اجراي دستورات داخل هريك از آنها را مي توان به عنوان يك بار اجراي عمل اصلي در نظر گرفت.
•اندازه ورودي: n، تعداد رئوس
•پيچيدگي زماني:
چون حلقه repeat به تعداد (n –1) بار تكرار مي شود، پيچيدگي زماني برابر است با:

T(n) = 2(n – 1)(n – 1) = Q(n2)

قضيه 4-1 - الگوريتم پريم همواره يك درخت پوشاي كمينه ايجاد مي كند.

اثبات: براي آنكه نشان دهيم F پس از هر بار تكرار حلقه repeat اميد بخش است از استقراء استفاده مي كنيم.

مبناي استقراء: واضح است كه مجموعه Æ اميد بخش است.

فرض استقراء: فرض كنيد پس از يك بار تكرار حلقه repeat مجموعه يال هاي بدست آمده F اميد بخش است.

گام استقراء: بايد نشان دهيم مجموعه F È {e} كه e يال انتخابي در تكرار بعدي است، اميد بخش است. چون يال e كمينه است و يك راس از V را به راسي در V – F متصل مي كند، طبق لم 4.1 نتيجه مي گيريم كه È {e} F اميد بخش مي باشد.

بنابراين مجموعه نهايي F اميد بخش مي باشد و چون شامل يال هاي يك درخت مي باشد، آن درخت بايد يك درخت پوشاي كمينه باشد.