مسئله n وزیر (N-Queens Problem) یکی از مسائل کلاسیک در ریاضیات و علوم کامپیوتر است که به دلیل کاربردهای گسترده در هوش مصنوعی و بهینهسازی مورد توجه قرار گرفته است. این مسئله به بررسی قرار دادن n وزیر (Queens) روی یک صفحه شطرنج n×n به گونهای میپردازد که هیچ دو وزیری یکدیگر را تهدید نکنند. و اما مسئله 8 وزیر (8-Queens Problem) یک نمونه خاص از مسئله n وزیر است که در آن n = 8، یعنی شما باید 8 وزیر را روی یک صفحه شطرنج استاندارد 8×8 قرار دهید. یکی از بهترین روش های استفاده از الگوریتمهای فراابتکاری (Metaheuristic Algorithms) است.
تعریف مسئله
مسئله n وزیر چنین است:
- n وزیر باید به گونهای روی صفحه شطرنج قرار گیرند که:
- هیچ دو وزیر در یک ردیف (Row)، ستون (Column) یا قطر (Diagonal) مشترک نباشند.
- هدف یافتن تمامی چیدمانهای معتبر (Valid Configurations) یا حداقل یک چیدمان معتبر برای مسئله است.
ویژگیها و دشواریهای مسئله
- افزایش پیچیدگی: با افزایش مقدار n، تعداد حالات ممکن به شدت رشد میکند و حل مسئله برای مقادیر بزرگ n دشوارتر میشود.
- کاربردها: مسئله n وزیر نه تنها در ریاضیات بلکه در بهینهسازی، طراحی سیستمهای توزیعشده، زمانبندی و طراحی شبکهها کاربرد دارد.
روشهای حل مسئله
حل مسئله n وزیر به دو رویکرد اصلی تقسیم میشود:
- روشهای دقیق (Exact Methods):
- جستجوی عقبگرد (Backtracking): رویکرد متداول که با کاوش سیستماتیک فضای حالت، به دنبال چیدمانهای معتبر است.
- برنامهریزی خطی صحیح (Integer Linear Programming – ILP): مدلسازی مسئله به صورت یک برنامهریزی خطی و یافتن جواب با استفاده از روشهای ریاضی.
- روشهای تقریبی و فراابتکاری (Approximation and Metaheuristic Methods):
- برای مقادیر بزرگتر n، استفاده از این روشها بسیار مؤثر است.
حل مسئله n وزیر با الگوریتمهای فراابتکاری
الگوریتمهای فراابتکاری به دلیل توانایی بالا در کاوش فضای حالت و یافتن جوابهای نزدیک به بهینه، برای حل مسئله n وزیر بسیار کاربردی هستند. برخی از این الگوریتمها عبارتند از:
- الگوریتم ژنتیک (Genetic Algorithm – GA):
- شبیهسازی فرایند تکامل زیستی برای جستجوی چیدمانهای معتبر.
- کروموزومها نشاندهنده موقعیت وزیرها روی صفحه هستند.
- بهینهسازی ازدحام ذرات (Particle Swarm Optimization – PSO):
- استفاده از حرکت ذرات در فضای حالت برای یافتن چیدمانهای بدون برخورد.
- الگوریتم تبرید شبیهسازیشده (Simulated Annealing – SA):
- کاهش تدریجی دمای سیستم برای جستجوی فضای حالت و کاهش تعارضات بین وزیرها.
- جستجوی تابو (Tabu Search – TS):
- جلوگیری از جستجوی مجدد در نقاط مشابه فضای حالت برای تسریع فرآیند حل.
- الگوریتم مورچگان (Ant Colony Optimization – ACO):
- شبیهسازی رفتار مورچهها برای کاوش مسیرهای مناسب چیدمان وزیرها.
- الگوریتم جستجوی هارمونی (Harmony Search – HS):
- الگوریتمی الهامگرفته از فرایند نواختن موسیقی که میتواند برای حل مسائل ترتیبی مانند n وزیر استفاده شود.
کاربردها و اهمیت مسئله
مسئله n وزیر به دلیل ماهیت ترکیبیاتی و ساختار پیچیده، به عنوان یک مسئله استاندارد برای ارزیابی الگوریتمهای جستجو و بهینهسازی به کار میرود. حل این مسئله میتواند راهکارهایی برای مسائل مشابه در زمانبندی، تخصیص منابع، طراحی سیستمهای توزیعشده و حتی مسائل زیستی ارائه دهد.
در ادامه لیستی کاملی از بهترین الگوریتم های فراابتکاری برای حل مسئله TSP بررسی نمودهایم.
نویسنده: حسن سعادتمند
- بیش از 250 دوره آموزشی در MATLAB و پایتون.
- بیش از 15 سال تجربه در زمینه یادگیری ماشین، الگوریتم های فراابتکاری، یادگیری عمیق، مهندسی کنترل.
- چاپ چندین مقاله Q1 در بهترین ژرنال های دنیا Google Scholar.
- مدرس فرادرس
اطلاعات تماس:
- تلگرام: t.me/matlabanyone
- ایمیل: h.saadatmand22@yahoo.com
- یوتیوب: matlablearning
- تلفن: 09155137038
لیست الگوریتمهای مهم فراابتکاری از ابتدا تا سال 2025:
- الگوریتم ژنتیک (Genetic Algorithm – GA) – 1975
- الگوریتم تبرید شبیهسازی (Simulated Annealing – SA) – 1983
- جستجوی تابو (Tabu Search – TS) – 1986
- الگوریتم فرهنگی (Cultural Algorithm – CA) – 1991
- بهینهسازی کلونی مورچهها (Ant Colony Optimization – ACO) – 1992
- بهینهسازی ازدحام ذرات (Particle Swarm Optimization – PSO) – 1995
- تکامل تفاضلی (Differential Evolution – DE) – 1997
- جستجوی هارمونی (Harmony Search – HS) – 2001
- الگوریتم ازدحام ماهی (Fish Swarm – FS) – 2002
- الگوریتم زنبورها (Bees Algorithms – BA) – 2005
- کلونی زنبور عسل مصنوعی (Artificial Bee Colony – ABC) – 2005
- الگوریتم قورباغه (Shuffled Frog Leaping Algorithm – SFLA) – 2006
- الگوریتم رقابت استعماری (Imperialist Competitive Algorithm – ICA) – 2007
- الگوریتم کرم شبتاب (Firefly Algorithm – FA) – 2008
- الگوریتم جغرافیای زیستی (Biogeography-based Optimization – BBO) – 2009
- الگوریتم جستجوی گرانشی (Gravitational Search Algorithm – GSA) – 2009
- جستجوی فاخته (Cuckoo Search – CS) – 2009
- الگوریتم خفاش (Bat Algorithm – BA) – 2010
- الگوریتم علف هرز (Invasive Weed Optimization – IWO) – 2011
- الگوریتم بهینهسازی ایده پردازی (Brain Storm Optimization – BSO) – 2011
- الگوریتم بهینهسازی فاخته (Cuckoo Optimization Algorithm – COA) – 2011
- الگوریتم آموزش و یادگیری (Teaching–Learning-Based Optimization – TLBO) – 2011
- الگوریتم سیاهچاله (Black Hole – BA) – 2013
- بهینهسازی گرگ خاکستری (Grey Wolf Optimizer – GWO) – 2014
- الگوریتم گردهافشانی گل (Flower Pollination Algorithm – FPA) – 2014
- الگوریتم جستجوی فراکتال تصادفی (Stochastic Fractal Search – SFS) – 2015
- الگوریتم شیر مورچه (Ant Lion Optimizer – ALO) – 2015
- الگوریتم سنجاقک (Dragonfly Algorithm – DA) – 2015
- الگوریتم شمع پروانه (Moth-Flame Optimization – MFO) – 2015
- الگوریتم بهینهسازی پروانه سلطنتی (Monarch Butterfly Optimization – MBO) – 2015
- الگوریتم ازدحام پرندگان (Bird Swarm Optimization Algorithm – BSOA) – 2015
- الگوریتم کلاغ (Crow Search Algorithm – CSA) – 2016
- الگوریتم سینوس کسینوس (Sine Cosine Algorithm – SCA) – 2016
- الگوریتم جستجوی پروانه (Moth Search Algorithm – MSA) – 2016
- الگوریتم جایا (Jaya Algorithm – JA) – 2016
- الگوریتم بهینهسازی کرم (Glowworm Swarm Optimization – GSO) – 2016
- الگوریتم بهینهساز چند-نظمی (Multi-Verse Optimizer – MVO) – 2016
- الگوریتم پشه (Mosquito Flying Optimization – MFO) – 2016
- الگوریتم وال (نهنگ) (Whale Optimization Algorithm – WOA) – 2016
- الگوریتم سالپ (Slap Swarm Algorithm – SSA) – 2017
- الگوریتم بهینهساز کفتار خالدار (Spotted Hyena Optimizer – SHO) – 2017
- الگوریتم بهینهسازی پروانه و زنبور (Butterfly Optimization Algorithm with Bee – BOAB) – 2017
- الگوریتم ملخ (Grasshopper Optimization Algorithm – GOA) – 2017
- الگوریتم رشد درخت (Tree Growth Algorithm – TGA) – 2018
- الگوریتم پنگوئن امپراتور (Emperor penguin optimizer – EPO) – 2018
- الگوریتم شاهین هریس (Harris Hawks Optimization – HHO) – 2019
- الگوریتم گوزن قرمز (Red Deer Algorithm – RDA) – 2019
- الگوریتم بهینهسازی فقیر و غنی (Poor and Rich Optimization – PRO) – 2019
- الگوریتم مسیریاب (Pathfinder Algorithm – PFA) – 2019
- الگوریتم بهینهسازی اتم (Atom Search Optimization – ASO) – 2019
- الگوریتم ازدحام دلفینها (Dolphin Swarm Algorithm – DSA) – 2019
- الگوریتم بهینهسازی ارشمیدس (Archimedes Optimization Algorithm – AOA) – 2020
- الگوریتم کپک لجن (Slime Mould Algorithm – SMA) – 2020
- الگوریتم اسب وحشی (Wild Horse Optimizer Algorithm – WHOA) – 2020
- الگوریتم سفره ماهی (Manta Ray Foraging Optimization – MRFO) – 2020
- الگوریتم عقاب طلایی (Golden Eagle Optimizer – GEO) – 2020
- الگوریتم کانگورو (Kangaroo Optimization – KO) – 2020
- الگوریتم بهینهسازی اکوسیستم مصنوعی (Artificial Ecosystem-Based Optimization – AEO) – 2020
- الگوریتم عنکبوت اجتماعی (Social Spider Optimization – SSO) – 2020
- الگوریتم شکارچیان دریایی (Marine Predators Algorithm – MPA) – 2020
- بهینهساز نقاشی تصادفی (Stochastic Paint Optimizer – SPO) – 2020
- الگوریتم بهینهسازی مبتنی بر روانشناسی دانشآموزان (Student Psychology Based Optimization Algorithm) – 2020
- الگوریتم مبتنی بر اشتراک و کسب دانش (Gaining-Sharing Knowledge Based Algorithm) – 2020
- الگوریتم فیل (Elephant Herding Optimization – EHO) – 2021
- الگوریتم گله اسب (Horse herd Optimization Algorithm – HOA) – 2021
- الگوریتم جستجوی اجتماعی (Social Network Search – SNS) – 2021
- الگوریتم عقاب (Bald Eagle Search Optimization – BES) – 2021
- الگوریتم بهینهسازی خروسها (Roosters Algorithm – RA) – 2021
- الگوریتم بهینهسازی کرکسهای آفریقایی (African Vultures Optimization Algorithm – AVOA) – 2021
- بهینهسازی بازی آشوب (Chaos Game Optimization – CGO) – 2021
- الگوریتم حسابی (The Arithmetic Optimization Algorithm – AOA) – 2021
- الگوریتم بهینهسازی گرادیان (Gradient Based Optimization – GBO) – 2021
- الگوریتم مار (Snake Optimizer – SO) – 2022
- الگوریتم غزال (Gazelle Optimization Algorithm – GOA) – 2022
- الگوریتم بهینهسازی خرگوشها (Artificial Rabbits Optimization – ARO) – 2022
- الگوریتم بهینهسازی ازدحام گربه شنی (Sand Cat Swarm Optimization – SCSO) – 2022
- الگوریتم بهینهسازی سوسک (Cockroach Swarm Optimization – CSO) – 2022
- الگوریتم بهینهسازی زنبور عسل مصنوعی بهبود یافته (Improved Artificial Bee Colony Algorithm – IABC) – 2022
- الگوریتم علی بابا و چهل دزد (Alibaba and the Forty Thieves – AFT) – 2022
- الگوریتم بهینهسازی سارها (Starling Murmuration Optimizer – SMO) – 2022
- الگوریتم بهینهسازی غزال کوهستان (Mountain Gazelle Optimizer – MGO) – 2022
- الگوریتم جستجوی بهینهسازی ابولا (Ebola Optimization Search – EOS) – 2022
- الگوریتم جستجوی طلایی (Golden Search Optimization Algorithm – GSA) – 2022
- الگوریتم بهینهسازی درخت (Tree Optimization Algorithm – TOA) – 2022
- الگوریتم گورکن عسل (Honey Badger Algorithm – HBA) – 2022
- الگوریتم جستجوی خزنده (Reptile Search Algorithm – RSA) – 2022
- الگوریتم بهینهسازی موشخرمای کوتوله (Dwarf Mongoose Optimization Algorithm) – 2022
- بهینهساز فندقشکن (Nutcracker Optimizer) – 2023
- الگوریتم قانون فیک (Fick’s Law Algorithm) – 2023
- الگوریتم نهنگ بهبود یافته (Improved Whale Optimization Algorithm – IWOA) – 2023
- الگوریتم بهینهسازی حافظه انسان (Human Memory Optimization Algorithm – HMOA) – 2023
- الگوریتم بهینهسازی تیرانوسور (Tyrannosaurus Optimization Algorithm – TOA) – 2023
- الگوریتم Coati Optimization Algorithm (COA) – 2023
- الگوریتم Crayfish Optimization Algorithm (COA) – 2023
- الگوریتم خواب عمیق (The Deep Sleep Optimizer – DSO) – 2023
- الگوریتم بهینهسازی شکار گوزنها (Deer Hunting Optimization Algorithm – DHOA) – 2024
- الگوریتم بهینهسازی اسب آبی (Hippopotamus Optimization Algorithm – HOA) – 2024
- بهینهسازی گروه جوجهها (Chickens Swarm Optimization – CSO) – 2024
- الگوریتم کروکدیل (Crocodile Optimization Algorithm – COA) – 2024
- الگوریتم یوزپلنگ (Puma Optimizer – PO) – 2024
- الگوریتم هایکینگ (Hiking Optimization Algorithm – HOA) – 2024
- الگوریتم بهینهسازی درونیابی درجه دوم (Quadratic Interpolation Optimization – QIO) – 2023
- الگوریتم پروتوزوای مصنوعی (Artificial Protozoa Optimizer – APO) – 2024
- الگوریتم مارماهی و هامور (Eel and Grouper Optimizer – EGO) – 2024
- الگوریتم خرگوش نیشکر بزرگ (Greater Cane Rat Algorithm – GCRA) – 2024
- الگوریتم کوید (COVIDOA) – 2024
- الگوریتم جستوجوی پنگوئن ها (Penguins Search Optimization Algorithm -PeSOA) – 2024
- الگوریتم نهنگ قاتل (Killer Whale Algorithm – KWA) – 2024
- الگوریتم ستاره دریایی (Starfish Optimization Algorithm – SFOA) – 2025
- الگوریتم روباه قطبی (Arctic Fox Optimization – AFO) – 2025
کپی با ذکر نام سایت (www.matlablearning.com) مجاز است.
نقد و بررسیها
هنوز بررسیای ثبت نشده است.