پیاده‌سازی الگوریتم تقریبی پوشش راسی (Vertex Cover) به زبان پایتون

بدون ديدگاه

 پیاده‌سازی الگوریتم تقریبی پوشش راسی
 (Vertex Cover) به زبان پایتون

عنوان: پیاده‌سازی الگوریتم تقریبی پوشش راسی (Vertex Cover) به زبان پایتون
توضیحات:

در این پروژه، برنامه‌ای به زبان پایتون طراحی شده است که الگوریتم تقریبی پوشش راسی (Vertex Cover) را پیاده‌سازی می‌کند. علاوه بر این الگوریتم تقریبی، راه حل مسئله پوشش راسی به روش فراگیر نیز پیاده‌سازی شده است تا با مقایسه  این دو، میزان تقریب را بتوان بررسی کرد.

در مسئله پوشش راسی، به دنبال پیدا کردن کوچک‌ترین زیرمجموعه از رئوس گراف هستیم که حداقل یکی از رئوس هر یال از گراف، در این مجموعه قرار داشته باشد. این مسئله NP-hard است و برای حل آن الگوریتم تقریبی نیز پیشنهاد شده است. در این پروژه هر دو الگوریتم فراگیر و تقریبی برای حل این مسئله پیاده‌سازی شده است. در الگوریتم اول جواب دقیق مسئله با بررسی تمام حالات ممکن پیدا می‌شود که برای گراف‌های بزرگ بسیار زمان‌بر و پیچیده خواهد بود. اما در الگوریتم دوم یک پاسخ تقریبی برای این مسئله به دست می‌آید که ممکن است کوچک‌ترین زیرمجموعه نباشد، اما پیچیدگی کم آن باعث می‌شود از این نقص صرف نظر کنیم.

در این برنامه، مشخصات گراف مورد نظر کاربر از یک فایل خوانده می‌شود و سپس هر دو الگوریتم اجرا می‌گردند. زمان اجرای هر کدام از این دو الگوریتم نیز به کاربر نمایش داده می‌شود. نمونه‌ای از خروجی این برنامه برای یک گراف با شش راس به صورت زیر است: Result of the brute force algorithm for vertex cover problem: [1, 3] Execution time is 26 microseconds ********************************************************************** Result of approximation algorithm for vertex cover problem: [1, 2, 3, 4] Execution time is 12 microseconds
  کلمات کلیدی: پایتون، پوشش راسی، الگوریتم تقریبی، مقایسه Python, Vertex cover, Approximation algorithm, Comparison

یارآموزان بزرگترین سامانه شبیه سازی با دراختیار داشتن اساتید مجرب، شبیه سازی پروژه های پژوهشی در تمامی رشته های فناوریاطلاعات و مهندسی کامپیوتر می باشد. برای ارتباط با ما از فرم تماس زیر و یا ایمیل اقدام فرمایید.

Yaramoozan.ir@gmail.comتماس با ما

نوشتن دیدگاه

نشانی ایمیل شما منتشر نخواهد شد.

نوزده − 13 =