9.6 חלוקה אופטימלית למשולשים (Optimal Triangulation)

מבנה נתונים ואלגוריתמים

טריאנגולציה היא בעיה גיאומטרית של חלוקת מצולע קמור למשולשים. מצולע נקרא קמור אם בהינתן שתי נקודות על שפת המצולע או בפנים המצולע , כל הנקודות על הקטע המחבר ביניהן נמצאות גם הן על שפתו של המצולע או בפנים המצולע. טריאנגולציה היא הצעד הראשון בפתרון של מספר בעיות הנדסה, ולכן מציאת חלוקה אופטימלית הינה בעיה חשובה בפני עצמה.

הבעיה

כל מצולע קמור יכול להתחלק למשולשים. הבעיה היא למצוא את החלוקה האופטימלית. כלומר, יש למצוא קבוצה של מיתרים המחלקים את המצולע באופן כזה שסכום היקפי המשולשים יהיה מינימלי.

הפתרון בגישה הדינאמית

כפי שכבר הוזכר, בעיה היא בעלת תת-מבנה אופטימלי, אם פתרון אופטימלי לבעיה מכיל בתוכו פתרונות אופטימליים לתת-בעיות, וקיומה של תכונה זו מאפשרת יצירת אלגוריתמים לפתרון הבעיה הכוללת מתוך גישה של תכנון דינאמי. לבעיית הטריאנגולציה האופטימלית יש תת-מבנה אופטימלי: משקלה של טריאנגולציה אופטימלית T של מצולע בעל n+1 קדקודים P={v_0, v_1,..., v_n} המכילה את המשולש _Dv₀v_kv_n עבור k כלשהו המקיים n-1 ³ k ³ 1, הוא פשוט סכום המשקלים של _Dv₀v_kv_n ושל משולשים בטריאנגולציה של שני תתי-המצולעים {v_0, v_1,..., v_k} ו- {v_k, v_k+1,..., v_n}. הטריאנגולציות של תתי-המצולעים הנקבעות על ידי T הן בהכרח אופטימליות, שכן טריאנגולציה במשקל נמוך יותר של אחד מהם הייתה סותרת את האופטימליות של T.

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

מושגים

מצולע קמור (convex polygon)

.מצולע נקרא קמור אם בהינתן שתי נקודות על שפת המצולע או בפנים המצולע , כל הנקודות על הקטע המחבר ביניהן נמצאות גם הן על שפתו של המצולע או בפנים המצולע.

המשך ל: התאמת מחרוזות חזור ל: תוכן עניינים