בעיית הסוכן הנוסע – הבדלי גרסאות

תיקנתי קישור
מ (ביטול גרסה 16017298 - ע"ע עצרת (התעלמת מהסימן !))
(תיקנתי קישור)
 
פתרון פשוט לבעיה הוא בדיקת כל המסלולים האפשריים. אלא, שכאשר יש <math>n</math> ערים, פתרון זה מצריך בדיקה של <math>n!</math> אפשרויות, ([[עצרת]] של מספר הערים), ולכן דרך זו הופכת מהר מאוד לבלתי מעשית (לבלתי [[חישוב יעיל|יעילה]], במינוח של [[מדעי המחשב]]). דוגמה להמחשת הבעיה: אם ישנן 70 ערים בהן על הסוכן לבקר, יצטרך הסוכן לבחון [[עצרת|!]]70 מסלולי נסיעה אפשריים, אשר מהווים מספר רב יותר ממספר האטומים ביקום כולו.
בתורת הסיבוכיות הוכח שבעיה זו נכללת בקטגוריה [[NP (מחלקת סיבוכיות)#בעיות NP-קשות (NP-Hard) ובעיות NP-שלמות (NPC)|{{כ}}NP-קשה]], והצגתה כ[[בעיית הכרעה]] ("האם קיים מסלול שאורכו פחות מ-x ק"מ?") היא בקטגוריה [[NP-שלמה]]. ניתן להוכיח שהוספת דרישה שבתום המסע יחזור הסוכן הנוסע לעיר שממנה יצא אינה משנה את ה[[סיבוכיות]] של הבעיה.
 
הקושי למצוא פתרון אופטימלי לבעיה דוחף למציאת פתרון קרוב לאופטימלי, באמצעות [[אלגוריתם קירוב]] (ראו תיאור של [[אלגוריתם קירוב#דוגמה לאלגוריתם קירוב|אלגוריתם קירוב לבעיית הסוכן הנוסע]]). [[אלגוריתם חמדן]] הוא דרך מעשית נוספת להשגת פתרון שאינו בהכרח אופטימלי.
24

עריכות