پاورپوینت رهيافت حريصانه (pptx) 79 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 79 اسلاید

قسمتی از متن PowerPoint (.pptx) :

فصل چهارمرهيافت حريصانهGreedy Approach A.D MT. Kheirabadi 2 ايده رهيافت اسكروج عناصر داده اي را به ترتيب انتخاب كن، هر بار «بهترين» انتخاب را انجام بده، بدون توجه به انتخاب هاي قبلي و انتخاب هايي كه در آينده انجام خواهند گرفت. اغلب در مسائل بهينه سازي بكار مي رود. (مانند برنامه نويسي پويا) تقسیم به نمونه های کوچکتر صورت نمی گیرد. بايد مشخص شود كه با دنباله اي از راه حل هاي بهينه محلي، يك راه حل بهينه سراسري بدست مي آيد. A.D MT. Kheirabadi 3 مثال: باقيمانده پول A.D MT. Kheirabadi 4 الگوريتم A.D MT. Kheirabadi 5 شکست رهيافت حريصانه A.D MT. Kheirabadi 6 اضافه كردن يك عنصر به مجموعه روال انتخاب، عنصر بعدي را كه بايد به مجموعه اضافه شود، انتخاب مي كند. انتخاب براساس يك ملاك حريصانه انجام مي شود كه برخي شرايط بهينه محلي را در زمان انتخاب برآورده مي سازد. بررسي امكان سنجي، تعيين مي كند كه آيا مجموعه جديد براي رسيدن به حل نمونه عملي است يا خير. بررسي راه حل، بررسي مي كند كه آيا مجموعه جديد، راه حلي براي نمونه مساله مي باشد يا خير. A.D MT. Kheirabadi 7 درخت هاي پوشاي كمينه (MST) برخي اصطلاحات: گراف بدون جهت مسير گراف همبند(متصل) دور ساده گراف بدون دور درخت درخت ريشه دار A.D MT. Kheirabadi 8 مثال ها A.D MT. Kheirabadi 9 درخت پوشاي كمينه درخت پوشا درخت پوشاي كمينه تعريف رسمي گراف بدون جهت تعريف: يك گراف بدون جهت G شامل يك مجموعه متناهي و غير تهي V مي باشد كه عناصر آن را رئوس گراف G مي ناميم، به همراه مجموعه E كه شامل مجموعه اي از زوج رئوس (يال) در V مي باشد. G = (V, E)