راهنمایی در مورد نوشتن الگوریتم برنامه ای که عدد گذاری نماید

[javadt]

راهنمایی در مورد نوشتن الگوریتم برنامه ای که سطر ها و ستون ها را جمع ببندد

به عنوان مثال

من یک جدول 3*3 دارم که می شه 9 تا خونه
حالا می خوام توی این جدول اعداد 1-9 رو جوری بزارم که تکراری هم نباشه


22 * * *
9 * * *
14 * * *
10 20 15
اعداد رو جای ستاره ها بزارم
با تشکر

[javadt]

راهنمایی در مورد نوشتن الگوریتم برنامه ای که سطر ها و ستون ها را جمع ببندد

[baidin]

راهنمایی در مورد نوشتن الگوریتم برنامه ای که سطر ها و ستون ها را جمع ببندد

به عنوان مثال

من یک جدول 3*3 دارم که می شه 9 تا خونه
حالا می خوام توی این جدول اعداد 1-9 رو جوری بزارم که تکراری هم نباشه


22 * * *
9 * * *
14 * * *
10 20 15
اعداد رو جای ستاره ها بزارم
با تشکر

[COLOR="Red"]حالا می خوام توی این جدول اعداد 1-9 رو جوری بزارم که تکراری هم نباشه[/
COLOR]
ما نفهميديم كه ميخواهي جمع كني يا ... سوالت مشخص نيست. اين اعداد توي چي قرار گرفتند؟

[Felony]

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

[quantomquery]

راهنمایی در مورد نوشتن الگوریتم برنامه ای که سطر ها و ستون ها را جمع ببندد

به عنوان مثال

من یک جدول 3*3 دارم که می شه 9 تا خونه
حالا می خوام توی این جدول اعداد 1-9 رو جوری بزارم که تکراری هم نباشه


22 * * *
9 * * *
14 * * *
10 20 15
اعداد رو جای ستاره ها بزارم
با تشکر


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

[javadt]

نه من می خوام برنامه طوری باشه که جایی که الان اعداد هست عدد بزارم
و بعد اعداد 1-9 را طوری برنامه جای ستاره ها قرار بده که جمع هر ردویف به عددی که آخر ردیف هست برسه

[quantomquery]

نه من می خوام برنامه طوری باشه که جایی که الان اعداد هست عدد بزارم
و بعد اعداد 1-9 را طوری برنامه جای ستاره ها قرار بده که جمع هر ردویف به عددی که آخر ردیف هست برسه


فکر می کنم بهترین راه استفاده از الگوریتم ژنتیک باشه
یعنی شما یه جمعیت اولیه باید داشته باشید مثلا به صورت تصادفی 100 جدول که اعداد 1 تا 9 هستند را تولید کنید سپس سطر وستون های هر کدام را جمع کرده و با سطر و ستون های جدول اولیه مقایسه کنید اگر به جواب رسیدید که چه بهتر و اگر به جواب نرسیدید شما باید بهترین جدول ها را از بین 100 جدول انتخاب کرده و اعداد داخل ان را تصادفا جابجا کنید و دوباره آن را تست کنید

برای فهمیدن بهتر الگوریتم ژنتیک به :

http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_% DA%98%D9%86%D8%AA%DB%8C%DA%A9

مراجعه کنید

[javadt]

دوست عزیز مثالی چیزی برای دانلود اگر داری بزار لطفا

[quantomquery]

دوست عزیز مثالی چیزی برای دانلود اگر داری بزار لطفا





1- صورت مسئله

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

جدول سودوکو در حقیقت یک جدول 9*9 است که بعضی از خانه‌های آن با اعدادی بین 1 تا 9 پرشده است. شما می‌توانید در هر خانه خالی یکی از اعداد 1 تا 9 را قرار دهید اما باید این کار را طوری انجام دهید که سه شرط زیر برقرار باشد.

بقیه در ادامه مطلب






http://www.shabakeh-mag.com/Data/Gallery/s73_Genetic-Jadval1.2_s.jpg (http://shabakeh-mag.com/img.aspx?l=/data/gallery/s73_genetic-jadval1.2.jpg)
1- در هر سطر هیچ عدد تکراری وجود نداشته باشد.
2- در هر ستون هیچ عدد تکراری نباید وجود داشته باشد.
3- در هر جدول 3*3 طبق شکل نیز نباید هیچ عدد تکراری وجود داشته باشد.

در جدول 1 یکی از جداول حل شده سودوکو را می‌بینید که شروط مورد نظر در آن صادق است، اما در حقیقت شکل آغازین مسئله مانند جدول 2 است که باید حل شود. اگر به حل یک نمونه جدول سودوکو تمایل دارید، می‌توانید جدول 2 را حل کنید.

مسئله‌ای که می‌خواهیم در این مقاله حل کنیم بدین‌صورت است که فرض کنید یک جدول سودوکوی خالی دارید و از شما می‌خواهند مثلا‌ً پنجاه راه‌حل معرفی کنید. یعنی به پنجاه جدول که خاصیت سودوکو داشته باشد. توجه کنید که در مسئله ما همه خانه‌ها خالی هستند. برای این‌که زمان اجرای این برنامه کمتر شود و امکان رسیدن به جواب در خانه نیز مهیا باشد، در صورت مسئله مورد نظر تغییر کوچکی دادیم؛ فرض کنید در هر خانه غیر از اعداد 1 تا 9 عدد صفر را نیز می‌توانید قرار دهید.

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

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

2- حل مسئله


http://www.shabakeh-mag.com/Data/Gallery/s73_Genetic01_s.jpg (http://shabakeh-mag.com/img.aspx?l=/data/gallery/s73_genetic01.jpg)
با توجه به این‌که تعداد حالا‌ت مسئله بسیار زیاد است، پیمایش کل فضای درخت حالت مسئله غیرممکن است. از طرفی ما نیازمند پنجاه جواب درست هستیم و مطمئناً جواب‌های مسئله ما در فضای درخت حالت مسئله پراکنده هستند و در نهایت این شرایط این ایده را به وجود می‌آورد که برای حل مسئله از الگوریتم‌های ژنتیک استفاده کنیم. اما برای پیاده‌سازی برنامه سعی می‌کنم همه مراحل را قدم به قدم توضیح دهم.

2-1- تعیین کروموزم

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

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

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

2-2 - ساختن جمعیت آغازین یا نسل اول


http://www.shabakeh-mag.com/Data/Gallery/s73_Genetic-code01_s.jpg (http://shabakeh-mag.com/img.aspx?l=/data/gallery/s73_genetic-code01.jpg)
کد 1
همان‌طور که می‌دانیم، جمعیت آغازین را می‌توانیم به صورت تصادفی ایجاد کنیم. یعنی در هر خانه از یک نمونه از جدول مورد نظر یک عدد تصادفی بین صفر تا نُه قرار دهیم. در اینجا ذکر چند نکته لا‌زم است: اول این‌که، در کد قرار گرفته در بخش دانلود سایت ماهنامه شبکه (http://www.shabakeh-mag.com/download) من تعداد کروموزم‌های جمعیت آغازین را برابر پنجاه فرض کردم و از این به بعد از هر نسل پنجاه عنصر انتخاب می‌شوند و به عنوان عناصر سازنده نسل بعدی مورد استفاده قرار می‌گیرند.

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


http://www.shabakeh-mag.com/Data/Gallery/s73_Genetic-code02_s.jpg (http://shabakeh-mag.com/img.aspx?l=/data/gallery/s73_genetic-code02.jpg)
کد 2
با توجه به این ایده می‌توانیم جمعیت آغازین را به‌گونه‌ای طراحی کنیم که با این‌که در هر خانه یک عدد تصادفی قرار داشته باشد، در هر سطر هیچ عدد تکراری نداشته باشیم. (کد 2)

در اینجا ذکر یک نکته لازم است که با توجه به این‌که نیازمند تعداد بسیار زیادی عدد بین 0 تا 9 به صورت تصادفی هستیم و با توجه به این‌که این اعداد در کسر بسیار کوچکی از زمان برای کامپیوتر تولید می‌شوند، نمی‌توانیم از توابعی مانند RND که عدد تصادفی ایجاد می‌کنند، استفاده کنیم؛ چراکه هسته یا سید تولید عدد تصادفی در این توابع در بهترین حالت ساعت (زمان) اجرای تابع است که برای ما مناسب نیست.

به همین منظور، می‌توانیم از RngCryptoServiceProvider از کلا‌س System.Security.Cryptography استفاده کنیم. (کد 1)

2-3- ساختن تابع از ارزش

در ادامه باید تابعی ایجاد کنیم که بتوانیم توسط آن به هر نمونه عددی متناسب با میزان خوب بودن آن را اختصاص دهیم. این تابع را که RANK می‌نامیم، بدین‌صورت تعریف می‌کنیم: به ازای هر سطر یا ستون یا هر مربع 3 *3 که شرط جدول سودوکو را داشته باشد، یک واحد به جواب تابع RANK اضافه می‌کنیم.


http://www.shabakeh-mag.com/Data/Gallery/s73_Genetic-code03_s.jpg (http://shabakeh-mag.com/img.aspx?l=/data/gallery/s73_genetic-code03.jpg)
کد 3
بدین‌صورت تابع RANK تابعی خواهد بود که دارای جواب بین صفر تا 27 ‌باشد. البته بدیهی است که اگر نمونه‌ای دارای RANK برابر 27 باشد، بدین معنی است که معادل یکی از المان‌های جواب نهایی سودوکو مسئله ما است. (کد 3)

باید توجه داشت که خروجی تابع RANK از نظر برنامه‌نویسی آرایه‌ای است یک‌بعدی به طول تعداد نمونه‌هایی که قرار است ارزشیابی شوند. مثلا‌ً اگر بخواهیم جمعیت پنجاه‌گانه اولیه را ارزشیابی کنیم، خروجی تابع ما آرایه‌ای یک بعدی با طول پنجاه است که ارزش نمونه صفر در خانه شماره صفر و به همین ترتیب تا ارزش نمونه 49 در خانه شماره 49 قرار می‌گیرد. (کلا‌ً پنجاه نمونه). (در VB آرایه‌ها از شماره صفر آغاز می‌شوند).

2-4- ترکیب نمونه‌ها و ساختن جواب جدید


http://www.shabakeh-mag.com/Data/Gallery/s73_Genetic-code04_s.jpg (http://shabakeh-mag.com/img.aspx?l=/data/gallery/s73_genetic-code04.jpg)
کد 4
در ادامه باید هر بار دو نمونه را انتخاب کنیم و از ترکیب هر دو نمونه دو جواب جدید به دست آوردیم. این عمل را در این برنامه پنج هزار بار انجام دادیم. یعنی از ترکیب تصادفی دو نمونه تصادفی از میان پنجاه نمونه مزبور، ده هزار جواب جدید ایجاد کردیم.

باید توجه داشت که نباید یک نمونه با خودش ترکیب شود؛ چراکه دو جواب عیناً مثل خودش تولید می‌کند. در نهایت اگر بخواهیم به طور خلا‌صه بیان کنیم، با انتخاب دو عدد تصادفی بین صفر تا 49 دو نمونه را انتخاب می‌کنیم.

توجه داشته باشید که باید این عدد تصادفی به گونه‌ای باشد که نمونه‌ای که دارای مقدار تابع ارزش بیشتری است، به همان نسبت نیز دارای شانس انتخاب بیشتری باشد. برای این کار، از تابعی به نام Selectinst استفاده کردیم که حتماً در Source برنامه متن آن را خواهید دید. (کد 4)

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


http://www.shabakeh-mag.com/Data/Gallery/s73_Genetic-code05_s.jpg (http://shabakeh-mag.com/img.aspx?l=/data/gallery/s73_genetic-code05.jpg)
کد 5
بنابراین به ازای هر جواب به دست آمده است این اعمال را انجام دهیم. ابتدا یک عدد تصادفی بین یک یا صفر انتخاب می‌کنیم. اگر عدد ما صفر بود، عمل جهش را انجام نمی‌دهیم، اما اگر یک بود، دو عدد تصادفی دیگر بین صفر تا هشت به نشانه شماره سطر و ستون خانه‌ای که باید در آن جهش انجام شود و یک عدد تصادفی بین صفر تا نُه به عنوان مقدار جدید آن خانه به دست می‌آوریم و عمل جهش را در آن انجام می‌دهیم. بدین‌ترتیب هر جواب ممکن است با احتمال پنجاه درصد در یکی از ژن‌های خود دچار جهش بشود.

مطالب گفته شده را در برنامه در قالب تابع Produce نوشتم. تابعی که آرایه مجموعه آغازین (مجموعه پنجاه‌تایی) و مجموعه جواب بعدی (مجموعه ده هزارتایی) و دو عدد تصادفی نقطه شکست و آدرس ذخیره کردن جواب‌ها در مجموعه بعدی را دریافت می‌کند دو عمل ترکیب و جهش را انجام می‌دهد و در نهایت آرایه‌ای ده‌هزارتایی به عنوان جواب برمی‌گرداند. (کد 5)

2-5 - ارزشیابی مجموعه جواب

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

2-6- ساختن نسل بعد


http://www.shabakeh-mag.com/Data/Gallery/s73_Genetic-code06_s.jpg (http://shabakeh-mag.com/img.aspx?l=/data/gallery/s73_genetic-code06.jpg)
کد 6
در اینجا باید از میان ده هزار جواب به دست آمده، جواب‌های برتر را به عنوان والدهای نسل بعدی انتخاب کنیم و بقیه را دور بریزیم، اما قبل از انجام این عمل، ذکر یک مطلب لازم است و آن این‌که همان‌طور که در مقاله قبلی توضیح داده شده یکی از تکنیک‌های جالب در الگوریتم‌های ژنتیک، نخبه‌گرایی است.

در این برنامه برای انجام این کار بدین‌صورت عمل کردیم که اگر عناصر آرایه ارزش مجموعه والد همه دارای یک مقدار بودند، عمل نخبه‌گرایی را انجام نمی‌دهیم، در غیراین‌صورت، از میان والد نسل قبلی ده والدی را انتخاب می‌کنیم که دارای مقدار تابع ارزش بیشتری بودند و در مجموعه والد نسل بعد قرار می‌دهیم. (کد 6)


http://www.shabakeh-mag.com/Data/Gallery/s73_Genetic-code07_s.jpg (http://shabakeh-mag.com/img.aspx?l=/data/gallery/s73_genetic-code07.jpg)
کد 7

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

2-7- ادامه، ادامه و ادامه ...

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

[tdkhakpur]

سلام
من کارم داخل bcb هست ولی خواستم سوال شما را بخوانم. برنامه اجرایی زیر کار شما را انجام میدهد. که هما الگوریتم ژنتیک را پیاده سازی میکند.