حل مسائلي در گراف با استفاده از الگوريتم simulated annealing

---

شرح پروژه

قصد داريم با استفاده از الگوريتم simulated annealing مسائل زير را حل کنيم: الف) مساله clique به صورت زير تعريف مي شود: گرافي با n راس و m يال در اختيار داريم. ميخواهيم بزرگترين زيرگراف کامل اين گراف را بدست بياوريم. اين زيرگراف کامل Clique ناميده مي شود. با استفاده از الگوريتم simulated Annealing، برنامه اي بنويسيد که با دريافت يک گراف، Clique آن را بدست آورده و برگرداند. ورودي اين برنامه بک فايل input.txt بايد باشد.که در واقه ماتريس همسايگي گراف مورد نظر را نمايش مي دهد. به بياني، براي يک گراف با n راس فايل مورد نظر حاوي n خط بوده و در هر خط n مولفه صفر يا يک وجود دارد، يک بودن مولفه jام از خط iام به معني اتصال دو راس i و j خواهد بود، و صفر بودن اين مولفه به منزله نبودن يال بين دو راس مربوطه است. خروجي برنامه بک فايل به نام output.txt خواهد بود که هر خط آن شامل راس هاي يک clique پيدا شده است. لازم به يادآوري است که برنامه شما نبايد از خط فرمان، پارامتر يا اطلاعاتي بگيرد، تنها داده ورودي شما به مساله همان فايل input.txt است. براي تنظيم پارامترهاي مورد نظر، با اجراهاي متفاوت که ميتوانيد بهترين مقدار را براي آن تنظيم کنيد. و در گزارش خود نيز بهترين مقدار يا نمودارها يا نتايجي که بيانگر بهتر بودن اين مقدار (نسبت به ساير مقادير ) است را بياوريد. ب) مساله مجموعه هاي مجزا به صورت زير تعريف مي شود: گراف G و عدد K را در اختيار داريم، هدف يافتن مجموعه اي از k راس است که دو به دو مجزا بوده و با هم يالي ندارند. با استفاده از الگوريتم SA برنامه اي بنويسيد که با دريافت يک گراف، بزرگترين مجموعه مجزاي آن را بدست آورد. در اين قسمت نيز ورودي برنامه يک فايل input.txt بايد باشد که در واقع ماتريس همسايگي گراف مورد نظر را نشان مي دهد. و خروجي برنامه شما يک فايل به نام output.txt خواهد بود که شامل راس هاي بزرگترين مجموعه مجزاي گراف ورودي است. اگر گراف داراي بزرگترين مجموعه يکتا نباشد، يکي از آنها را به عنوان خروجي چاپ کند. در قسمت پياده سازي به علت ساده بودن، شما مجاز به استفاده از کتابخانه هاي موجود و کدهاي آماده نيستيد . روند اجراي برنامه را مشخص کنيد. مثلا براي اجرا، چه فايلي بايد بارگذاري شده و اين فايل در چه پوشه اي بايد باشد. اين بخش بايد کاملا واضح بوده و با خواندن آن به راحتي بتوان کد را اجرا و نتيجه گرفت.

این پروژه شامل 1 فایل مهم است، لطفا قبل از ارسال پیشنهاد حتما نسبت به بررسی این فایل اقدام فرمایید.

مهارت ها و تخصص های مورد نیاز

---

---