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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

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

  1. כפי שצוין בשאלה, נגדיר את אורך כ, ואת אורך כ.
  2. נסמן את הרישה ה של מחרוזת כ. במילים אחרות, .‏
  3. נגדיר כ את אורך הLCS של ו. במילים אחרות, היא אורך תת-הסדרה הארוכה ביותר המשותפת ל ו.


עכשיו תורכם:

וודא שהמך מבין מדוע לפי הגדרה זו, הוא אורך הLCS של ו.



משפט:

מקיים את הנוסחה הבאה:

  1. אם או ,‏ אז .
  2. אם לא,‏ אז:
    1. אם , אז .
    2. אם , אז .



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


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

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

לחלופין, נניח ש; יש שלוש אפשרויות:

  1. מסתיימת ב - אם כן, הLCS בהכרח מהצורה , כאשר היא הLCS של ו.
  2. מסתיימת ב - אם כן, הLCS בהכרח מהצורה , כאשר היא הLCS של ו.
  3. אינה מסתיימת ב, וכן אינה מסתיימת ב - אם זה המצב, אז הLCS של ו הוא הLCS של ו (וכן גם הLCS של ו), כך ששתי הבדיקות הקודמות מכסות כבר (פעמיים אפילו) מקרה זה.


מש"ל.PNG

מציאת אורך ה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, מטפלות במצב בו הפונקציה נקראת עם פרמטרים שאתם היא כבר נקראה בעבר.

ניתוח סיבוכיות[עריכה]

נגדיר את כזמן שאורכת LCS-Length בהנחה שכל אחת מקריאותיה הרקורסיביות היא . קל לראות ש.

זמן הריצה של LCS-Length(m, n) חסום מלמעלה על ידי . חוץ מכך ישנו האתחול 1-4 שאורך גם כן . הזמן הכולל, לכן, הוא .

הדפסת איברי ה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 מתארת בכניסה ה את ההחלטה לגבי הLCS של ו:

  1. 'x' מסמלת את ההחלטה לוותר על התו האחרון ב.
  2. 'y' מסמלת את ההחלטה לוותר על התו האחרון ב.
  3. 'b' מסמלת את ההחלטה לוותר על התו האחרון בשניהם. זה בדיוק המצב בו נמצא כחלק מה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])

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