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

[kondor1706]

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

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

 

[kobi2579]

LCS

האלגוריתם בנוי למעשה מ-2 פונקציות עיקריות: SPL Extract_LCS האלגוריתם מאפס תחילה את השורה והעמודה ה-0 של המטריצה המתאימה לאורך LCS של שתי סדרות שאחת מהן ריקה. לאחר מכן האלגוריתם מחשב שורה אחר שורה תוך שימוש בנוסחאות הנסיגה הרקורסיביות. לאחר שסימנו את ביצוע האלגוריתם אורך תת הסידרה המקסימלית שלנו ימצא באיבר: TL[n,m] אז נשתמש באלג': extract_LCS המחשב את תת הסידרה המקסימלית עצמה. כדי לבנות את תת הסיגרה המשותפת המקסימלית מבצעים סיור מ-TL[1,1] ועד ל:TL[n,m] ובמהלך הסיור בונים את תת הסדרה המשותפת המקסימלית מן הסוף להתחלה.