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

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

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

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

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

منابع
  1. Du, Ko and Hu, Design and Analysis of Approximation Algorithms, 18.
  2. Bach and Shallit, Algorithmic Number Theory: Efficient algorithms, 46.
  3. Ausiello, Complexity and Approximability Properties: Combinatorial Optimization Problems and Their Approximability Properties, 14.
  4. Korte and Vygen, Combinatorial Optimization: Theory and Algorithms, 387.
  5. Drozdek, Data Structures and Algorithms in Java, 74.
  • Bach, E.; Shallit, J.O. (1996). Algorithmic Number Theory: Efficient algorithms. Algorithmic Number Theory. MIT Press. ISBN 9780262024051. Retrieved 2013-10-31.
  • Du, D.; Ko, K.I.; Hu, X. (2011). Design and Analysis of Approximation Algorithms. Probabilities and Potential B. Springer. ISBN 9781461417019. Retrieved 2013-10-31.
  • Korte, B.H.; Vygen, J. (2012). Combinatorial Optimization: Theory and Algorithms. Algorithms and combinatorics. Springer. ISBN 9783642244889. Retrieved 2013-10-31.
  • Drozdek, A. (2005). Data Structures and Algorithms in Java. Course Technology. ISBN 9780534492526. 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. ISBN 9783540654315. Retrieved 2013-10-31.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.