تعیین درخت پوشای مینیمم با الگوریتم GPC ساخت اهرام جیزه در متلب

در این بخش سورس کد تعیین درخت پوشای مینیمم با الگوریتم GPC ساخت اهرام جیزه در متلب قرار داده شده است. درخت پوشای مینیمم درختی است از زیر مجموعه‌ای از گراف G که تمام رأس‌ها با حداقل تعداد ممکن لبه‌ها پوشیده شده است. از این رو، در درخت پوشای مینیمم حلقه‌ای وجود ندارد و همچنین نمی‌تواند قطع باشد. با استفاده از الگوریتم های فرا ابتکاری می‌توان، درخت پوشای مینیمم را تعیین نمود. یکی از این الگوریتم‌ها GPC یا الگوریتم ساخت اهرام جیزه می‌باشد که سورس کد کامل آن در این بخش آورده شده است.

درخت پوشای کمینه (مینیمم)

در نظریه گراف، درخت پوشا T، درختی است از یک گراف G کامل و بدون جهت و وزن دار که شامل تمام راس‌ها و حداقل یال‌ها می‌باشد. به بیان دیگر می‌توان گفت، درخت پوشای G درختی است که مجموعه‌ای از یال‌ها را شامل می‌شود که تمام رئوس را پوشش می‌دهد. در واقع تمام رئوس G در درخت پوشا وجود دارند به شرطی که هیچ حلقه یا دوری ایجاد نشود و درخت همبند نیز باشد. درخت پوشای کمینه (Minimum Spanning Tree) یک درخت پوشا است که داری کم‌ترین هزینه (مجموع هزینه یال‌ها) باشد.

با توجه به یک گراف متصل و بدون جهت، درخت پوشا از آن گراف یک زیرگرافی است که اولاً یک درخت است و تمام رأس‌ها را با یکدیگر متصل می‌کند. یک گراف می‌تواند انواع درخت‎‌های مختلف را پوشش دهد. یک Minimum Spanning Tree درخت پوشای کمینه (MST) یا درخت پوشای مینیمال برای یک گراف وزنم دار، متصل و بدون جهت یک درخت پوشا با وزن کمتر یا برابر با وزن هر درخت دیگر است. وزن یک درخت، مجموع وزن های داده شده به هر لبه درخت است.

الگوریتم ساخت اهرام جیزه

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

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

تعیین درخت پوشای مینیمم با الگوریتم GPC

در این سورس کد همانند دیگر روش‌های حل مسئله، با استفاده از توابع CostFun به تعیین درخت پوشای کمینه با استفاده از الگوریتم اهرام جیزه پرداخته شده است. پس از اجرای سورس کد، گراف به صورت خودکار شروع به طراحی می‌شود و در نهایت، در بهینه‌ترین حالت ممکن که قابل انجام با الگوریتم اهرام جیزه می‌باشد جابه جایی گره‌ها و طراحی گراف به اتمام می‌رسد. این سورس کد دارای ۷ فایل می‌باشد که فایل GPC.m فایل اصلی بوده و تمامی فراخوانی توابع و تعریف Iteration ها در این فایل انجام می‌گیرد.

در ادامه تصاویر خروجی سورس کد و همچنین ویدیو نحوه اجرای برنامه و خروجی آن قرار گرفته است. بخشی از سورس کد در زیر آورده شده است.

%% Problem Definition
model=CreateModel();
CostFunction=@(xhat) CostFun(xhat,model);        % Cost Function
nVar=model.n*(model.n-1)/2;             % Number of Decision Variables
VarSize=[1 nVar];   % Decision Variables Matrix Size
VarMin = -10;         % Decision Variables Lower Bound
VarMax = 10;         % Decision Variables Upper Bound
%% Giza Pyramids Construction (GPC) Parameters
MaxIteration=1000;   % Maximum Number of Iterations (Days of work)
nPop=100;             % Number of workers
G = 9.8;             % Gravity
Tetha = 14;          % Angle of Ramp

برای دریافت سورس کد کامل آن را خریداری نمایید.

تصاویر خروجی حل مسئله تعیین درخت پوشای مینیمم با الگوریتم GPC

تعیین درخت پوشای مینیمم با الگوریتم GPC ساخت اهرام جیزه در متلب

سورس کد تعیین درخت پوشای مینیمم با الگوریتم GPC ساخت اهرام جیزه در متلب در محیط Matlab 2017 نوشته و اجرا شده است و قابل اجرا با نسخه‌های بالاتر متلب نیز هست. این سورس کد توسط تیم پشتیبانی پی استور تست و اجرا شده است. کیفیت اثر توسط پی استور تضمین می‌شود و دارای نشان تضمین کیفیت پی استور است. برای دانلود این سورس کد آن را خریداری فرمایید به محض خرید لینک دانلود در دسترس خواهد بود.