אלגוריתם הפרד ומשול

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

מימוש
פרדיגמה אלגוריתמית זו מבוססת על פירוק בעיה מורכבת ליחידות קטנות וניהולן באופן הדרגתי:

 חלוקה (הפרד): פירוק הבעיה המקורית למספר תת-בעיות קטנות יותר, הדומות במבנן לבעיה המקורית.
 פתרון (משול): פתרון תת-בעיות אלו באופן רקורסיבי. כאשר תת-בעיה מגיעה לגודל מינימלי (מקרה בסיס), היא נפתרת באופן ישיר ופשוט.
 מיזוג: חיבור וסנכרון הפתרונות של תת-הבעיות לכדי פתרון קוהרנטי ומלא עבור הבעיה הכוללת.

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

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

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

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

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

אלגוריתמים המשתמשים בשיטת הפרד ומשול
חיפוש בינארי
מיון מהיר
מיון מיזוג
התמרת פורייה המהירה
אלגוריתם הפרד ומשול למציאת קמור

ראו גם
 אינדוקציה מתמטית
 שיטת האב

קישורים חיצוניים

קטגוריה:אופטימיזציה בדידה
הפרד ומשול