پاورپوینت الگوریتمی دیگر با رویکرد حریصانه برای مسئله درخت پوشای کمینه (pptx) 14 اسلاید

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

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

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

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

اهداف درس این جلسه الگوریتمی دیگر با رویکرد حریصانه برای مساله درخت پوشای کمینه الگوریتمی حریصانه برای مساله کوتاه‌ترین مسیر الف) درخت‌های پوشای کمینه تعریف: گراف بدون جهتِ G شامل ... مجموعه V از راس‌های G و همچنین ... مجموعه E شامل یالها (که به صورت دو راس نشان داده می‌شود) می‌باشد. 3 الف) درخت‌های پوشای کمینه درخت پوشای T برای G تعداد راس‌های یکسان V همانند راس‌های G دارد ولی ... مجموعه یال‌های آن (F)، زیر مجموعه E است. بنابراین درخت پوشا را می‌توانیم به صورت زیر نشان دهیم: T=(V, F) 4 الف) درخت‌های پوشای کمینه- الگوریتم Kruskal در این روش به ازای هر vi عضو V یک زیرمجموعه مجزا ایجاد می‌شود که تنها شامل یک راس است. سپس یال‌ها که از قبل به ترتیب صعودی مرتب شده‌اند به ترتیب وارسی می‌شوند. چنانچه یالی دو راس در دو مجموعه جدا از هم را به هم متصل کند ... یال مربوطه به F اضافه شده و دو مجموعه که دو راس آن توسط یال به هم متصل شده بودند با هم ادغام می‌شوند. این فرایند تازمانیکه تمامی زیرمجموعه‌ها در یک مجموعه ادغام شوند ادامه می‌یابد. 5 الف) درخت‌های پوشای کمینه- الگوریتم Kruskal 6 الف) درخت‌های پوشای کمینه- الگوریتم Kruskal 7 الف) درخت‌های پوشای کمینه- الگوریتم Kruskal 8 ب) الگوریتم Dijkstra برای کوتاه‌ترین مسیر تک مبدا این الگوریتم هم از همان رویکرد الگوریتم پرایم برای مساله درخت پوشای کمینه استفاده می‌کند. مجموعه Y با راسی که کوتاه‌ترین مسیرها تا آن قرار است محاسبه شود مقداردهی اولیه می‌شود. در ادامه این راس v1 درنظر گرفته می‌شود. مجموعه F را برابر با مجموعه یال‌های موجود در کوتاه‌ترین مسیر از v1 به بقیه رئوس درنظر می‌گیریم که ... در شروع با تهی مقداردهی اولیه می‌شود. سپس راس v که نزدیکترین راس به v1 است را انتخاب می‌کنیم ... راس v را به Y و یال به F اضافه می‌کنیم. یال مسلما کوتاه‌ترین مسیر از v1 به v است. 9