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