9.5 תת-סדרה משותפת ארוכה ביותר

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

בעיה נוספת אשר יש לה פתרון יעיל על ידי שימוש בגישת התכנון הדינאמי היא מציאת תת-סדרה משותפת (common subsequence) ארוכה ביותר. תת-סדרה של סדרה נתונה היא פשוט הסדרה הנתונה לאחר שהוצא ממנה מספר כלשהו (אולי 0) של איברים. סדרה היא תת-סדרה משותפת של שתי סדרות, אם היא תת-סדרה של כל אחת מהן.

הבעיה

בבעיה של תת-סדרה משותפת ארוכה ביותר נתונות שתי סדרות איברים X ו- Y, ויש לקבוע מהי תת-הסדרה הארוכה ביותר של איברים המופיעים הן ב- X והן ב- Y.

פתרון הגישה הישירה

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

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

בעיית תת-הסדרה המשותפת הארוכה ביותר היא בעלת תת-מבנה אופטימלי. אנו אומרים כי בעיה היא בעלת תת-מבנה אופטימלי, אם פתרון אופטימלי לבעיה מכיל בתוכו פתרונות אופטימליים לתת-בעיות. תכונה זו מאפשרת יצירת אלגוריתמים לפתרון הבעיה הכוללת מתוך גישה של תכנון דינאמי. גישה זו מנצלת את העובדה שפתרון הבעיה של מציאת תת-הסדרה הארוכה ביותר של סדרות {X={x_1, x_2,..., x_m ו- Y={y_1, y_2,..., y_n}, יכול להתקבל מפתרון תת-בעיה אחת או שתי תתי-בעיות. אם האיבר האחרון זהה בשתי הסדרות (x_m=y_n), מציאת תת-סדרה משותפת ארוכה ביותר של x_m-1ו- y_n-1, והוספה של x_m=y_n לתת-סדרה זו, תספקנה את הפתרון לבעיה. אם האיבר האחרון בשתי הסדרות אינו זהה, פתרון של שתי תתי-בעיות יספק את הפתרון הכללי לבעיה: מציאת תת-סדרה משותפת ארוכה ביותר של x_m-1ו- y, ומציאת תת-סדרה משותפת ארוכה ביותר של xו- y_n-1, כאשר הארוכה מבין השתיים תהווה את פתרון הבעיה. מאחר שפתרון כל אחת מתתי-הבעיות יכול להתקבל באותו אופן מפתרון של תתי-תתי-בעיות וכן הלאה, ניתן לנסח אלגוריתם רקורסיבי בזמן מעריכי לפתרון הכולל של הבעיה. אולם, גישת התכנון הדינאמי מנצלת את העובדה שישנן רק O(mn) תתי-בעיות שונות, ומחשבת את פתרונותיהן "מלמטה למעלה", כלומר, באופן שפתרון כל תת-בעיה יסתמך על פתרונות קודמים של תתי-בעיות שאוחסנו בזיכרון. זמן הריצה של אלגוריתם דינאמי כזה הוא O(mn) - ושוב אנו רואים כי ניתן לקצר את זמן הביצוע בתמורה לשימוש (חכם) במקום נוסף בזיכרון!

מידע נוסף בנושא

הרצאה בנושא מאת קריק פרוס מאונ' פיטסבורג

פסאדו-קוד מאת ג'ון סטסקו מג'ורגיה-טק

מושגים

תת-סדרה

תת-סדרה של סדרה נתונה היא פשוט הסדרה הנתונה לאחר שהוצא ממנה מספר כלשהו (אולי 0) של איברים.

תת-סדרה משותפת

סדרה היא תת-סדרה משותפת של שתי סדרות, אם היא תת-סדרה של כל אחת מהן.

תת-מבנה אופטימלי

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

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