رتبه موضوع:
  • 2 رای - 3.5 میانگین
  • 1
  • 2
  • 3
  • 4
  • 5
سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
#1
با سلام. امروز سورس مسئله n وزیر با الگوریتم ژنتیک رو قرار میدم.

کد پی‌اچ‌پی:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace 
chess2
{
public 
partial class Form1 Form
{
int c 0;
public 
Form1()
{

InitializeComponent();
}
private 
int[] rand(int nint x)
{
Random random = new Random(DateTime.Now.Millisecond);
int t random.Next(0n);
int[] inta = new int[n];
int c;
string[] abc = new string[n]; ;
for (
int i 0ni++) { arandom.Next(0n); 1; while ((c) >= 0)
{
if (
inta[c] == t)
{
abc[i] = t.ToString();
goto 
a;

}
c++;
}
for (
int i2 0i2 <= ii2++)
{
if (
abc[i2] == t.ToString())
goto 
a;
}
inta[i] = t;
}
return 
inta;
}
private 
Double fib(int n)
{
if (
== 0)
return 
0;
if (
== 1)
return 
1;
Double tmp 0;
for (
int i 0<= ni++)
{
tmp += i;
}
return 
tmp 0.0;
}

private 
int[,] cross(int[] pop1int[] pop2int n)
{
int[,] pop_4_return = new int[2n];
for (
int c 02c++)
{
for (
int i 0ni++) { if ((2) > i)
{
if (
== 0)
{
pop_4_return[ci] = pop2[i];
}
else
{
pop_4_return[ci] = pop1[i];
}
}
else
{
if (
== 0)
{
pop_4_return[ci] = pop1[i];
}
else
{
pop_4_return[ci] = pop2[i];
}
}
}
}
return 
pop_4_return;
}
private 
Double fit(int[] nffint n)
{
int[,] inta = new int[nn];
int tmp 0fitness 0;
for (
int c 0nc++)
{
inta[cnff[c]] = 1;
}

for (
int i 0ni++)
{
for (
int ii 0ii nii++)
{
if (
inta[iii] == 1)
{
tmp ii;
goto 
a;
}
}
a:
for (
int i2 1i2 ni2++)
{
if (((
i2) < n))
if ((
tmp i2) < n)
if (
inta[i2tmp i2] == 1)
fitness++;
if (((
i2) < n)) if ((tmp i2) >= 0)
if (
inta[i2tmp i2] == 1)
fitness++;
if ((
i2) < n)
if (
inta[i2tmp] == 1)
fitness++;
}
}
Double fibonachi fib(1) + 0.0;
Double r 100 - (fitness * (100 fibonachi));
return 
r;
}
private 
int[,] pop_generator(int n)
{
int[,] inta = new int[nn];
int[] intb = new int[n];
intb rand(nc);
c++;
for (
int i 0ni++)
{
intb rand(nc);
while ((
fit(intbn)) < 50.0)
intb rand(nc); c++;
for (
int j 0nj++)
{
inta[ij] = intb[j];
}
c++;
}
return 
inta;
}
private 
int arr_to_var(int[] narrint n)
{
string nvar "";
for (
int i 0ni++)
{
nvar += narr[i].ToString();
}
Int32 n_for_return Int32.Parse(nvar);
return 
n_for_return;

}
private 
int[,] crossover(int[,] popint n)
{
int[,] pop_for_return = new int[nn];
int[,] crosstemp = new int[22];
int[] tmp1 = new int[n];
int[] tmp2 = new int[n];
for (
int i 0n+= 2)
{
for (
int j 0nj++)
{
tmp1[j] = pop[ij];
tmp2[j] = pop[1j];
}
crosstemp cross(tmp1tmp2n);
for (
int j2 0j2 nj2++)
{
pop_for_return[ij2] = crosstemp[0j2];
pop_for_return[1j2] = crosstemp[1j2];
}
}
return 
pop_for_return;
}
private 
void printc(int[] arr_4_printint n)
{
int[,] tmp = new int[nn];
for (
int i 0ni++)
tmp[arr_4_print[i], i] = 1;
for (
int i 0ni++)
{
label1.Text += "\n\r";
for (
int j 0nj++)
{
if (
tmp[ij] == 1)
label1.Text += "*";
else
label1.Text += "0";
}
}
}
private 
void Form1_Load(object senderEventArgs e)
{

}

private 
void button1_Click(object senderEventArgs e)
{
Int32 n Int32.Parse(textBox1.Text);
int[,] pop = new int[nn];
int[,] cros = new int[nn];
int[] tmp = new int[n];
pop pop_generator(n);
for (
int i 0ni++)
{
for (
int j 0nj++)
{
tmp[j] = pop[ij];
}
if (
fit(tmpn) == 100.0)
{
printc(tmpn);
goto 
a;
}
}
int comp 1;
int counter 0;
cros crossover(popn);
while (
comp == 1)
{
this.Text counter.ToString();
counter++;
label1.Text "";
for (
int i 0ni++)
{
for (
int j 0nj++)
{
label1.Text += cros[ij];
}
label1.Text += "\n\r";
}
for (
int i 0ni++)
{
for (
int j 0nj++)
{
tmp[j] = cros[ij];
}
if (
fit(tmpn) == 100.0)
{
printc(tmpn);
comp 0;
goto 
a;

}
}
cros crossover(crosn);
}
a:
this.Text "find";
}
}

[عکس: www.Mojsazan.com.gif]
پاسخ
#2
سلام
من به تازگی با این سایت آشنا شدم
واقعا خیلی جالبه خسته نباشید
اگر براتون امکان داره بیشتر در مورد این کدی که گذاشتید توضیح بدید
من نتونستم رانش کنم!
با تشکر
پاسخ
سپاس شده توسط
#3
با سلام و خوش آمد گویی به شما

صورت مسئله : هشت وزير را در هشت خانه شطرنج (8*8) طوري قرار دهيد كه هيچكدام يكديگر را تهديد نكنند. وزير در خانه هاي شطرنج به صورت عرضي،طولي و قطري مي تواند حركت كند. اين مسئله قابل تعميم به مسئله N وزير در يك شطرنج N*N است.

تاريخچه: اين مسئله در سالي 1848 توسط شطرنج بازي به نام Max Bezzel عنوان شد و رياضي دانان بسياري ازجمله Gauss و Georg Cantor بر روي اين مسئله كار كرده و در نهايت آنرا به N وزير تعميم دادند. اولين راه حل توسط Franz Nauck در سال 1850 ارائه شد كه به همان مسئله N وزير تعميم داده شد. پس از آن Gunther راه حلي با استفاده از دترمينان ارائه داد كه J.W.L. Glaisher آنرا كامل نمود.
در سال 1979 ، Edsger Dijkstra با استفاده از الگوريتم عقب گرد اول عمق اين مسئله را حل كرد.

راه حل: براي حل اين مسئله كه داراي 92 جواب است ، بايد تكنيكهايي جهت كاهش حالات ،روش Brute Force يا امتحان تك تك جواب ها انجام شود. تعداد همه حالاتي كه مي تواند در روش Brute Force چك شود برابر 16,777,216 يا هشت به توان هشت است!
يكي از روش هاي حل اين مسئله براي n>=4 يا n=1 استفاده از روش مكاشفه اي (heuristic) است:
1- عدد n را بر عدد 12 تقسيم كن و باقي مانده را يادداشت كن
2- به ترتيب اعداد زوج 2 تا n را در ليستي بنويس
3- اگر باقي مانده 3 يا 9 بود ، عدد 2 را به انتهاي ليست انتقال بده.
4- به ليست اعداد فرد 1 تا N را به ترتيب اضافه كن، اما اگر باقي مانده 8 بود اعداد را دو به دو باهم عوض كند (مثلا 1و3و5و7و9 تبديل به 3و1و7و5و9 ميشه)
5- اگر باقي مانده 2 بود جاي 1 و3 را با هم عوض كن و 5 را به انتهاي ليست ببر
6- اگر باقي مانده 3 يا 9 بود ، اعداد 1 و 3 را به انتهاي ليست ببر.
7- حال با استفاده از ليست بدست آمده وزير ها در صفحه شطرنج چيده مي شوند، بطوريكه جاي وزير ستون اول ،اولين عدد ليست ،جاي وزير ستون دوم ، دومين عدد ليست و ...
اين الگوريتم يك راه حل براي حل اين مسئله است، براي بدست آوردن همه حالات از روشهاي ديگري مي توان استفاده كرد.
روش حل مسئله 12 راه حل يكتا دارد كه با در نظر گيري تقارن و چرخش به 92 حالت قابل تبديل است.




REF
[عکس: www.Mojsazan.com.gif]
پاسخ
سپاس شده توسط parastoo
#4
روش های جستجوی محلی
برای معرفی هریک از روش های جستجویی که در فصل به بررسی آن ها می پردازیم از مسئله 8 وزیر استفاده خواهیم کرد. در مسئله 8 وزیر هدف قرار دادن 8 وزیر بر روی صفحه شطرنج به گونه ای است که هیچیک از وزیرها همدیگر را گارد ندهند. تعمیم یافته مسئله 8 وزیر، مسئله n وزیر است که در آن بر روی یک صفحه شطرنج n*n باید n وزیر را به گونه ای قرار دهیم که هیچیک همدیگر را گارد ندهند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش های جستجوی معمولی قادر به حل آن ها نخواهد بود. از سوی دیگر می توان به مسئله 8 وزیر به عنوان یک مسئله بهینه سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می باشد. به عنوان مثال فرض کنید در صفحه شطرنج معمولی ، 8 وزیر را به دو روش زیر قرار دهیم :

[عکس: queen1.JPG]
[عکس: queen.JPG]

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

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

سخن آخر اینکه نحوه پیاده سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روش های جستجو از اهمیت ویژه ای برخوردار است. به عنوان مثال برای مسئله 8 وزیر می توان به شکل های زیر حالت های همسایگی را تولید کرد :
1) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد.
2) یکی از وزیر ها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند.
3) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند
REF
[عکس: www.Mojsazan.com.gif]
پاسخ
سپاس شده توسط
#5
تپه نوردی Hill Climbing Searching یکی از الگوریتم های هوش مصنوعی می باشد که برای مسائل پیچیده به کار میرود به گونه ای که بجای اینکه برای حل مسئله از کل گراف استفاده کند.به صورت اتفاقی از یک قسمت از گراف استفاده میکند

دريافت سورس برنامه به زبان #C

REF


فایل‌های پیوست
.zip   Hill-20Climbing-20Searching.zip (اندازه 28.41 KB / تعداد دانلود: 558)
[عکس: www.Mojsazan.com.gif]
پاسخ
سپاس شده توسط R_Ebadi
#6
اين مسئله به وسيله الگوريتم ژنتيک نيز در لينک زير(پاورپوينت سوم) توضيح داده شده است

اسلاید های آموزشی الگوریتم ژنتیک

دراین لينک زير هم حل اين مسئله توسط الگوريتم ژنتيک با زبان vb.net قرار دارد

برنامه کامل ضمیمه شد

REF


فایل‌های پیوست
.rar   queentest.rar (اندازه 83.36 KB / تعداد دانلود: 887)
[عکس: www.Mojsazan.com.gif]
پاسخ
سپاس شده توسط DaydayEdide ، Smormawawwalk ، R_Ebadi
#7
حل مسئله هشت وزير با آنالينگ شبيه سازي شده


فایل‌های پیوست
.pdf   AIapxSA8Q.pdf (اندازه 122.58 KB / تعداد دانلود: 664)
[عکس: www.Mojsazan.com.gif]
پاسخ
سپاس شده توسط محمد دادجو ، reavoicerbili ، R_Ebadi
#8
فرض کنید که در محله‌ای به دنبال یک کتاب فروشی خاص می‌گردیم. این کتاب فروشی در کوچه‌ای قرار دارد که نبش آن یک خواربار فروشی است و همچنین در ابتدای خیابانی که این کوچه قرار دارد یک مدرسه هست.

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

روالی که برای یافتن جواب در مثال بالا دنبال شد، روش بازگشت به عقب (Backtracking) نام دارد. در این روش همانطور که در مثال مشاهده کردید، در هر زمان که متوجه شدیم مسیر انتخاب شده به جواب نمی‌رسد، یک مرحله به عقب برگشته و مسیر دیگری را دنبال می کنیم.

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


مثال 8 وزير:

چگونه هشت وزیر را بر روی صفحه شطرنج قرار دهیم به گونه‌ای که هیچ یک از آنها مورد تهدید دیگری قرار نگیرد؟

در مقاله زير اين مسئله با استفاده از روش عقبگرد همراه با سورس کد آن کاملاً توضيح داده شده


فایل‌های پیوست
.pdf   att226_0_vazere8.pdf (اندازه 292.41 KB / تعداد دانلود: 692)
[عکس: www.Mojsazan.com.gif]
پاسخ
سپاس شده توسط R_Ebadi
#9
و این هم برنامه ی NQueen که n رو از کاربر می خواد و بعد تمام جوابهای موجود رو چاپ میکنه!
با TC اجرا ميشه
REF


فایل‌های پیوست
.zip   Nqueen.zip (اندازه 506 بایت / تعداد دانلود: 405)
[عکس: www.Mojsazan.com.gif]
پاسخ
سپاس شده توسط mohsen_sh ، DaydayEdide ، R_Ebadi ، peymanttm
#10
یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.
- هدف از مسئله n وزیر ، چیدن n مهره وزیر در یک صفحه شطرنج است ، به طوری که هیچ دو وزیری یکدیگر را گارد ندهند. یعنی هیچ دو مهره ای نباید در یک سطر، ستون یا قطر یکسان باشند.

- عقبگرد حالت اصلاح شده ی جست و جوی عمقی یک درخت است.

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

الگوریتم عقبگرد برای مسئله n وزیر
کد پی‌اچ‌پی:
void queens index i)
 {
 
index j;
  if ( 
promising(i))
  if ( 
== n)
  
cout << col [1through col [n];
  else
  for ( 
j ≤ n j++ ) {
 
 
col +] = j;
 
queens 1);
 }
}
bool promising index i )
{
  
index k ;
 
bool  switch;
 
1;
 switch = 
true ;
  while ( 
&& switch ) {
  if (
col [i] == col[k] || abs(col[i– col[k] == i-k)
 switch = 
false;
 
k++;
 }
  return switch;
 } 
REF
[عکس: www.Mojsazan.com.gif]
پاسخ
سپاس شده توسط mohsen_sh ، nahid ، Smormawawwalk ، R_Ebadi


موضوعات مشابه ...
موضوع نویسنده پاسخ بازدید آخرین ارسال
  الگوریتم ژنتیک(Genetic Algorithm) TinaSefati 6 6,512 04-15-2014, 12:54 PM
آخرین ارسال: siryahya
  مسئله کشیش و آدم خوار ها & مسئله های مشابه مهرداد عباسی 1 241 04-01-2014, 05:53 PM
آخرین ارسال: مهرداد عباسی
  سورس کد و آموزش های الگوریتم کلونی مورچه ها(Ant Colony Algorithm) مهرداد عباسی 31 23,311 01-25-2014, 02:36 PM
آخرین ارسال: najafi123
  مسئله فروشنده دوره‌گرد(Travelling salesman problem، به‌اختصار: TSP ) مهدی ابراهیمی 5 3,731 10-29-2013, 08:34 PM
آخرین ارسال: zooroo
Smile الگوریتم های دوز بازی laleh62 0 475 10-04-2013, 06:14 PM
آخرین ارسال: laleh62
  حل مسئله جورچین با الگوریتم ژنتیک bdb 3 1,392 05-24-2013, 06:00 PM
آخرین ارسال: bdb
  پیاده سازی مسئله 8 وزیر با استفاده از الگوریتم ABC sharokh 2 2,895 12-10-2012, 05:20 PM
آخرین ارسال: FATEMEH1369
  الگوریتم کلونی زنبور عسل مصنوعی Artificial Bee Colony (ABC) Algorithm مهدی ابراهیمی 6 9,131 05-23-2012, 09:54 PM
آخرین ارسال: مهدی ابراهیمی

پرش به انجمن:


کاربران در حال بازدید این موضوع: 1 مهمان