مدل رشد بلور از یک هسته بلور رشد خواهد کرد،
شرح مسئله :یک صفحه n*n داریم مشابه صفحه شطرنج . می خواهیم مهره ها را روی آن قرار داده به نحوی که مانند قرار گرفتن وزیرها در خانه های شطرنج در خطوط افقی و عمودی و اریب با یکدیگر برخورد نکنند. مسئله را برای داشتن چند نقطه اولیه مشخص و یافتن جای بقیه مهره ها باید حل کنیم .
قبلا برنامه ++C را برای حل این مسئله نوشتم . بطور طبيعي وقتی تعداد ابعاد صفحه به حدود 100 رسید کامپیوتر موجود از رسیدن به جواب طی یک روز ناتوان گردید. ( در واقع نخواستم ببینم چه مدت زمان طول می کشد تا جواب مسئله پیدا شود) این راه را غیر عملی یافتم .
در اینجا متوجه شدم که نیاز به یک الگوریتم جدید داریم و جایزه مطرح شده ؛ برای یافتن یک الگوریتم جدید است . از این الگوریتم در موارد دیگر مثل یافتن رمز رایانه و غیره نیز استفاده می شود . از این جهت شرکت هایی که روی ایمنی رمز بانکها و تبادلات مالی کار می کنند خیلی علاقمند هستند راه حل را یافته و ایمنی معاملات جهانی را حفظ نمایند . بدین ترتیب می توان پی برد که جایزه مذکور از منابع شرکتهای خدماتی بانکها باشد.
اما راه حل :
مقدمه : اگر یک هسته تک بلور را در مایع همگن آن ماده قرار دهید تک بلور رشد خواهد کرد تا به تعادل برسد. در اینجا توزضیح ساخت تک بلورها را نمی آوریم .
در صنعت تک بلور را برش می دهند و از ویفرها برای ساخت نیمه هادی ها استفاده می کنند .(نکته : بلورهای هر ماده ای به صورت ویژه "خاص آن ماده" رشد می کنند . مانند مکعب مرکز دار و یا مکعب با یک اتم در هر ضلع و غیره )
برای حل این مسئله از الگوریتم رشد بلوری استفاده شده . محیط کشت را صفحه شطرنج و روابط قرار گرفتن اتمها را مطابق قوانین قرارگیری وزیرها در نظر میگیریم . همه حالات محتمل در رشد بلورهای طبیعی نیز ممکن است رخ دهد .
برای شروع فواصل نقاط اولیه موجود را محاسبه می کنیم و دو نقطه اولیه نزدیکتر را به عنوان هسته اولیه شروع رشد بلور مشخص می کنیم . دنبال یافتن همه راه حل ها نیستیم . بلکه دنبال یافتن یک راه حل قابل قبول هستیم . برای این کار فواصل بین دو نقطه نزدیکتر را پر می کنیم . ( با الگوریتمهای موجود ) حالا به سمت نقطه نزدیک بعدی حرکت می کنیم و فواصل بین این بلور را با نقطه ثابت بعدی پر می کنیم . این کار را برای بقیه نقاط موجود انجام می دهیم تا شبکه کامل گردد.
آن چیزی که باعث کاهش سرعت کامپیوتر می شود کنترل همه نقاط ممکن است . اما وقتی رنج قرار گیری هسته بلور بعدی محدود گردد ، سرعت عملیات به میزان چشمگیری کاهش خواهد یافت . در واقع حجم بزرگی از محاسبات در این الگوریتم حذف می گردد.
آن چیزی که باعث کاهش سرعت کامپیوتر می شود کنترل همه نقاط ممکن است . اما وقتی رنج قرار گیری هسته بلور بعدی محدود گردد ، سرعت عملیات به میزان چشمگیری کاهش خواهد یافت . در واقع حجم بزرگی از محاسبات در این الگوریتم حذف می گردد.
امکان استفاد از شبکه چند هسته ای هم هست گر چه زمان جواب دهی خیلی کمتر خواهد شد ، اما امکان رسیدن به حالتی که جواب نیست افزایش میابد .
پیشنهاد مناسب رشد بلور از هسته اولیه است به نحوی که به تدریج سایر نقاط ثابت را پر کند . سپس در انتها پر کردن جای خالی اطراف صفحه میرسد. ( نقاط داخلی در الگوریتم پر شده اند )
پیشنهاد مناسب رشد بلور از هسته اولیه است به نحوی که به تدریج سایر نقاط ثابت را پر کند . سپس در انتها پر کردن جای خالی اطراف صفحه میرسد. ( نقاط داخلی در الگوریتم پر شده اند )
خلاصه الگوریتم
1- نقاط ورودی دریافت می گردند . ( از این به بعد هر نقطه را وزیر می نامیم )
2- فواصل وزیر ها تعیین می شود و امتیاز دهی میگردد .
3- هسته اولیه رشد پیدا می شود ( نزدیکترین دو نقطه از مجموعه نقاط )
4- فواصل بین دو نقطه پر می شود .
5- نقطه بعدی نزدیک انتخاب و فواصل پر می شود .
6- مرحله 5 تا تمام شدن نقاط اولیه تکرار می گردد.
7- فواصل کناری که فاقد نقطه هستند پر می شوند.
8- پایان
هیچ نظری موجود نیست:
ارسال یک نظر