(הנוסע המתמיד האוקלידי)
נתונות נקודות במישור. כל נקודה מייצגת שדה תעופה, לצורך העניין. סוכן נסיעות מתחיל את מסלולו בשדה התעופה השמאלי ביותר; עליו לעבור בכל שדה תעופה ולנחות בשדה התעופה שממנו יצא לדרכו. מחיר הטיסה משדה תעופה אחד לשני הוא המרחק האוקלידי בין שני השדות. על הנוסע למצוא את המסלול שעלותו הכוללת נמוכה ככל האפשר.
כדאי לדעת:
לבעיית הנוסע המתמיד האוקלידי אין אלגוריתם יעיל ידוע - כל האלגוריתמים הידועים עובדים בזמן אקספוננציאלי. למרות שהדבר לא הוכח, יש סיבות המרמזות לכך שלא ייתכן אלגוריתם יעיל לבעיה זו.
שאלה זו דנה בגרסה קלה יותר של הבעיה.
הגדרה:
(מסלול ביטוני)
מסלול הוא ביטוני אם הוא מורכב משני תתי מסלולים: בראשון נעים בכיוון ימין, ובשני נעים מימין חזרה לכוון שמאל.
דוגמה:
בתרשים הבא, A מראה מישור בעל נקודות; B מראה את המסלול הקצר ביותר, אך המסלול אינו ביטוני.
מישור ומסלולים.
בתרשים הבא, A וB מראים כל אחד מסלול ביטוני אפשרי.
מסלולים ביטוניים.
בשאלה זו עליך למצוא אלגוריתם למציאת המסלול הביטוני האוקלידי הזול ביותר לכל קבוצת נקודות במרחב: אנא תאר אלגוריתם יעיל המוצא את עלות המסלול הנמוכה ביותר.
שימו לב:
#הנח שP הוא מערך גלובלי בעל אורך המתאר את הנקודות.
כדי לגשת לקואורדינטות הX והY של הנקודה ה, השתמש בP[i].x ובP[i].y, בהתאמה.
הנח שP ממוין בסדר עולה על פי קואורדינטות הX של נקודותיו (ולכן P[1] היא בהכרח נקודת המוצא של הנוסע, לדוגמה).
הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל, מ פונה ימינה, אינו מגיע לאף נקודה אחרת מכוון ימין, ומכסה את כל הנקודות משמאלה ל. לכן, בהכרח, מדובר במסלול שעובר נקודה אחרי נקודה מ ל.
הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל, מ ימינה ל, ומכסה את כל הנקודות משמאלה ל. נסמן כ את הנקודה שאליה עובר המסלול ישירות מ; A בתרשים הבא מציג זאת. מקרה 2 בהוכחת נוסחת הנסיגה. היות שהוכחנו למעלה שלמסלולים שקולים יש מחיר זהה, נוכל לטעון שB בתרשים הקודם בעל אותו מחיר כA.
הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל, מ ימינה ל, ומכסה את כל הנקודות משמאלה ל. היות ש, המסלול חייב להתחיל במעבר ישיר (שמאלה) מ ל. מקרה 3 בהוכחת נוסחת הנסיגה.