בעיית העץ של שטיינר

בעיית העץ של שטיינר (באנגלית: Steiner tree problem), שנקראת על שם יאקוב שטיינר, היא מונח המתאר קבוצה של בעיות באופטימיזציה קומבינטורית. בעיית שטיינר בניסוחה הכללי ביותר דורשת לייצר את הקישור הקצר ביותר בין קבוצה נתונה של אובייקטים בהינתן פונקציית מרחק מוגדרת מראש. וריאנט אחד של הבעיה, שלעיתים קרובות משמש כמונח נרדף לבעיית עץ שטיינר, הוא בעיית עץ שטיינר האוקלידית: בהינתן קבוצה של נקודות במישור, יש למצוא רשת בעלת אורך מינימלי המקשרת בין כל הנקודות.

היסטוריה

הפתרון במקרה של ארבע נקודות - ישנן שתי נקודות שטיינר S₁ ו- S₂.

המקור המוקדם ביותר לבעיית עץ שטיינר מופיע בהתכתבות של פייר דה פרמה (1601–1665), בה נידון המקרה הלא טריוויאלי הפשוט ביותר של בעיית שטיינר ל-n נקודות - המקרה הפרטי של n = 3. פרמה תיאר את הבעיה הזאת ב-1643 בחיבורו "שיטה לקביעת מקסימום ומינימום ומשיקים לקווים עקומים". הפתרון הידוע המוקדם ביותר לבעיה שהציע פרמה היה בנייה גאומטרית של הפיזיקאי והמתמטיקאי האיטלקי אוונג'ליסטה טוריצ'לי (1608–1647). הבנייה של טוריצ'לי הראתה שהנקודה שסכום מרחקיה מקודקודי המשולש מינימלי היא הנקודה בה רואים כל אחת מצלעות המשולש בזווית שווה, דהיינו 120 מעלות.

את בעיית שטיינר המוכללת הציע לראשונה קרל פרידריך גאוס (1777–1855) במכתב לחברו היינריך כריסטיאן שומאכר משנת 1836, שעסק בבעיית שטיינר במקרה של 4 נקודות. גאוס טען שבעיה מעניינת יותר היא למצוא את הרשת הקצרה ביותר שמחברת בין כל הנקודות, במקום את הנקודה שסכום מרחקיה מכל הנקודות מינימלי. הוא טען שבאמצעות שימוש ברשת (יותר מנקודת שטיינר אחת) ניתן לקצר את האורך הכולל של קווי הקישור שנמתחים בין הנקודות. באותו מכתב דן גאוס בכל הטופולוגיות האפשריות של הפתרון לבעיה, והציע להשתמש בפתרון הבעיה כדי לקצר את האורך הכולל של מסילות הרכבת שיחברו בין ארבע הערים הרבורג, ברמן, הנובר ובראונשוויג.

הוכחת הטענה של טוריצ'לי

עץ שטיינר בעבור שלוש נקודות A,B ו-C. נקודת שטיינר S ממוקמת בנקודת פרמה של המשולש ABC.

לטענה שנקודת שטיינר של משולש ABC ממוקמת בנקודת פרמה של המשולש יש הוכחה פיזיקלית יפה. נדמיין שולחן בצורת מנסרה שבסיסה זהה למשולש שבבעיה. נדמיין שלושה חוטים העוברים דרך כל אחד מקודקודי הבסיס העליון של המנסרה (שצורתו כצורת משולש ABC), המחוברים ביניהם באמצעות צמה הנמצאת בפנים המשולש. כעת נתלה על כל אחד מקצות החוטים משקולת שמסתה m. ברור שהמערכת תתייצב בנקודה בה האנרגיה הפוטנציאלית הכוללת שלה מינימלית, וכיוון שמסת כל אחת מהמשקולות זהה, נקודה זו היא גם הנקודה בה סכום הגבהים של המשקולות מעל הקרקע מינימלי. ניתן להראות בנקל שבמצב היציב הזה הצמה תתייצב בנקודת שטיינר של המשולש - הנקודה ממנה סכום המרחקים אל קודקודיו מינימלי. כיוון שהמתיחות בכל אחד מהחוטים זהה ושווה למשקל המשקולת, מחשבון וקטורי פשוט ניתן להראות שהקונפיגורציה היציבה היחידה של החוטים תהיה כאשר הם נפגשים בצמה בזוויות של 120 מעלות, כלומר בנקודת פרמה של המשולש.

קישורים חיצוניים

מדיה וקבצים בנושא בעיית העץ של שטיינר בוויקישיתוף

• בעיית העץ של שטיינר, באתר MathWorld (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

27281287בעיית העץ של שטיינר