Question

winter_15-16_a
dynamic_programming

נתון נהר ולו שני צדדים - צפון ודרום. בכל אחד מהצדדים יש nn בניינים, A1,,AnA_1, \ldots, A_n ו-B1,,BnB_1, \ldots, B_n בהתאמה. בצפון הבניינים מסודרים לפי הסדר (משמאל לימין): A1,,AnA_1, \ldots, A_n ובדרום הבניינים מסודרים לפי פרמוטציה כלשהי של B1,,BnB_1, \ldots, B_n. המטרה היא לבנות גשרים בין שני הצדדים. מותר לבנות גשר אך ורק בין בניינים AiA_i ו-BiB_i לכל 1in1 \leq i \leq n. כמו כן, אסור שהגשרים יחצו זה את זה.

לדוגמה, אם במקרה הבא, נבחר לבנות גשר בין B2B_2 ל-A2A_2 אזי לא נוכל לבנות גשר בין A1A_1 ל-B1B_1, אך כן נוכל לבנות גשר בין A5A_5 ל-B5B_5.

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

1

Answers

נראה רדוקציה למסלול כבד ביותר בגרף מכוון חסר מעגלים. נסמן ב-bi=(Ai,Bi)b_i = (A_i, B_i) את הגשר ה-ii, ונסמן bibjb_i \| b_j אם גשר bib_i לא חוצה את גשר bjb_j.נגדיר את הגרף הבא:

D=({b1,,bn},E)D = (\{b_1, \ldots, b_n\}, E)

כאשר

E={(bi,bj):i<jbibj}E = \{(b_i, b_j) : i < j \land b_i \| b_j \}

אבחנה: אם עבור i<j<ki < j < k מתקייםbibjb_i \| b_j וגם bjbkb_j \| b_k אז bibkb_i \| b_k.

מהאבחנה הנ"ל נובע ש-bi1bilb_{i_1} \ldots b_{i_l} פתרון חוקי אמ"מ bi1bilb_{i_1} \ldots b_{i_l} מסלול ב-DD.

אלגוריתם:

  • בנה את הגרף DD
  • מצא ב-DD מסלול ארוך ביותר ביותר
  • החזר את קבוצת הגשרים המתאימה

נכונות: נובעת מיידית מהטענות לעיל.

סיבוכיות: נשים לב שהגרף הוא בגודל O(n2)O(n^2). מציאת מסלול ארוך ביותר בגרף מכוון חסר מעגלים אפשר לעשות בזמן לינארי ולכן סך כל הסיבוכיות היא O(n2)O(n^2).

0
Feedback