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