الگوریتم غیرقطعی

در علوم رایانه الگوریتم غیرقطعی به الگوریتمی گفته می‌شود که رفتار غیرقطعی دارد. برای نمونه در یکی از مراحل چنین الگوریتمی مقدار ۰ یا ۱ به صورت غیرقطعی (تصادفی) به یک متغیر نسبت داده می‌شود، رفتار الگوریتم از این نقطه به بعد دو مسیر متفاوت خواهد داشت. اگر الگوریتمی k بار چنین حرکتی داشته باشد، تعداد مسیرهای قطعی آن 2^k خواهد بود. الگوریتم‌های غیرقطعی لزوماً متقارن نیستند به این معنی که اگر مقدار ورودی‌های غیرقطعی آن معکوس شوند، جواب لزوماً معکوس نمی‌شود. این الگوریتم‌ها در مرحلهٔ تصمیم‌گیری خود یک حالت را از میان تعدادی متناهی‌ای از حالت‌های ممکن برمی‌گزینند. اگر دست کم یکی از حالت‌های ممکن بتواند خروجی مورد انتظار را برای یک ورودی مشخص به بار آورد، می‌گویند الگوریتم آن خروجی را می‌پذیرد و در غیر این صورت خروجی را رد می‌کند (یعنی خروجی مورد انتظار را در هیچ مسیری تولید نمی‌کند یا اینکه الگوریتم به صورت نامتناهی ادامه پیدا می‌کند).

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

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

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

• نظریه پیچیدگی محاسباتی
• الگوریتم موازی
• الگوریتم‌های تصادفی
• اتوماتون تعیین‌ناپذیر متناهی
• ماشین حالات متناهی
• ان پی (کامل)
• مسئله برابری پی و ان‌پی

منابع

• Bach, E.; Shallit, J.O. (1996). Algorithmic Number Theory: Efficient algorithms. Algorithmic Number Theory (به انگلیسی). MIT Press. Retrieved 2013-10-31.
• Du, D.; Ko, K.I.; Hu, X. (2011). Design and Analysis of Approximation Algorithms. Probabilities and Potential B (به انگلیسی). Springer. Retrieved 2013-10-31.
• Korte, B.H.; Vygen, J. (2012). Combinatorial Optimization: Theory and Algorithms. Algorithms and combinatorics (به انگلیسی). Springer. Retrieved 2013-10-31.
• Drozdek, A. (2005). Data Structures and Algorithms in Java (به انگلیسی). Course Technology. Retrieved 2013-10-31.
• Ausiello, G. (1999). Complexity and Approximability Properties: Combinatorial Optimization Problems and Their Approximability Properties. Springer-electronic-Media (به انگلیسی). U.S. Government Printing Office. Retrieved 2013-10-31.