پیاده‌سازی الگوریتم تقریبی گنزالس (K-center) به زبان پایتون
پیاده‌سازی الگوریتم تقریبی گنزالس (K-center) به زبان پایتون
عنوان: پیاده‌سازی الگوریتم تقریبی گنزالس (K-center) به زبان پایتون
توضیحات: در این پروژه، برنامه‌ای به زبان پایتون طراحی شده است که الگوریتم تقریبی مراکز بهینه (K-center) که اصطلاحا الگوریتم گنزالس نیز نامیده می‌شود را پیاده‌سازی می‌کند. علاوه بر این الگوریتم تقریبی، راه حل مسئله مراکز بهینه به روش فراگیر نیز پیاده شده است تا با مقایسه این دو، میزان تقریب را بتوان بررسی کرد. در مسئله مراکز بهینه، باید تعداد k راس از میان رئوس گراف را به گونه‌ای انتخاب کنیم که سایر رئوس گراف، کمترین فاصله را تا این راس‌ها داشته باشند.. این مسئله NP-hard است و برای حل آن الگوریتم تقریبی نیز پیشنهاد شده است. در این پروژه هر دو الگوریتم فراگیر و تقریبی برای حل این مسئله پیاده‌سازی شده است. در الگوریتم اول جواب دقیق مسئله با بررسی تمام حالات ممکن پیدا می‌شود که برای گراف‌های بزرگ بسیار زمان‌بر و پیچیده خواهد بود. اما در الگوریتم دوم یک پاسخ تقریبی برای این مسئله به دست می‌آید که ممکن است بهینه‌ترین رئوس نباشند، اما پیچیدگی کم آن باعث می‌شود از این نقص صرف نظر کنیم. در این برنامه، مشخصات گراف مورد نظر کاربر از یک فایل خوانده می‌شود و سپس هر دو الگوریتم اجرا می‌گردند. زمان اجرای هر کدام از این دو الگوریتم نیز به کاربر نمایش داده می‌شود. نمونه‌ای از خروجی این برنامه برای یک گراف با پنج راس به صورت زیر است: Result of brute force algorithm for k-center problem: [1, 2] The maximum distance is 3 and the execution time is 924 microseconds ********************************************************************** Result of approximation algorithm for k-center problem: [1, 4] The maximum distance is 4 and the execution time is 124 microseconds |
کلمات کلیدی: پایتون، مراکز بهینه، الگوریتم تقریبی، مقایسه، الگوریتم گنزالس
Python, K-center, Approximation algorithm, Comparison, Gonzalez’s algorithm
یارآموزان بزرگترین سامانه شبیه سازی با دراختیار داشتن اساتید مجرب، شبیه سازی پروژه های پژوهشی در تمامی رشته های فناوریاطلاعات و مهندسی کامپیوتر می باشد. برای ارتباط با ما از فرم تماس زیر و یا ایمیل اقدام فرمایید.
| Yaramoozan.ir@gmail.com | تماس با ما |
