الگوریتم‌های تصادفی

در شکل بالا نحوهٔ عملکرد الگوریتم های تصادفی را می‌توانید مشاهده کنید در این مقاله با جزییات این نوع الگوریتم آشنا می شوید.

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

== چکیده ==

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

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

== الگوریتم تصادفی ==

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

== میزان Reality الگوریتم های تصادفی ==

در این قسمت می خواهیم در مورد مطلب بسیار مهم میزان اطمینان به این نوع الگوریتم صحبت کنیم. همان طور که در شکل مشاهده می نمایید با افزایش محور افقی می‌توانیم با احتمال نزدیک به ۱۰۰ درصد نتیجهٔ حاصل نزدیک به واقعیت می‌باشد. (برای اطلاعات بیشتر از نحوهٔ بدست آوردن این صفحه می‌توانید به لینک آن مراجعه نمایید.)

== یک مثال از الگوریتم های تصادفی ==

به عنوان یک مثال واقعی، Quick Sort یکی از مهمترین الگوریتم هایتصادفی می‌باشد که بدترین حالت خیلی کم اتفاق می افتد و با تحلیل احتمالی این موضوع را ثابت می کنیم و همچنین نوع Randomize Quick Sort که یک الگوریتم تصادفی می‌باشد و صرفا به ورودی آرایه‌ای مربوط نمی‌باشد بلکه به یک عدد تصادفی تولید شده نیز مربوط می‌باشد.

به عنوان یک مثال فرض کنید در آرایه‌ای که شامل اعداد ۰ و۱ می‌باشد بطوری که نصف آن ها ۰ و نیمی دیگر ۱ می‌باشند حال می خواهیم با جستجو کردن از ابتدای آرایه اولین عنصر با مقدار ۱ را بیابیم در مسئله در بدترین حالت باید N/2 تا خانه را چک کنیم تا ۱ را پیدا کنیم ولی این حالت بسیار خاص می‌باشد و در حالت متوسط مشاهده می کنیم تعداد حالت جستجو برای این موضوع بسیار کمتر از این مقدار است.

== موارد استفاده الگوریتم های تصادفی ==

۱٫ الگوریتم‌های تصادفی بویژه در مواردی استفاده دارند که با یک دشمن یا مهاجم بد خواهی! مواجهیم که از روی عناد ورودی بدی را برای ما فراهم می‌کند(آنالیز رقابتی). به همین دلیل انتخاب تصادفی پایه رمزنگاری را تشکیل می‌دهد. این بدین معنی است که دشمن شما(!) نمی‌تواند با یک ورودی خاص بدترین حالت (Worst Case)شما را پدید بیاورد چون که به اعداد تصادفی تولید شده نیز مربوط می‌باشد.

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

== انواع الگوریتم های تصادفی ==

در مثال بالا الگوریتم تصادفی همیشه درست جواب می‌دهد تنها احتمال کوچکی وجود دارد که زمان زیادی برای رسیدن به پاسخ صرف کند. در بعضی مواقع ما از الگوریتم با اجازه دادن ایجاد احتمال کمی خطا انتظار سرعت بالاتر را داریم. الگوریتمهای از نوع اول را لاس وگاس (Las Vegas algorithms) و نوع اخیر را مونت کارلو (Monte Carlo algorithms) می‌نامند. مشاهده می‌کنیم که هر الگوریتم لاس وگاس با گرفتن جوابی احتمالاً نادرست در زمانی مشخص و محدود شده به الگوریتم مونت کارلو تبدیل می‌شود.

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

در آزمایشگاه لوس آلاموس در آمریکا دانشمندانی که بر روی پروژه سری منهتن کار می‌کردند، برای بررسی سیستم‌هایی که درآنها تعداد ذرات بالااست، مجبور به ابداع روش و یا الگوریتمی شدند که بعدها نام «مونت کارلو» بر آن قرار دادند.این الگوریتم برای نمونه گیری آماری از سیستم‌هایی با تعداد فضای فاز بالا به کار می‌رود.همچنین از این الگوریتم برای حل معادلات دیفرانسیل و انتگرال گیری معین استفاده می‌شود. دوالگوریتم مشهور مونت کارلو عبارتند از:

# الگوریتم متروپلیس
# الگوریتم مونت کارلو جنبشی یا n-fold way.

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

== منابع ==

* Knuth, Donald. The Art of Computer Programming (Volume 1 / Fundamental Algorithms), 2nd Printing. USA: Addison-Wesley Publishing, 1969.

* Cormen, Thomas H. (et al), Intorduction to Algorithms (2nd Edition), USA: McGraw-Hill, 2001. ISBN 0-07-013151-1

* هورویتز، الیس. طراحی الگوریتم‌ها، چاپ دوم (مترجم: علیخانزاده، امیر). مشهد: پرتونگار، ۱۳۸۵.

ISBN 964-6735-12-6

* کرمن/لیرسون/ریورست/استین، کتاب طراحی مقدمه‌ای بر طراحی الگوریتم ها، چاپ چهارم(مترجم : گروه مهندسی پژوهشی خوارزمی) فصل ششم، مشهد(۱۳۸۷)

== جستارهای وابسته ==

* فلوچارت
* الگوریتم‌های مرتب‌سازی
* الگوریتم کروسکال