زمان جاری: 04-19-2014,
خوش آمدید مهمان گرامی! (ورودعضویت)

ارسال پاسخ 
سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
04-27-2010, (آخرین تغییر در این ارسال: 04-27-2010 توسط مهرداد عباسی.)
ارسال: #1
سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
با سلام. امروز سورس مسئله n وزیر با الگوریتم ژنتیک رو قرار میدم.

کد PHP:
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]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : ali.it fereshteh محمد دادجو Smormawawwalk R_Ebadi رضا بهادری mansoor-13
12-19-2010,
ارسال: #2
RE: سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
سلام
من به تازگی با این سایت آشنا شدم
واقعا خیلی جالبه خسته نباشید
اگر براتون امکان داره بیشتر در مورد این کدی که گذاشتید توضیح بدید
من نتونستم رانش کنم!
با تشکر
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
12-20-2010,
ارسال: #3
RE: سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
با سلام و خوش آمد گویی به شما

صورت مسئله : هشت وزير را در هشت خانه شطرنج (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 حالت قابل تبديل است.




You are not allowed to view links. Register or Login to view.

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : parastoo
12-20-2010, (آخرین تغییر در این ارسال: 12-20-2010 توسط مهرداد عباسی.)
ارسال: #4
RE: سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
روش های جستجوی محلی
برای معرفی هریک از روش های جستجویی که در فصل به بررسی آن ها می پردازیم از مسئله 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) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند
You are not allowed to view links. Register or Login to view.

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
12-20-2010, (آخرین تغییر در این ارسال: 12-20-2010 توسط مهرداد عباسی.)
ارسال: #5
RE: سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
تپه نوردی Hill Climbing Searching یکی از الگوریتم های هوش مصنوعی می باشد که برای مسائل پیچیده به کار میرود به گونه ای که بجای اینکه برای حل مسئله از کل گراف استفاده کند.به صورت اتفاقی از یک قسمت از گراف استفاده میکند

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

REF


فایل‌های ضمیمه
.zip  Hill-20Climbing-20Searching.zip (اندازه: 28.41 KB / دانلودها: 505)

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : R_Ebadi
12-20-2010,
ارسال: #6
RE: سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
اين مسئله به وسيله الگوريتم ژنتيک نيز در لينک زير(پاورپوينت سوم) توضيح داده شده است

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

دراین You are not allowed to view links. Register or Login to view.زير هم حل اين مسئله توسط الگوريتم ژنتيک با زبان vb.net قرار دارد

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

You are not allowed to view links. Register or Login to view.


فایل‌های ضمیمه
.rar  queentest.rar (اندازه: 83.36 KB / دانلودها: 791)

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : DaydayEdide Smormawawwalk R_Ebadi
12-20-2010,
ارسال: #7
RE: سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
حل مسئله هشت وزير با آنالينگ شبيه سازي شده


فایل‌های ضمیمه
.pdf  AIapxSA8Q.pdf (اندازه: 122.58 KB / دانلودها: 586)

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : محمد دادجو reavoicerbili R_Ebadi
12-20-2010,
ارسال: #8
RE: سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
فرض کنید که در محله‌ای به دنبال یک کتاب فروشی خاص می‌گردیم. این کتاب فروشی در کوچه‌ای قرار دارد که نبش آن یک خواربار فروشی است و همچنین در ابتدای خیابانی که این کوچه قرار دارد یک مدرسه هست.

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

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

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


مثال 8 وزير:

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

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


فایل‌های ضمیمه
.pdf  att226_0_vazere8.pdf (اندازه: 292.41 KB / دانلودها: 648)

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : R_Ebadi
12-20-2010,
ارسال: #9
RE: سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
و این هم برنامه ی NQueen که n رو از کاربر می خواد و بعد تمام جوابهای موجود رو چاپ میکنه!
با TC اجرا ميشه
You are not allowed to view links. Register or Login to view.


فایل‌های ضمیمه
.zip  Nqueen.zip (اندازه: 506 بایت / دانلودها: 376)

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : mohsen_sh DaydayEdide R_Ebadi peymanttm
12-20-2010, (آخرین تغییر در این ارسال: 12-20-2010 توسط مهرداد عباسی.)
ارسال: #10
RE: سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C
یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.
- هدف از مسئله n وزیر ، چیدن n مهره وزیر در یک صفحه شطرنج است ، به طوری که هیچ دو وزیری یکدیگر را گارد ندهند. یعنی هیچ دو مهره ای نباید در یک سطر، ستون یا قطر یکسان باشند.

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

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

الگوریتم عقبگرد برای مسئله n وزیر
کد PHP:
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;
 } 
You are not allowed to view links. Register or Login to view.

[تصویر: www.Mojsazan.com.gif]
مشاهده سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در پاسخ
 تشکر شده توسط : mohsen_sh nahid Smormawawwalk R_Ebadi
ارسال پاسخ 


موضوعات مشابه ...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  الگوریتم ژنتیک(Genetic Algorithm) TinaSefati 6 5,870 04-15-2014
آخرین ارسال: siryahya
  مسئله کشیش و آدم خوار ها & مسئله های مشابه مهرداد عباسی 1 61 04-01-2014
آخرین ارسال: مهرداد عباسی
  سورس کد و آموزش های الگوریتم کلونی مورچه ها(Ant Colony Algorithm) مهرداد عباسی 31 19,455 01-25-2014
آخرین ارسال: najafi123
  مسئله فروشنده دوره‌گرد(Travelling salesman problem، به‌اختصار: TSP ) مهدی ابراهیمی 5 2,971 10-29-2013
آخرین ارسال: zooroo
Smile الگوریتم های دوز بازی laleh62 0 319 10-04-2013
آخرین ارسال: laleh62
  حل مسئله جورچین با الگوریتم ژنتیک bdb 3 1,044 05-24-2013
آخرین ارسال: bdb
  پیاده سازی مسئله 8 وزیر با استفاده از الگوریتم ABC sharokh 2 2,559 12-10-2012
آخرین ارسال: FATEMEH1369
  الگوریتم کلونی زنبور عسل مصنوعی Artificial Bee Colony (ABC) Algorithm مهدی ابراهیمی 6 7,996 05-23-2012
آخرین ارسال: مهدی ابراهیمی

پرش در انجمن: