دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ #C

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

 

رنگ آمیزی گراف 

در نظریه گراف، رنگ‌آمیزی گراف یکی از حالت‌های خاص مساله‌های برچسب گذاری گراف است و کاربرد زیادی در زمینه‌های عملی و تئوری گوناگون دارد. رویکرد کلی آن استفاده از نظیر کردن رنگهایی به یالها یا راس‌هاست که این رنگامیزی محدودیت خاصی را رعایت کند. در ساده‌ترین حالت، رنگ‌آمیزی‌ای مورد نظر است که در آن هیچ دو راس مجاوری که یک یال آنها را متصل میکند، هم رنگ نباشند(رنگامیزی راسها). علاوه بر آن رنگامیزی یالها به همین صورت تعریف میشود. از انجایی که یک طوقه نمی‌تواند این ویژگی را داشته باشد، این گراف‌ها باید بدون طوقه باشند.

استفاده از رنگ‌ها برای این رنگ آمیزی گراف به استفاده آنها در رنگ آمیزی نقشه بازمی‌گردد. چرا که از تعداد رنگ‌های کمی برای این منظور استفاده می‌کنیم. به طور طبیعی هر رنگ را متناظر یکی از اعداد طبیعی {...و3و2و1} در نظر می‌گیریم.

 

الگوریتم عقبگرد backtracking

تکنیک عقبگرد، شیوه ای در حل مسائل است که از علامت های خاصی برای بیان اینکه راه حل کاندیدی به حل مسئله می انجامد یا خیر استفاده می کند.این رویکرد برای حل مسائل درخت فضای آن مسئله را ایجاد کرده و تعیین میکند کدام گره امید بخش است. الگوریتم های عقب گرد، از تابلوها یا علامت هایی برای بیان اینکه یک راه حل کاندید به حل مسئله نمی انجامد استفاده میکند. عقبگرد، حالت اصلاح شده ی جستجوی عمقی یک درخت می باشد.

در حل مسئله رنگ آمیزی گراف می باشد.در این مسأله می خواهیم تمام راه های ممکن جهت رنگ آمیزی گره های یک گراف بدون جهت را با استفاده از حداکثر m رنگ متفاوت پیدا کنیم، به گونه ای که هیچ دو رأس مجاوری هم رنگ نباشند.

 

رنگ آمیزی راسی گراف به روش عقبگرد

رنگ آمیزی گراف به روش عقبگرد همان روش جستجوی عمقی است طوری که هیچ دو راس مجاور یکدیگر با هم همرنگ نباشند    

 

روش کار برنامه:

در طراحی این نرم افزار  از radio button برای هر راس استفاده شده است طوری که با drag  کردن آن به صفحه میتوان رئوس راتعیین کرد.

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

برای هر کدام از این کارها تابعی در برنامه نوشته شده است. 

در این برنامه همچنین تابعی برای رنگ آمیزی راس ها نوشته شده است بطوری که چک میکند رئوس متصل به هم دارای رنگ یکسان نباشند. 

در آخر کاربر با کلیلک روی دکمه "اجرای الگوریتم عقبگرد" رئوس طبق قاعده رنگ آمیزی میشوند و حداقل تعداد رنگهای لازم برای رنگ آمیزی مشخص میگردند.

 

لازم به ذکر است، توضیحات کامل در کدهای برنامه نیز نوشته شده است.

 

 

سورس پروژه هوش مصنوعی رنگ آمیزی گراف به روش عقبگرد را پس از پرداخت اینترنتی دانلود نمایید

حجم فایل : 180  KB