תוכן עניינים:
הגדרה - מה המשמעות של אלגוריתם לא-דטרמיניסטי?
אלגוריתם לא דטרמיניסטי יכול לספק תפוקות שונות לאותה קלט בהוצאות להורג שונות. בניגוד לאלגוריתם דטרמיניסטי שמייצר פלט בודד לאותה קלט גם בריצות שונות, אלגוריתם לא דטרמיניסטי נוסע בנתיבים שונים כדי להגיע לתוצאות השונות.
אלגוריתמים לא-דטרמיניסטיים מועילים למציאת פתרונות משוערים, כאשר קשה או לגזור פיתרון מדויק באמצעות אלגוריתם דטרמיניסטי.
Techopedia מסביר את האלגוריתם הלא-דטרמיניסטי
דוגמה אחת לאלגוריתם לא דטרמיניסטי היא ביצוע אלגוריתמים במקביל בתנאי מירוץ, שיכולים להציג תפוקות שונות בריצות שונות. בשונה מאלגוריתם דטרמיניסטי הנוסע נתיב יחיד מכניסה לפלט, אלגוריתם לא-דטרמיניסטי יכול לעבור נתיבים רבים, כאשר חלקם מגיעים לאותן תפוקות, ואחרים מגיעים לפלטים שונים. תכונה זו משמשת באופן מתמטי במודלים של חישוב לא-דטרמיניסטי כמו אוטומט סופי שאינו דטרמיניסטי.
אלגוריתם לא דטרמיניסטי מסוגל לבצע במחשב דטרמיניסטי שיש לו מספר בלתי מוגבל של מעבדים מקבילים. לאלגוריתם לא דטרמיניסטי בדרך כלל שני שלבים ושלבי פלט. השלב הראשון הוא שלב הניחוש, העושה שימוש בתווים שרירותיים כדי להריץ את הבעיה.
השלב השני הוא שלב האימות, שמחזיר אמת או כוזב עבור המחרוזת שנבחרה. ישנן בעיות רבות שניתן להמשיג בעזרת אלגוריתמים לא-דטרמיניסטיים כולל הבעיה הבלתי פתורה של P לעומת NP בתורת המחשוב.
משתמשים באלגוריתמים לא-דטרמיניסטיים בפתרון בעיות המאפשרות תוצאות מרובות. כל תוצאה שהאלגוריתם הלא-דטרמיניסטי מייצר תקפה, ללא קשר לבחירות שעשה האלגוריתם במהלך הביצוע.
