Loading...
بهبود نتایج درخت پوشای کمینه با الگوریتم ژنتیک تطبیقی
در این پست پروژه بهبود نتایج درخت پوشای کمینه با الگوریتم ژنتیک تطبیقی (Adaptive Genetic Algorithm) در متلب را آماده کرده ایم که به توضیحاتی در رابطه با درخت پوشای کمینه پرداخته و فیلم خروجی این پروژه قرار داده شده است.
درخت های پوشای کمینه (Minimum Spanning Trees):
فرض کنید که در برنامه ریزی احداث جاده بین شهرها، می خواهیم تعدادی شهر را با جاده به هم وصل کنیم تا امکان رفتن از هر شهر به شهر دیگر با جاده های احداث شده ممکن شود. چنانچه بحث محدودیت بودجه ای مطرح باشد، بنابراین در این برنامه ریزی می خواهیم حداقل جاده را از نظر طولی احداث کنیم. در ادامه به دنبال الگوریتمی هستیم که مسائلی از این قبیل را حل کند.
اگر ارتباط بین شهرها را با گراف نمایش دهیم، گراف حاصل جهت دار (directed) نیست. چرا که با احداث یک جاده بین هر دو شهر امکان رفت و آمد از هر دو شهر در این جاده وجود دارد. در هر گراف بدون جهت، مسیر عبارت است از دنباله ای از راس ها که بین هر راس و راس بعدی آن یالی وجود داشته باشد. به گراف بدون جهت داری متصل (connected) گفته می شود که مسیری بین هر دو جفت راس وجود داشته باشد.
توضیحات بیشتر و مشاهده فیلم خروجی پروژه بهبود نتایج درخت پوشای کمینه با الگوریتم ژنتیک تطبیقی در ادامه مطلب.
چرخه ساده در درخت پوشای کمینه (simple cycle):
در هر گراف بدون جهت، مسیری از یک راس به خودش است، چنانچه حداقل شامل سه راس باشد و هیچ راس میانی تکراری نباشد.
گراف فاقد چرخه در درخت پوشای کمینه (Acyclic):
گراف فاقد چرخه گرافی غیرجهت دار است که هیچ چرخه ساده ای در آن وجود نداشته باشد. درخت (Tree) گرافی است، غیرجهت دار (undirected)، متصل (connected) و فاقد چرخه (acyclic).
این مساله به این صورت بیان می شود:
حذف یال هایی از یک گراف متصل، وزن دار و غیرجهت دار که زیرگرافی بدست آید تا همچنان تمامی راس ها متصل به هم باقی بمانند و مجموع وزن یال های باقی مانده کمینه گردد.
این مساله می تواند کاربردهای متعددی داشته باشد، مانند: ساخت جاده، ایجاد شبکه های مخابراتی، ایجاد شبکه های لوله گذاری و …
برای اینکه زیرگرافی شرایط گفته شده را داشته باشد حتما باید درخت باشد. چرا که اگر زیرگرافی این شرایط را داشته باشد و درخت نباشد، بنابراین در آن حداقل یک چرخه ساده وجود خواهد داشت که می توانیم یکی از یال های چرخه را حذف کنیم و گراف حاصل همچنان متصل با مجموع وزن یال های کمتر باقی بماند.
انجام پروژه ها و شبیه سازی مقالات و پایان نامه ها با متلب
پروژه ها و آموزش های برنامه نویسی
مشاهده ویدئو در این باره
سلام من این پروژرو از شما خرید کردم ولی متاسفانه تو اجراش دچار مشکل شدم میشه کمی راهنماییم کنید ؟ ممنون
دوست عزیز لطفا تصویر خطا را ارسال کنید تا بررسی شود البته دقت شود که ما از ورژن 2013a استفاده کردیم.
سلام من یه پروژه دارم که ناقصه می خواستم برام کاملش کنید اگه وقت داشته باشید براتون ایمیل کنم بررسی کنید ببنید قابل انجامه یا نه ؟
آقا حمید مشکلی نیست ارسال کنید تا بررسی کنیم سعی میکنیم تا آخر امشب خبر بدیم
با عرض سلام و خسته نباشید خدمت دوستان می خواستم روند کار این پروژرو برام تغییر بدید وقت دارید ؟ این تغییرات چقدر زمان میبره لطفا می تونید کارمو زود راه بندازید .
مشکلی نیست قابل تغییر است
برای پیدا کردن درخت پوشای کمینه از یک گراف به روش الگوریتم ژنتیک باید چه جوری کروموزومها رو انتخاب کنیم؟