بایگانی برچسب برای: l;hati hd

مسئله فروشنده دوره‌گرد

 اگر فروشنده دوره گرد از نقطه A شروع کند و فواصل بین نقاط مشخص باشد، کوتاه‌تربن مسیر که از تمام نقاط یکبار بازدید می‌کند و به A بازمی‌گردد کدام است؟

مسئله فروشنده دوره گرد (به انگلیسی: Travelling salesman problem، به‌اختصار: TSP) مسئله‌ای مشهور است که ابتدا در سده ۱۸مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثلکارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.

شرح مسئله بدین شکل است:

تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاً یکبار عبور کند و به شهر شروع برگردد.

 

مسئله فروشنده دوره گرد

تعداد جواب‌های شدنی مسئله، برابر است با {\displaystyle {\frac {1}{2}}(n-1)!}{\displaystyle {\frac {1}{2}}(n-1)!} برای n>۲ که n تعداد شهرها می‌باشد. در واقع این عدد برابر است با تعداددورهای همیلتونی در یک گراف کامل با n رأس.

مسئله‌های مرتبط

مسئله فروشنده دوره گرد یا Traveling Salesman Problem (به اختصار TSP)، یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات است.

سه روش کلی برای کد کردن راه حل‌های مسئله TSP ارائه شده‌است که در الگوریتم‌های مختلفی قابل استفاده هستند. راه حل‌های سه گاه عبارتند از:

الف) نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتم‌های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms (به اختصار GA) شبیه‌سازی تبرید یا Simulated Annealing (به اختصار SA) جستجوی ممنوعه یا Tabu Search (به اختصار TS) جستجوی همسایگی متغیر یا Variable Neighborhood Search (به اختصار VNS) بهینه‌سازی کلونی مورچگان یا Ant Colony Optimization (به اختصار ACO) جستجوی هارمونی یا Harmony Search (به اختصار HS) و سایر الگوریتم‌های بهینه‌سازی گسسته

ب) نمایش جواب به صورت کلیدهای تصادفی یا Random Key که در الگوریتم‌های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms (به اختصار GA) بهینه‌سازی ازدحام ذرات یا Particle Swarm Optimization (به اختصار PSO) الگوریتم رقابت استعماری یا Imperialist Competitive Algorithm (به اختصار ICA) تکامل تفاضلی یا Differential Evolution (به اختصار DE) بهینه‌سازی مبتنی بر جغرافیای زیستی یا Bio-geography Based Optimization (به اختصار BBO) استراتژی‌های تکاملی یا Evolution Strategies (به اختصار ES) برنامه‌ریزی تکاملی یا Evolutionary Programming (به اختصار EP) و سایر الگوریتم‌های بهینه‌سازی پیوسته

پ) نمایش جواب به شکل ماتریس‌های شبیه فرومون که توسط تمامی الگوریتم‌های اشاره شده در مورد (ب) قابل استفاده می‌باشد.

  • مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
  • مسئله تنگراه فروشنده دوره‌گرد (به انگلیسی: Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP) مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
  • تعمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاً از یک شهر عبور کند. این مسئله به «مسئله سیاست‌مدار مسافر» نیز شهرت دارد.

الگوریتم‌ها

مسئله فروشنده دوره گرد جزء مسائل ان‌پی سخت است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:

  • طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آن‌ها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
  • استفاده از الگوریتم‌های مکاشفه‌ای که جواب‌هایی به‌دست می‌دهد که احتمالاً درست هستند.
  • پیدا کردن زیرمسئله‌هایی از مسئله یا به عبارت دیگر تقسیم مسئله به مسئله‌های کوچکتر، تا بتوان الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه داد.

الگوریتم‌های دقیق

سرراست‌ترین راه حل امتحان کردن تمامی جایگشتهای ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. با استفاده از برنامه‌نویسی پویا مسئله می‌تواند با مرتبه زمانی{\displaystyle n^{2}2^{n}}{\displaystyle n^{2}2^{n}} حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است.

الگوریتم‌های مکاشفه‌ای

الگوریتم‌های تقریبی متنوعی وجود دارند که خیلی سریع جواب‌های درست را با احتمال بالا به‌دست می‌دهند که می‌توان آن‌ها را به صورت زیر دسته‌بندی کرد:

  • مکاشفه‌ای سازنده
  • بهبود تکراری
    • مبادله دوبه‌دو
    • مکاشفه‌ای k-opt
    • مکاشفه‌ای V-opt
  • بهبود تصادفی

پیچیدگی محاسباتی الگوریتم فروشنده دوره گرد

این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل می‌شود اما اگر به روش برنامه‌نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن (O(n^2*2^n خواهد شد که جز مرتبه‌های نمایی است. باید توجه داشت علی‌رغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می‌باشد. شبه کد الگوریتم فوق به صورت زیر است که در آن تعداد زیر مجموعه‌های یک مجموعه n عضوی ۲ به توان n می‌باشد و for اول یک ضریب n را نیز حاصل می‌شود که به ازای تمام شهرهای غیر مبدأ می‌باشد و حاصل (n*(2^n را پدیدمی‌آورد؛ بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه n داریم که در زمان فوق نیز ضرب می‌شود و در نهایت زمان (n^2)*(2^n) را برای این الگوریتم حاصل می‌کند.

 

C({1},1) = 0
  for (S=2 to n)
  for All Subsets S subset of {1,2,3,...} of size S and containing1
  C(S,1) = &
  for All J member of S , J<>1
  C (S , J) = min { C (S - { J } , i) + D i,J: i member of S , i <> J }
 return min j C ({1 . . . n}, J) + D J,1

 

شبه کد مسئله فروشنده دوره گرد

مسئله:یک تور بهینه برای یک گراف وزن دار و جهت دار مشخص نمایید. وزن‌ها اعدادی غیر منفی هستند

ورودی:یک گراف وزن دار و جهت دار و n تعداد گره‌های گراف. گراف با یک ارائه دو بعدی w مشخص می‌شود که سطرها و ستون‌هایش از ۱ تا n شاخص دهی شده‌اند و در ان [w[i][j معرف وزن لبه از گره iام به گره jام است.۴

خروجی:یک متغیر minlength که مقدار ان طول تور بهینه است و یک ارائه دو بعدی p که یک تور بهینه را از روی ان می‌توان ساخت . سطرهای p از ۱ تا n و ستونهای ان با تمامی زیر مجموعه‌های {v-{v1 شاخص دهی شده‌اند . [P[i][A شاخص اولین گره بعد از vi بر روی کوتاهترین مسیر از viتاvj است که از تمام گره‌های A دقیقاً یکبار می‌گذرد.

 

* Void travel ( int n ,
 *              const number W[][],
 * index p[][],
 * number&minlength
* )
* {
* Index i, j, k;
* number D[1..n][subset of V-{vi}];
* for (i= 2 ; i<=n;i++)
* D[i][∅} = w[i][1];
* for(k=1; k<=n-2 ; k++)
* for (all subsets A v-{v1} containing k vertices
* for (i such that j≠1 and vi is not in A){
* D[i][A] = minimum (W[i][j]+ D[vj][A-{vj}]);
* P[i][A]= value of j that gave the minimum
* }
* D[1][v-{vi}]= minimum (W[1][j]+ D[vj][V-{v1}];
* P[1][V-{v1}]= value of j that gave the minimum ;
* Minlength = D[1][V-{v1}];
* }

 

الگوریتم جستجوی ممنوعه یا Tabu Search یا به اختصار TS، یکی از قوی‌ترین الگوریتم‌ها در زمینه حل مسائل بهینه‌سازی، به خصوص مسائل بهینه‌سازی مبتنی بر گراف و مسائل بهینه‌سازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباً یکی از مسائلی که برای حل آن‌ها از الگوریتم TS استفاده می‌شود، مسئله فروشنده دوره گرد یا TSP است. این الگوریتم پاسخ‌های بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسئله TSP ارائه می‌کند!

منبع


 

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

این مسئله علاوه بر جنبه نظری از جنبه عملی نیز کاربرد فراوانی دارد به عنوان مثال در مواردی مانند مسیریابی، ساخت تراشه های الکترونیکی، زمان بندی کارها و غیره مورد استفاده قرار گیرد. اما  در مواجهه با چالش حل مسائل بهینه سازی، که این نوع مسائل در دنیای واقعی بسیار زیاد هستند، روش های کلاسیک اغلب با مشکل مواجه می شوند. به همین دلیل معمولا از روشهای فرا ابتکاری همانند الگوریتم ژنتیک و سایر الگوریتم های تکاملی برای حل این نوع مسائل استفاده میشود

 

به صورت کلی مسئله فروشنده دوره گرد دارای 3 حالت زیر می باشد.

1-    فروشنده دوره گرد متقارن

در حالت متقارن مسئله، تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم .مطلوب است کم ‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقا یکبار عبور کند و به شهر شروع بازگردد.

2-   فروشنده دوره گرد نامتقارن

مسأله ­ي فروشنده ­ي دوره­ گرد نامتقارن, یک TSP است که فاصله بين رئوس آن, متقارن نيست. ATSP بسيار مشکل­تر از TSP است، در حقيقت در حالي که TSP متقارن, حتي در گراف­هاي با چندين هزار  رأس, به طور بهينه, قابل حل است, تنها نمونه­هاي خاصي ازATSP را که ماتريس فاصله­ي آنها, تقريباً متقارن است, تنها در گراف­هاي داراي چندين دوجين رأس, مي­توان به طور بهينه حل کرد. به کاربردن هوش مصنوعی  براي ATSP, راحت­ و سر راست است. چون هيچ تغييراتي در الگوريتم اصلي, لازم ندارد. پيچيدگي محاسباتي در حلقه­ي الگوريتم, برنامه­ي کاربردي TSP, يکسان است, زيرا تنها تفاوت آنها در فاصله­ها و ماتريس­هاي ردپا است که در اينجا ديگر متقارن نيستند.

3-   فروشنده دوره گرد با پنجره های زمانی

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

 

مسئله چند وزیر یک معمای شطرنجی و ریاضیاتی است که بر اساس آن باید n وزیر شطرنج در یک صفحه n×n شطرنج به‌گونه‌ای قرار داده شوند که هیچ‌یک زیر ضرب دیگری نباشند. با توجه به اینکه وزیر به‌صورت افقی، عمودی و اُریب حرکت می‌کند، باید هر وزیر را در طول، عرض و قطر متفاوتی قرار داد.

اولین و مشهورترین شکل این مسئله معمای هشت وزیر است که برای حل آن باید ۸ وزیر را در یک صفحهً معمولی (۸×۸) شطرنج قرار داد. این مسئله ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید.

مسئله n وزیر در صورتی جواب دارد که n مساوی ۱ یا بیشتر از ۳ باشد. یعنی مسئله دو وزیر و سه وزیر راه حلی ندارند.

تاریخچه

این مسئله در سال ۱۸۴۸ توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله Gauss و Georg Cantor بر روی این مسئله کار کرده و در نهایت آن را به n وزیر تعمیم دادند. اولین راه حل توسط Franz Nauck در سال ۱۸۵۰ ارائه شد که به همان مسئله n وزیر تعمیم داده شد. پس از آن Gunther راه حلی با استفاده از دترمینان ارائه داد که J.W.L. Glaisher آن را کامل نمود. در سال ۱۹۷۹، Edsger Dijkstra Nauck این مسئله را با استفاده از الگوریتم عقب‌گرد حل کرد.

حل مسئله

هشت وزیر را می‌توان با الگوریتم‌های مختلفی مانند تپه نوردی و روش ارضای محدودیت(csp) حل کرد که در زیر روش ارضای محدودیت را بررسی می‌کنیم. هر وزیری در هر ستونی هدفی دارد که همان مکانش در هرستون می‌شود یک گره .در کد زیر تعریف مکان‌ها را داریم:

Variables: { Q1, Q2, Q3, Q4 }

Domain: { (1, 2, 3, 4), (1, 2, 3, 4), (1, 2, 3, 4), (1, 2, 3, 4) }

Constraints: Alldifferent( Q1, Q2, Q3, Q4 ) and 
for i = 0...n and j = (i+1)...n, k = j-i, Q[i] != Q[j] + k and Q[i] != Q[j] - k

و این الگوریتم که برای جواب هر خانه‌است به دست می‌آید که یک csp است

min-conflicts(csp, max):
initial := complete assignment ;jamiyate avaliye
for 1..max do: ;az 1 .. akharin khane
if initial is a solution: ;if jamiyate tolide javab bod 
return initial ;barmigardanad
var := nextVar() ;da ghire indorat yek motaghair be jelo
value := leastConflicts( var ) ;taeein meghdar
var := value in initial ;gharar dadan meghdar dar motaghair
return failure ;bargash be ebtedaye algoritm

صورت مسئله

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

شمردن تعداد جواب‌ها

جدول زیر تعداد راه حل‌ها برای قرار دادن n وزیر بر روی صفحه n × nنشان می‌دهد. هر دو منحصر به فرد و متمایز، برای تعداد ۱-۱۴،۲۴-۲۶ است.

مسئله ی چند وزیر

  • توجه:

حالت شش وزیر جواب‌های کمتری نسبت به پنج وزیر دارد و فرمول صریحی برای یافتن تعداد جواب‌ها وجود ندارد.

روش‌های حل مسئله

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

از تکنیک عقبگرد Backtracking برای حل مسائلی استفاده می‌شود که در آن‌ها دنباله‌ای از اشیاء از یک مجموعه مشخص انتخاب می‌شود، به‌طوری‌که این دنباله، ملاکی را در بر می‌گیرد. عقبگرد حالت اصلاح شدهٔ جستجوی عمقی یک درخت است. این الگوریتم همانند جستجوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می‌شوند که گره امید بخش باشد و در آن گره حلی وجود نداشته باشد. با توجه به اینکه هیچ ۲ وزیری نباید همدیگر را گارد کنند و در یک سطر نمی‌توانند باشند، تعداد کل حالت‌ها برای n=۴ برابر ۴*۴*۴*۴=۲۵۶ است. در شطرنج یک وزیر می‌تواند به مهره‌هایی که در خانه‌های عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره‌گذاری کنیم و وزیر در خانه (i، j) قرار داشته باشد، مهره‌هایی که در خانه‌های (i، m) یا (m، j) یا (i ± m، j ± m) قرار دارند توسط وزیر تهدید می‌شوند.

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

مراحل جستجو برای یافتن جواب را به این صورت دنبال می‌کنیم که: وزیر اول را در ردیف اول و ستون اول قرار می‌دهیم.

در ردیف دوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در این خانه قرار می‌دهیم.

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

دوباره در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید دو وزیر قبلی نباشد. این بار خانه را می‌یابیم و وزیر سوم را در آن قرار می‌دهیم.

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

در ردیف دوم اولین خانه‌ای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار می‌دهیم.

در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه می‌گذاریم.

در ردیف چهارم اولین خانه‌ای را میابیم که مورد تهدید وزیران پیشین نباشد. این بار خانه را می‌یابیم و وزیر چهارم را در آن خانه قرار می‌دهیم.

به یک جواب می‌رسیم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالاً” می‌توانیم جوابهای دیگری نیز بیابیم.

شبه کد پیاده‌سازی الگوریتم عقبگرد برای مسئله n وزیر

void queens (index i)
{
	index j;
	if (promising(i))
		if (i == n)
			cout << col[1] through col[n];
		else
			for (j = 1; j <= n; j++) {
				col[i + 1] = j;
				queens(i + 1);
			}
}
bool promising (index i)
{
	index k;
	bool Switch;
	k = 1;
	Switch = true ;
	while (k < i && switch) {
		if (col[i] == col[k] || abs(col[i] – col[k] == i - k))
			switch = false;
		k++;
	}
	return Switch;
}

برنامه زبان C به صورت غیر بازگشتی

# include <stdio.h>

int b[8];

inline static int unsafe(int y) {
        int i, t, x;
        x = b[y];
        for (i = 1; i <= y; i++) {
                t = b[y - i];
                if ((t == x) ||
                     (t == x - i) ||
                     (t == x + i)) {
                        return 1;
               }
       }

        return 0;
}

static void putboard(void) {
        static int s = ۰;
        int x, y;
        printf("\n\nSolution #٪i\n", ++s);
        for (y = 0; y < 8; y++) {
                for (x = 0; x < 8; x++) {
                        printf((b[y] == x) ? "|Q": "|_");
               }
                printf("|\n");
       }
}

int main(void) {
        int y = ۰;
        b[۰] = -۱;
        while (y >= ۰) {
                do {
                        b[y]++;
               } while ((b[y] < 8) && unsafe(y));
                if (b[y] < 8) {
                        if (y < 7) {
                                b[++y] = -۱;
                       } else {
                                putboard();
                       }
               } else {
                        y--;
               }
       }

        return 0;
}

برنامه زبان ++C به صورت بازگشتی

  • برنامه زیر برای هشت وزیر نوشته شده‌است با انتخاب اعداد دیگر به جای هشت در define MAXSIZE 8 # می‌توان برای تعداد دیگری وزیر نیز استفاده کرد.
# include <assert.h>
# include <stdio.h>

# define MAXSIZE 8
class EightQueens
{
    int m_size;				
    int m_solution_count;		
    int m_attempt_count;		
    int m_queen[MAXSIZE];		
    bool m_row_inuse[MAXSIZE]; 		
    bool m_diag_rise[MAXSIZE*2];	
    bool m_diag_fall[MAXSIZE*2];	

public:

    EightQueens(int size, bool is_alt) {

	assert(size <= MAXSIZE);

	m_size = size;
	m_solution_count = 0;
	m_attempt_count = 0;

	for (int i = 0; i < m_size; i++) {
	    m_queen[i] = i;
	    m_row_inuse[i] = 0;
	}

	for (int j = 0; j < m_size*2; j++) {
	    m_diag_rise[j] = 0;
	    m_diag_fall[j] = 0;
	}

	if (is_alt) SearchAlt(0);
	else        Search(0);

   }

    int GetSolutionCount() {
	return m_solution_count;
   }

    int GetAttemptCount() {
	return m_attempt_count;
   }

private:

    void SearchAlt(int col){

	if (col == m_size) {
	    m_solution_count++;
	    return;
	}

	for (int row = 0; row < m_size; row++) {
	    m_attempt_count++;
	    if (m_row_inuse[row] == 0 && IsDiagValid(col, row)) {
		m_queen[col] = row;
		m_row_inuse[row] = 1;
		SetDiags(col, 1);
		SearchAlt(col+1);
		SetDiags(col, 0);
		m_row_inuse[row] = 0;
		m_queen[col] = -1;
	   }
	}

   }

    void Search(int col) {
	if (col == m_size) {
	    m_solution_count++;
	    return;
	}

	for (int i = col; i < m_size; i++) {
	    if (SwapQueenIfDiagValid(col, i)) {
		Search(col+1);
		UnSwapQueen(col, i);
	   };
	}
   }

    void SwapQueenBasic(int i, int j) {
	    int hold = m_queen[i];
	    m_queen[i] = m_queen[j];
	    m_queen[j] = hold;
   }

    void SetDiags(int col, int val) {
	assert(m_diag_rise[m_queen[col] + col]!= val);
	       m_diag_rise[m_queen[col] + col] =  val;
	assert(m_diag_fall[m_queen[col] - col + m_size]!= val);
	       m_diag_fall[m_queen[col] - col + m_size] =  val;
   }

    bool IsDiagValid(int col, int row) {
	return (m_diag_rise[row + col] == 0 &&
		m_diag_fall[row - col + m_size] == 0);
   }

    bool SwapQueenIfDiagValid(int i, int j) {
	m_attempt_count++;
	if (IsDiagValid(i, m_queen[j])) {
	    SwapQueenBasic(i, j);
	    SetDiags(i, 1);
            return true;
	}
        return false;
   }

    void UnSwapQueen(int i, int j) {
	SetDiags(i, 0);
	SwapQueenBasic(i, j);
   }

};

void
do_work(bool is_alt)
{
    int size = 8;

    EightQueens puzzle(size, is_alt);
    int soln = puzzle.GetSolutionCount();
    int attempt = puzzle.GetAttemptCount();
    assert(size!= 8 || soln == 92);
    const char* style = is_alt ? "cartesian": "permutation";
    printf("EightQueens[%d] has %d solutions found in %5d attempts using %s search. \n", size, soln, attempt, style);
}

int main()
{
    printf("We should have 92 solutions for 8x8. \n");
    do_work(0);
    do_work(1);
}

انیمیشن روش بازگشتی

 

مسئله چند وزیر

 

الگوریتم مونت کارلو

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

شبه کد پیاده‌سازی الگوریتم مونت کارلو برای الگوریتم عقبگرد مسئله n وزیر

  int ostimate _ n_ queens (int n)
   {
          index i , j , col [1..n];
          int m , mprod , numnodes ;
          set _of_ index  prom _children;
          i = ۰;
          numnodes =۱ ;
          m = ۱;

        mprod  = ۱ ;
        while  (m!= 0 && i!= n) {
        mprod = mprod * m ;
        numnodes  = numnodes + mprod * n;
        i ++;
        m = ۰ ;
        prom_childern  = Ø;
        for (j = 1 ; j ≤ n ; j++;) {
                col [i]  = j ;
                if (promising(i)) {

         m++;
         prom_children = prom _ children U {i};
                }
            }
             if (m!= ۰)  {
                 j = random selection from prom _childeren;
                 col [i];
             }
        }
         return numnodes;
     }

روش مکاشفه‌ای

برای حل این مسئله که دارای ۹۲ جواب است، باید تکنیکهایی جهت کاهش حالات، روش Brute Force یا امتحان تک تک جواب‌ها انجام شود. تعداد همه حالاتی که می‌تواند در روش Brute Force چک شود برابر ۱۶٬۷۷۷٬۲۱۶ یا هشت به توان هشت است! یکی از روش‌های حل این مسئله برای n>=4 یا n=1 استفاده از روش مکاشفه‌ای ( heuristic)است:

1- عدد n را بر عدد ۱۲ تقسیم کن و باقی‌مانده را یادداشت کن

۲- به ترتیب اعداد زوج ۲ تا n را در لیستی بنویس

۳- اگر باقی‌مانده ۳ یا ۹ بود، عدد ۲ را به انتهای لیست انتقال بده.

۴- به لیست اعداد فرد ۱ تا n را به ترتیب اضافه کن، اما اگر باقی‌مانده ۸ بود اعداد را دو به دو باهم عوض کند (مثلاً ۱و۳و۵و۷و۹ تبدیل به ۳و۱و۷و۵و۹ میشه)

۵- اگر باقی‌مانده ۲ بود جای ۱ و۳ را با هم عوض کن و ۵ را به انتهای لیست ببر.

۶- اگر باقی‌مانده ۳ یا ۹ بود، اعداد ۱ و ۳ را به انتهای لیست ببر.

۷- حال با استفاده از لیست بدست آمده وزیرها در صفحه شطرنج چیده می‌شوند، به‌طوری‌که جای وزیر ستون اول، اولین عدد لیست، جای وزیر ستون دوم، دومین عدد لیست و…

این الگوریتم یک راه حل برای حل این مسئله‌است، برای بدست آوردن همه حالات از روش‌های دیگری می‌توان استفاده کرد. روش حل مسئله ۱۲ راه حل یکتا دارد که با در نظرگیری تقارن و چرخش به ۹۲ حالت قابل تبدیل است.

روش‌های جستجوی محلی

می‌توان به مسئله ۸ وزیر به عنوان یک مسئله بهینه‌سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می‌باشد.

به عنوان مثال فرض کنید در صفحه شطرنج معمولی، ۸ وزیر را به دو روش زیر قرار دهیم:

مسئله ی چند وزیرمسئله ی چند وزیر

در روش چینش سمت چپ ۳ وزیر و در روش چینش سمت راست ۴ وزیر همدیگر را گارد می‌دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می‌توان مسئله بهینه‌سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جواب‌های ممکن برای مسئله باشد. در صورتی S* می‌تواند جواب مسئله باشد که به ازای همه جواب‌های موجود در S، S* بهینه تر از دیگر جواب‌ها باشد. در مسئله ۸ وزیر دیدیم که جوابی بهینه‌است که تعداد گاردهای جفت وزیر آن کمتر باشد.

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

نحوه پیاده‌سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روش‌های جستجو از اهمیت ویژه‌ای برخوردار است. به عنوان مثال برای مسئله ۸ وزیر می‌توان به شکل‌های زیر حالت‌های همسایگی را تولید کرد:

۱) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد.

۲) یکی از وزیرها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند.

۳) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند

مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4