حل مسئله 8 وزیر با الگوریتم SFS جستجوی فراکتال تصادفی در متلب

مسئله هشت وزیر

مسئله هشت وزیر از جمله مسائل کلاسیک در مباحث طراحی الگوریتم است که در حالت کلی‌تر با عنوان معمای n وزیر یا معمای چند وزیر مطرح می‌شود. وزیر یا Queen (که در بازی های بین المللی اصطلاحی هم نام با معنی اش یعنی ملکه دارد ولی در کشور ما از اصطلاح وزیر استفاده می شود) مهره‌ای از مهره‌های بازی شطرنج است که می‌تواند در تمامی هشت جهت به هر تعداد خانه (تا زمانی که مهره‌ای مانع نباشد) حرکت کند.

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

الگوریتم جستجوی فراکتال تصادفی

الگوریتم جستجوی فراکتال تصادفی Stochastic Fractal Search که به اختصار SFS نیز نامیده می شود یکی از الگوریتم های فرا ابتکاری مهم است که با الهام از پدیده طبیعی رشد (growth) به وجود آمده است. این الگوریتم فراابتکاری جدید ارائه شده است که از مفهومی ریاضی به نام فراکتال استفاده می کند. با استفاده از ویژگی انتشار (Diffusion) که به طور منظم در فراکتال‌های تصادفی دیده می‌شود، ذرات در الگوریتم ارائه شده، فضای جستجو را کارآمدتر جستجو می‌کنند.

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

فرکتال‌های تصادفی را می‌توان با اصلاح فرآیند تکرار از طریق قوانین تصادفی مانند خوشه‌های نفوذی (percolation clusters)، پیاده‌روی‌های خود اجتنابی (self-avoiding walks)، مناظر فراکتال (fractal landscapes)، مسیر حرکت براونی (trajectories of Brownian motion) و درخت براونی (Brownian tree) تولید کرد (دندریتی که با مدل‌سازی فراکتال‌های دندریتی تولید می‌شود).

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

حل مسئله 8 وزیر با الگوریتم SFS جستجوی فراکتال تصادفی در متلب

در علوم کامپیوتر، ممکن است مسائل متفاوتی برای حل کردن وجود داشته باشد. این مسائل که معمولاً مسائل سخت یا NP_hard هستند، برای حل آن ها از یک سری توابع و روش ها استفاده می شود که یکی از آن ها توابع برازش یا فیتنس (Fitness) است.

در حل مسئله 8 وزیر با الگوریتم SFS جستجوی فراکتال تصادفی نیز، از توابع Fitness استفاده شده است که به کمک کدهای الگوریتم جستجوی فراکتال تصادفی به بررسی و سپس حل مسئله 8 وزیر با یک تعداد وزیر مشخص به زبان متلب پرداخته است.

این سورس کد به طور کلی دارای 6 فایل است که فایل FSF.m کد اصلی بوده و فراخوانی توابع و تعیین تعداد وزیر مسئله در این سورس کد انجام می پذیرد. بخشی از سورس کد تابع فیتنس در زیر آورده شده است.

function out = Fitness(sol)
    [~,sol]=sort(sol);
    n=numel(sol);
    % Transform the input chromosome into the chess field 
    field = zeros(n,n);
    for i = 1:n
        field(sol(i),i) = 1;
    end

برای تهیه سورس کد کامل آن را خریداری نمایید. در ادامه خروجی مسئله با حل 15 وزیر و همچنین پیش نمایش ویدئویی اجرای سورس کد آورده شده است.

تصویر خروجی

ویدئو معرفی