מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תת-מחרוזת משותפת ארוכה ביותר/תשובה

המבנה הרקורסיבי של הבעיה

ראשית מספר סימונים:

1. כפי שצוין בשאלה, נגדיר את אורך $\displaystyle X$ כ$\displaystyle m$, ואת אורך $\displaystyle Y$ כ$\displaystyle n$.
2. נסמן את הרישה ה$\displaystyle i$ של מחרוזת $\displaystyle X$ כ$\displaystyle X_{i}$. במילים אחרות, $\displaystyle X_{i}=x_{1},...,x_{i}$.‏
3. נגדיר כ$\displaystyle l(i,j)$ את אורך הLCS של $\displaystyle X_{i}$ ו$\displaystyle Y_{j}$. במילים אחרות, $\displaystyle l(i,j)$ היא אורך תת-הסדרה הארוכה ביותר המשותפת ל$\displaystyle X_{i}$ ו$\displaystyle Y_{j}$.

עכשיו תורכם: וודא שהמך מבין מדוע לפי הגדרה זו, $\displaystyle l(m,n)$ הוא אורך הLCS של $\displaystyle X$ ו$\displaystyle Y$.

משפט: $\displaystyle l(i,j)$ מקיים את הנוסחה הבאה: אם $\displaystyle i=0$ או $\displaystyle j=0$,‏ אז $\displaystyle l(i,j)=0$. אם לא,‏ אז: אם $\displaystyle x_{i}=y_{j}$, אז $\displaystyle l(i,j)=1+l(i-1,j-1)$. אם $\displaystyle x_{i}\neq y_{j}$, אז $\displaystyle l(i,j)=\max\{l(i-1,j),l(i,j-1)\}$.

הוכחה: אם $\displaystyle i=0$ או $\displaystyle j=0$, אז (לפחות) אחת המחרוזות היא המחרוזת הריקה, ורק המחרוזת הריקה יכולה להיות תת-מחרוזת של המחרוזת הריקה. למחרוזת הריקה יש אורך 0, ומכאן החלק הראשון של המשפט.

מכאן נניח ששתי המחרוזות אינן ריקות.

נניח ש$\displaystyle x_{i}=y_{j}$. ראשית, קל לראות שבהכרח תווה האחרון של $\displaystyle Z$ הוא $\displaystyle x_{i}$ - אם זה לא היה המצב, אז $\displaystyle Zx_{i}$ גם היא מחרוזת משותפת ל$\displaystyle X_{i}$ ו$\displaystyle Y_{j}$, דבר שנוגד עפ"י ההגדרה את היותה של $\displaystyle Z$ תת-המחרוזת המשותפת הארוכה ביותר. נחשוב כעת על כל תתי המחרוזות המשותפות מהצורה $\displaystyle Z'x_{i}$: עבור כל אחת מהן, קל לראות ש$\displaystyle Z'$ היא תת-מחרוזת משותפת ל$\displaystyle X_{i-1}$ ו$\displaystyle Y_{j-1}$, ולכן בהכרח הארוכה שבהן היא זו שהרישה שלה היא הLCS של $\displaystyle X_{i-1}$ ו$\displaystyle Y_{j-1}$.

לחלופין, נניח ש$\displaystyle x_{i}\neq y_{j}$; יש שלוש אפשרויות:

1. $\displaystyle Z$מסתיימת ב$\displaystyle x_{i}$ - אם כן, הLCS בהכרח מהצורה $\displaystyle Z'x_{i}$, כאשר $\displaystyle Z'$ היא הLCS של $\displaystyle X_{i}$ ו$\displaystyle Y_{j-1}$.
2. $\displaystyle Z$ מסתיימת ב$\displaystyle y_{j}$ - אם כן, הLCS בהכרח מהצורה $\displaystyle Z'y_{j}$, כאשר $\displaystyle Z'$ היא הLCS של $\displaystyle X_{i-1}$ ו$\displaystyle Y_{j}$.
3. $\displaystyle Z$אינה מסתיימת ב$\displaystyle x_{i}$, וכן אינה מסתיימת ב$\displaystyle y_{j}$ - אם זה המצב, אז הLCS של $\displaystyle X_{i-1}$ ו$\displaystyle Y_{j-1}$ הוא הLCS של $\displaystyle X_{i-1}$ ו$\displaystyle Y_{j}$ (וכן גם הLCS של $\displaystyle X_{i}$ ו$\displaystyle Y_{j-1}$), כך ששתי הבדיקות הקודמות מכסות כבר (פעמיים אפילו) מקרה זה.

מציאת אורך הLCS

להלן פסוודו-קוד למציאת אורך הLCS.

1	L = Make-Matrix(m, n)

2	for i in [1, ..., m]
3		for j in [1, ..., n]
4			L[i][j] = Nil

LCS-Length(i, j)
1	if L[i][j] == Nil
2		if i == 0 or j == 0
3			return 0
4		else if X[i] == Y[j]
5			L[i][j] = 1 + LCS-Length(i - 1, j - 1)
6		else
7			guess-x = LCS-Length(i - 1, j)
8			guess-y = LCS-Length(i, j - 1)
		
9			L[i][j] = Max(guess-x, guess-y)

10	return L[i][j]

ארבע השורות הראשונות מאתחלות מטריצה המשמשת לmemoization, והפונקציה LCS-Length מוצאת את את האורך המבוקש. 1-4 מייצרות מטריצה (גלובלית) שכל אחד מאיבריה מאותחל לNil.‏ 2-9 של LCS-Length, פועלות בדיוק לפי נוסחת הנסיגה הקודמת (שאת נכונותה כבר הראינו). המטריצה L, בפרט ב1 של LCS-Length, מטפלות במצב בו הפונקציה נקראת עם פרמטרים שאתם היא כבר נקראה בעבר.

ניתוח סיבוכיות

נגדיר את $\displaystyle T'(i,j)$ כזמן שאורכת LCS-Length בהנחה שכל אחת מקריאותיה הרקורסיביות היא $\displaystyle O(1)$. קל לראות ש$\displaystyle T'(i,j)=O(1)$.

זמן הריצה של LCS-Length(m, n) חסום מלמעלה על ידי $\displaystyle \sum _{i=0}^{m}\sum _{j=0}^{n}[T'(i,j)]=\Theta (m\cdot n)$. חוץ מכך ישנו האתחול 1-4 שאורך גם כן $\displaystyle \Theta (m\cdot n)$. הזמן הכולל, לכן, הוא $\displaystyle O(m\cdot n)$.

הדפסת איברי הLCS

ראשית נשנה מעט את הפסוודו-קוד הקודם.

1	L = Make-Matrix(m, n)
2	D = Make-Matrix(m, n)

3	for i in [1, ..., m]
4		for j in [1, ..., n]
5			L[i][j] = Nil


LCS-Length(i, j)
1	if L[i][j] == Nil
2		if i == 0 or j == 0
3			return 0
4		else if X[i] == Y[j]
5			L[i][j] = 1 + LCS-Length(i - 1, j - 1)
6			D[i][j] = 'b'
7		else
8			guess-x = LCS-Length(i - 1, j)
9			guess-y = LCS-Length(i, j - 1)
		
10			L[i][j] = Max(guess-x, guess-y)
	
11			if L[i][j] == guess-x
12				D[i][j] = 'x'
13			else
14				D[i][j] = 'y'	

15	return L[i][j]

המטריצה הגלובלית D מתארת בכניסה ה$\displaystyle (i,j)$ את ההחלטה לגבי הLCS של $\displaystyle X_{i}$ ו$\displaystyle Y_{j}$:

1. 'x' מסמלת את ההחלטה לוותר על התו האחרון ב$\displaystyle X_{i}$.
2. 'y' מסמלת את ההחלטה לוותר על התו האחרון ב$\displaystyle Y_{j}$.
3. 'b' מסמלת את ההחלטה לוותר על התו האחרון בשניהם. זה בדיוק המצב בו $\displaystyle X_{i}=Y_{j}$ נמצא כחלק מהLCS.הפונקציה הבאה מדפיסה את הLCS כאשר קוראים לPrint-LCS(m, n):

Print-LCS(i, j)
1	if i > 1 and j > 1
2		if D[i][j] == 'x':
3			Print-LCS(i - 1, j)
4		else if D[i][j] == 'y':
5			Print-LCS(i, j - 1)
6		else
7			Print-LCS(i - 1, j - 1)

1	if D[i][j] == 'b':
2		Print(X[i])

קל לראות שהסיבוכיות עדיין $\displaystyle \Theta (m\cdot n)$: השינויים בLCS-Length אינם משנים את סיבוכיותה; כל קריאה לPrint-LCS(i, j) מורידה (לפחות) את אחד הארגומנטים שלה ב1, ולכן היא יכולה להיקרא לכל היותר $\displaystyle m+n$ פעמים. הסיבוכיות, לכן, היא $\displaystyle \Theta (m\cdot n)$ + $\displaystyle O(m+n)$ = $\displaystyle \Theta (m\cdot n)$.