تصادف بعنوان یک استراتژی هوشمندانه

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

کلیدواژه ها:

الگوریتمهای تصادفی ، بازیهای مجموع صفر ، استراتژی پیروزی ، هرس فضای حالت ، رشد نمایی