tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
בנוסף, תחום הביואינפורמטיקה (כגון סיווג גנים או חיזוי מבנה חלבונים) אימץ גם הוא אלגוריתמים מבוססי בוסטינג, כאשר ישנם אינספור מאפיינים ביולוגיים חלשים שיש לשקלל יחדיו.
AdaBoost שייך למשפחת אלגוריתמי ה-Boosting, שבהם המסווגים הבסיסיים מאומנים באופן סדרתי (טורי) תוך שימוש בתוצאות קודמיהם.
זאת בניגוד למשפחת ה-Bagging (כגון יער אקראי), שבה מודלים מרובים מאומנים במקביל על דגימות אקראיות של הנתונים.
בשתי הגישות משלבים מספר מודלים חלשים לכדי מודל חזק, אך האופן שבו הדבר מתבצע שונה: AdaBoost משנה באופן אדפטיבי את משקלי הדוגמאות כדי להתמקד במקרים קשים בכל סבב, בעוד שביער אקראי כל עץ מקבל משקל שווה, והעצים שונים זה מזה בשל דגימת נתונים ומאפיינים שונה בכל עץ.
יער אקראי מסתמך על הפחתת שונות (variance) על ידי ממוצע של מודלים לא תלויים יחסית, בעוד Boosting מכוון להפחתת הטיה (bias) באופן סדרתי – כל מודל מתקן את קודמו.
כתוצאה מכך, AdaBoost נוטה להתאים את עצמו חזק לנתוני האימון ועלול להיות רגיש יותר לרעש, בעוד שיער אקראי עקב אופיו הממוצע יותר חסין לרעש ולחריגות.
מצד שני, AdaBoost לעיתים קרובות מגיע לדיוק גבוה יותר על האימון ויכול להתמקד גם במקרים חריגים, בעוד שיער אקראי עשוי "לדלל" את השפעתם של מקרים נדירים.
עוד הבדל פרקטי הוא שיער אקראי יכול לנצל עיבוד מקבילי (מאחר שכל עץ נבנה באופן עצמאי) ובדרך כלל דורש פחות כוונון של היפר-פרמטרים, בעוד AdaBoost הוא תהליך טורי שקשה יותר להאיץ בחומרה מקבילית.
בסופו של דבר, שתי השיטות פופולריות ומשלימות זו את זו: יערות אקראיים טובים ביציבות ובמניעת הישררות יתר (overfitting), ואילו Boosting (לרבות AdaBoost) מצטיין בהגעה לביצועי שיא כאשר הנתונים נקיים מרעש או לאחר טיוב זהיר.
AdaBoost מול אלגוריתמי Boosting מודרניים
AdaBoost היה אחת הגרסאות הראשונות והבסיסיות של Boosting.
אחריו פותחו וריאנטים ושיפורים רבים.
חיזוק גרדיאנט היא מסגרת כללית שבה boosting מוגדר כבעיה של אופטימיזציה נומרית: במקום לעדכן משקלי דגימות באופן אקספוננציאלי כל מודל חדש מותאם לטעויות (residuals) שהמודל המשולב הנוכחי עדיין עושה, תוך שימוש במתודולוגיית Gradient descent על פונקציית עלות כללית.
יתרון הגישה הזו הוא שניתן לבחור פונקציית loss שונה (למשל לוגיסטית, ריבועית וכו'), מה שנותן גמישות רבה – למשל, חיזוק גרדיאנט מיושם לא רק לסיווג בינארי אלא גם לרגרסיה, לסיווג רב-מחלקות ועוד.
הוא מאפשר שימוש בלומדים חלשים מעט יותר מורכבים (כמו עצים בעלי עומק של 4–8 רמות במקום "עצים טיפשים" בני רמה אחת הנפוצים ב-AdaBoost), והוא כולל מנגנונים להפחתת הישררות יתר כמו רגולריזציה (חיזוק מדורג, קיצוץ ערכי עלים, ועוד).
AdaBoost משתייך לשיטות האנסמבל, ולכן שונה בגישתו ממסווגים "בודדים" כמו עצי החלטה עמוקים, מכונת וקטורים תומכים (SVM) או רשתות עצביות.
בהשוואה לעץ החלטה גדול, AdaBoost לרוב יבנה מספר רב של עצים קטנים (או מסווגים פשוטים אחרים), ולכן עשוי ללכוד דפוסים באופן שונה – לעיתים מדויק יותר עבור פרטים אך אולי פחות "גלובלי" מאשר עץ עמוק אחד.
בהשוואה לרשת עצבית, AdaBoost אינו דורש הגדרת שכבות והיפר-פרמטרים רבים, אך רשתות יכולות לנצל טוב יותר כמויות נתונים גדולות במיוחד וללמוד ייצוגים מורכבים, בעוד AdaBoost מסתמך על מאפיינים קיימים ולומד רק משקלים על גביהם.
אחד היתרונות של AdaBoost על פני מודלים כמו SVM הוא בפשטות העדכון – אין צורך בפתרון בעיה קמורה גלובלית מורכבת, אלא רק בחישובים סגורים בכל סבב – וכן בכך שקל לשלב אותו עם אלגוריתמים קיימים (למשל, לקחת סיווגים חלשים קיימים ולשפרם דרך Boosting).
מצד שני, בבעיות עם מרחב מאפיינים עצום או רציף מאוד, מודלים כמו SVM עם גרעין או רשתות עמוקות עשויים לתפוס מבנים לא-ליניאריים באופן יעיל יותר מאשר צירוף של רבים מאוד של חלוקים ליניאריים.
אלגוריה על האמת והזמן (באיטלקית: Allegoria della Verità e del Tempo) היא יצירת שמן על קנבס מאת הצייר האיטלקי אניבלה קראצ'י, שנוצרה בין השנים 1584–1585. הציור נמצא כיום באוסף המלכותי הבריטי ונחשב לדוגמה בולטת לאמנות האלגורית של סוף תקופת הרנסאנס.
היצירה משקפת את המעבר מהשפעות הציור הצפון-איטלקי לסגנון ריאליסטי ונועז יותר שפיתח קראצ'י בעבודותיו המוקדמות.
במרכז הקומפוזיציה מופיע הזמן, כדמות מכונפת המחזיקה שעון חול, כשהוא שולף את בתו – האמת – מתוך באר, ומביא אותה אל אור היום.
האמת מקרינה אור, עוטה הילה של קרני שמש, ומתבוננת בעצמה במראה – אשר מציגה "תמונה אמיתית של העולם".
דמותה רומסת תחת רגליה את הרמייה, דמות דו-פרצופית המתוארת לפעמים גם כתרמית (Fraud), צביעות (Hypocrisy) או השמצה (Calumny).
בשיקום האחרון של היצירה נחשפו תווי חיה מרושעים בגב ראשה של הדמות – הדגשה ציורית לכך שהיא ממש דו-פרצופית.
את הסצנה המרכזית מקיפות שתי דמויות סמליות: מימין, Bonus Eventus – הסיום הטוב, המחזיק פרחים, דגנים ופרג.
משמאל, דמות המזוהה או עם האושר (Felicità), בעלת קרן שפע וקדוקוס עם כנפיים, או לחלופין עם המזל הטוב (Buona Fortuna), המיוצגת באופן דומה.
הרעיון המרכזי ביצירה מתמצה בשני פתגמים: "האמת תתגלה" ו"הכול טוב שמסתיים בטוב".
על אף שאין מקור ספרותי ידוע שעליו התבססה הקומפוזיציה, סביר להניח שקראצ'י הושפע ממקורות מיתולוגיים כגון ספרו של וינצ'נצו קרטארי, Le Imagini, אשר כלל דימויים ואיורים מהעולם הקלאסי, ונשען על מקורות עתיקים כמו פליניוס.
הבחירה במראה כאובייקט אלגורי המוחזק בידי האמת משקפת את הרעיון לפיו המראה משקפת את המציאות האמיתית — ולפיכך האמת מתבוננת בעצמה, בלא עיוות.
העובדה שהאמת "מועלית מן הבאר" בידי הזמן מייצגת תמה קלאסית, לפיה האמת חבויה או נרדפת עד שהזמן חושף אותה.
הכנפיים של הזמן נועדו לסמן את ביטוי הזמן החולף במהירות — רעיון מוכר מהמסורת האיקונוגרפית האירופית.
ניתוח טכני של היצירה מראה כי חלקים נרחבים ממנה עוצבו תוך כדי תהליך העבודה.
ניתן להבחין בשינויים (Pentimenti) שבוצעו: ענפי עצים שנמחקו והוחלפו בשמיים, תנועות ידיים ורגליים של הדמויות שונו – כולל יד ימין של האמת, יד שמאל של דמות המזל, שתי הידיים של דמות הרמייה והגפיים של Bonus Eventus.
שינויים אלה מעידים על תהליך דינמי שבו האלגוריה לא הייתה מתוכננת בשלמותה מראש, אלא התגבשה במהלך הציור.
רישום שנמצא כיום במוזיאון פוג, מציג קומפוזיציה מיתולוגית של "משפט פריס".
אף שציור המבוסס על רישום זה לא שרד, קיים דמיון בולט במבנה, פורמט ועיצוב לדמויות ב-אלגוריה על האמת והזמן.
ייתכן כי קראצ'י תכנן לצייר זוג עבודות על נושאים משלימים: שיפוט נכון לעומת שיפוט שגוי, והשלכותיהם המוסריות.
מבנה היצירה ומורכבותה האלגורית מצביעים על השפעת ציורו של טיציאן אהבה קדושה ופרופאנית.
הדמויות, הנוף והארכיטקטורה שואבים מסגנון הרנסאנס הצפון-איטלקי, אך סימני ההשפעה של אנטוניו דה קורג'ו ופדריקו בארוצ'י בולטים אף הם — במיוחד בידיים הארוכות והמעוגלות, ובשימוש בגוונים מעט חומציים.
קראצ'י מעבד את ההשפעות הקודמות לכדי סגנון עצמאי, אשר משלב אינטלקטואליות אלגורית עם ריאליזם גופני וחומרי.
הנטורליזם שבלט לבני זמנו ניכר במיוחד בתיאור דמותה של האמת באור שמש חד, ובעיצוב של דמויות בסביבה חיצונית טבעית.
סגנון זה מופיע גם ביצירתו הטבילה של ישו (1585), והוא מבשר את פיתוח הסגנון הדרמטי והצבעוני של קראצ'י בשנים המאוחרות, כגון ביצירות שביצע בארמון פארנזה.
מעמדה של היצירה בהתפתחותו האמנותית של קראצ'י
היצירה מהווה נקודת מפנה ביצירתו של קראצ'י, בה הוא שוזר בין רעיונות מוסריים עמוקים לביצוע ציורי בוטח, מדויק ורב־משמעות.
השילוב בין דמויות סמליות, קונטרסט של אור וצל, ועיצוב חלל מורכב מעידים על שליטה צורנית ורעיונית, אשר תתגבש בהמשך ביצירותיו הבשלות ברומא.
האזכור הוודאי הראשון של היצירה מופיע ברשומות המלכותיות משנת 1876, אז תועדה על ידי ריצ'רד רדגרייב בארמון בקינגהאם.
קיימת סברה שהציור הוא אותו יצירה שתוארה כבר בשנת 1710 תחת השם Virtue correcting of Vice באחסון בארמון המפטון קורט, ובשנת 1714 בסומרסט האוס.
עם זאת, העדר תיעוד רציף מקשה על אימות חד־משמעי של זהות הציור לאורך התקופה.
אלגוריית האמונה, הידועה גם כאלגוריית האמונה הקתולית, היא ציור הולנדי מתור הזהב מאת יאן ורמיר משנת 1670–1672 בקירוב.
הוא נמצא במוזיאון המטרופוליטן לאמנות בניו יורק מאז 1931.
"אלגוריה של האמונה הקתולית" היא אחת משתי יצירותיו של ורמיר המסווגות כ"ציור היסטורי" לפי ההיררכיה המקובלת של הז'אנרים באמנות התקופה – השנייה היא "אמנות הציור".
אף על פי שהן משתייכות לז'אנר שונה, שתי היצירות שומרות על מאפיינים טיפוסיים לורמיר: קומפוזיציה הכוללת דמות אחת או שתיים במרחב פנים ביתי.
לשתי היצירות מבנה פרספקטיבי דומה, שטיח צבעוני בצד שמאל הנמשך הצידה וחושף את הסצנה, ושימוש באלמנטים מתוך "האיקונולוגיה" של צ'זארה ריפה.
ביצירה מכתב האהבה נראה גם כן פאנל מוזהב דומה.
עם זאת, "האלגוריה" ו"אמנות הציור" שונות באופן מובהק בסגנונן ובמטרתן משאר יצירותיו של ורמיר.
במרכז הציור נראית אישה הלבושה בגלימה כחולה מעל שמלת סאטן לבנה עם עיטורי זהב.
היא עומדת בתנוחה תיאטרלית על במה מוגבהת, כשרגלה הימנית מונחת על גלובוס – סמל לניצחון האמונה על העולם.
ידה הימנית מונחת על לוח לבה, ומבטה מופנה כלפי מעלה.
מן התקרה משתלשל כדור זכוכית שקוף התלוי במיתרים כחולים – סמל לרוח הקודש או לעולם השמימי.
לפניה מוצב שולחן מכוסה שטיח ירקרק שעליו מונחים גביע, ספר תפילה פתוח, צלב כהה מבהיק, וכן כתר קוצים – סמל ברור לסבלו של ישו בטרם צליבתו.
על הרצפה נראים תפוח מרוסק – כרמז לחטא הקדמון – ונחש שראשו נמחץ תחת אבן יסוד לבנה, המייצגת את ישו עצמו.
מאחורי הדמות, על הקיר, תלוי לוח עור מוזהב שמדמה וילון כבד – מרכיב מוכר בעיצוב כנסיות בית.
לצדו תלויה גרסה מצוירת של סצנת הצליבה מאת יקוב יורדאנס, שבה נראית רק דמותו של ישו, מבודדת משאר הדמויות ביצירה המקורית.
על פי פרשנות אחת, הדמות הראשית בציור אינה אלגוריה מופשטת בלבד, אלא מתארת את מריה מגדלנה המתחרטת.
דמות זו מייצגת הן את הקרבה האישית לישו והן את זהות הכנסייה הקתולית, ומשלבת בין מסר אישי של חרטה ואמונה לבין תיאור אוניברסלי של עקרונות דתיים.
הנחש המרוסק מסמל את השטן, ואבן היסוד שרומסת אותו מייצגת את ישו.
התפוח המרוסק רומז לחטא הקדמון.
ריפה הדגיש כי האמונה היא החשובה שבמידות, ורמיר הדגיש זאת בקומפוזיציה שבה מרוכזת תשומת הלב בדמותה האלגורית הבודדת.
הגלובוס שבציור זוהה על ידי החוקר ארתור ק.
וילוק ג'וניור כדגם שהודפס על ידי הקרטוגרף הנדריק הונדאוס.
השפעות ישועיות וסטיות מהאיקונוגרפיה של ריפה
על אף שהיצירה שואבת השראה מספר הסמלים של צ'זארה ריפה, ורמיר שינה חלק מהאיקונוגרפיה המתוארת בו.
במקום להניח את הגביע ביד הדמות ואת ידה השנייה על ספר פתוח, כפי שריפה הציע, הציב ורמיר את הגביע, הספר והצלב זה לצד זה על שולחן – קומפוזיציה המעניקה לדימוי אופי המזוהה עם טקס האכואוריסטיה, על פי פרשנותו של ארתור ק.
הצבת הגביע הזהוב על רקע כהה, והצלב השחור מול פאנל מוזהב, מדגישה את מרכזיותם.
לדברי קוונט גרגורי, חפיפת הזהב של הגביע והרקע הזהוב של הצלב מרמזת על גישור בין התחום הפיזי לרוחני – רעיון קתולי מובהק.
יש הרואים גם השפעה ישועית נרחבת בציור, בעיקר בשימוש בצליבה (במקום עקדת יצחק שהוזכרה אצל ריפה), ובשילוב של כדור הזכוכית, אשר לפי החוקר אדי דה־יונג שאוב מספר סמלים ישועי משנת 1636 מאת וילם הזיוס.
באיור זה מוצג ילד מכונף אוחז בכדור המחזיר אור, כסמל לנפש האדם היכולה לשקף את האלוהות.
ורמיר נולד למשפחה מזוהה עם הקלוויניזם, אך בשנת 1653 עבר לקתולית, ככל הנראה כתנאי לנישואיו.
ציור זה, שנחשב לאחת משתי היצירות האלגוריות היחידות שלו, שונה מהותית ביצירתו ומרמז על התנסות דתית אישית.
הסמלים הברורים – הגביע, התפוח המרוסק, הנחש הרמוס, אבן היסוד, הצלוב וכתר הקוצים – מבטאים את עקרונות הקונטרה-רפורמציה ואת הדגש הקתולי על גאולה, חטא וכפרה.
הקומפוזיציה הביתית עשויה לשקף את מנהגן של קהילות קתוליות ברפובליקה ההולנדית לערוך מיסות סודיות ב"כנסיות נסתרות".
במדעי המחשב, אלגוריתם חמדן הוא אלגוריתם המתבסס על היוריסטיקה שלפיה בוחרים את האפשרות הטובה ביותר הנראית לעין בשלב הנוכחי, מבלי לקחת בחשבון את ההשפעה של צעד זה על המשך הפתרון.
אלגוריתמים חמדנים נפוצים בפתרון בעיות מיטוב, שבהן מנסים למצוא את הפתרון הטוב ביותר.
לעיתים כאשר לא ניתן למצוא את הפתרון האופטימלי בזמן סביר, שימוש באלגוריתם חמדן עשוי לתת קירוב טוב לפתרון המיטבי בזמן קצר.
בהתחשב בעובדה שבעיות אופטימיזציה רבות הן NP-קשות, שימוש באלגוריתמים חמדניים יכול להיות יעיל במיוחד.
במקרים מסוימים האלגוריתם החמדן הוא גם האלגוריתם האופטימלי.
כלומר, סדרת בחירות חמדניות נותנת לפעמים את הפתרון האופטימלי הכללי לבעיה.
למשל, האלגוריתם של פרים למציאת עץ פורש מינימלי בגרף.
כדי להוכיח שאלגוריתם חמדן יוביל לפתרון אופטימלי ניתן להשתמש בתורת המטרואידים.
לא כל בעיה שאפשר לפתור בגישה חמדנית היא בהכרח מטרואיד (לדוגמה, בעיית התרמיל השלם).
ניתן להשתמש גם בהוכחה בדרך השלילה או בלמת החלפה, אך שיטות הוכחה אלו נוטות להיות פחות אלגנטיות.
בעיית הסוכן הנוסע: סוכן מכירות רוצה לעבור במספר יישובים כדי למכור את הסחורה שלו.
המטרה היא למצוא את המסלול הקצר ביותר שיעבור דרך כל היישובים.
על פי שיטת האלגוריתם החמדן, הסוכן הנוסע צריך להסתכל בכל פעם במפה ולנסוע ליישוב הקרוב ביותר שבו לא ביקר עדיין.
במקרה זה שיטת האלגוריתם החמדן לא תיתן בהכרח את הפתרון הטוב ביותר.
כפי שניתן לראות באיור, יכול להיות מצב שבו הסוכן ידלג על יישוב מסוים משום שישנו יישוב אחר קרוב יותר, כך שייאלץ לחזור ליישוב שעליו דילג בסוף המסלול ולעשות דרך ארוכה יותר.
בעיית בחירת פעילויות: יש לבחור פעילויות מתוך רשימה כך שלוח הזמנים יתמלא בכמה שיותר זמן פעילות.
האלגוריתם יבחר בכל פעם את הפעילות שזמן הסיום שלה הכי מוקדם ויחפש את הפעילות הבאה שזמן הסיום שלה הכי מוקדם, מתוך אלה שמתחילות אחרי הפעילות שכבר נבחרה.
בדוגמה זו, ניתן להראות כי עבור סדרת הערכים הנתונה וסדרות דומות לה, האלגוריתם החמדן הוא גם האלגוריתם האופטימלי, אך עבור סדרות ערכים אחרות אין זה כך.
קוד הופמן: בקידוד לשפה בינארית, יש לבחור בכל פעם את התו בעל השכיחות הגבוהה ביותר ולהגדיר לו את הייצוג המתאים כך שייצוג של תו לא יכיל בטעות תת-תווים בתוכו.
אלגוריתם ID3: אלגוריתם חמדן שמייצר עץ החלטה מקבוצת דוגמאות נתונה.
אלגוריתם אקראי או אלגוריתם הסתברותי הוא אלגוריתם המשתמש באקראיות במהלך ריצתו, או במילים אחרות, רשאי "להטיל מטבעות אקראיים" כחלק מפעולתו.
באופן פורמלי, מוגדר אלגוריתם אקראי בעזרת מכונת טיורינג הסתברותית: מכונת טיורינג רגילה אשר בנוסף לסרטים הרגילים שלה יש לה גישה לסרט קלט נוסף אשר מכיל רצף של "0"-ים ו-"1"-ים, המייצגים סדרה של הטלות אקראיות בלתי תלויות של מטבעות.
ניתן להגדיר פלט של מכונת טיורינג כנ"ל כהתפלגות על פלטי המכונה בהינתן התפלגות אחידה בדידה בלתי תלויה של איברי סדרת הסרט הנוסף.
פורמלית, זמן הריצה של אלגוריתם אקראי הוא משתנה מקרי, ולעיתים נמדדת יעילות האלגוריתם על פי תוחלת זמן הריצה שלו.
מקובל לחלק אלגוריתמים אקראיים לשתי משפחות עיקריות:
אלגוריתמי לאס וגאס הם אלגוריתמים אשר תמיד מוצאים תשובה נכונה לבעיה, ומשתמשים באקראיות רק על מנת לנסות ולשפר את זמן הריצה.
דוגמה ידועה לאלגוריתם ממין זה הוא אלגוריתם המיון מיון מהיר .
אלגוריתמי מונטה קרלו הם אלגוריתמים אשר עלולים להחזיר תשובה לא נכונה לבעיה.
דוגמה ידועה לאלגוריתם ממין זה הוא אלגוריתם מילר-רבין לבדיקת ראשוניות של מספר.
כאשר קלט נתון הוא מספר ראשוני, האלגוריתם תמיד יזהה אותו נכונה ככזה, אך האלגוריתם עלול גם לזהות מספר פריק כמספר ראשוני בהסתברות מסוימת.
על ידי חזרה על האלגוריתם מספר רב של פעמים, ניתן להקטין את הסתברות השגיאה למספר קטן כרצוננו, אך לא להבטיח תשובה נכונה בוודאות מלאה.
אלגוריתם זה, שנוצר בשנת 1976, הוא ראשיתו של תחום האלגוריתמים האקראיים.
במדעי המחשב מוגדרות מחלקות סיבוכיות המתאימות לבעיות אשר יש עבורן אלגוריתם אקראי יעיל:
מחלקת הסיבוכיות ZPP מתארת את מכלול הבעיות אשר ניתן לפתור באמצעות אלגוריתם אקראי יעיל שאינו טועה (דהיינו, אלגוריתמי לאס וגאס).
מחלקת הסיבוכיות RP מייצגת בעיות אשר יש עבורן אלגוריתם יעיל אקראי שעונה תמיד נכון על קלטים שהתשובה הנכונה עבורם היא "לא", אך עלול לטעות עבור קלטים שהתשובה הנכונה עבורם היא "כן".
המחלקה Co-RP מייצגת בעיות אשר יש עבורן אלגוריתם יעיל אקראי שעונה תמיד נכון על קלטים שהתשובה הנכונה עבורם היא "כן", אך עלול לטעות עבור קלטים שהתשובה הנכונה עבורם היא "לא".
(במחלקה זו נמצאת למשל בעיית הראשוניות).
מחלקת הסיבוכיות BPP מייצגת בעיות אשר יש עבורן אלגוריתם יעיל אקראי שעלול לטעות הן עבור קלטים שהתשובה הנכונה עבורם היא "כן" והן עבור קלטים שהתשובה הנכונה עבורם היא "לא".
עם זאת, נדרש שהטעות תהיה כזו שמאפשרת הקטנה שלה על ידי הפעלות חוזרות ונשנות של האלגוריתם.
לרוב מגדירים את המחלקה עם דרישת שגיאה של לכל היותר 1/3, אולם לכל בעיה במחלקה ניתן למצוא אלגוריתם יעיל אקראי שהשגיאה שלו קטנה באופן שרירותי.
בשל כך, PP היא מחלקה רחבה יותר מאשר BPP, אך לעומת זאת אם בעיה שייכת ל-PP זה אינו מבטיח שניתן יהיה למצוא לה אלגוריתם יעיל אקראי בעל הסתברות שגיאה קטנה באופן שרירותי.
אלגוריתמים אקראיים משמשים בבסיסן של הגדרות מחלקות סיבוכיות נוספות רבות, ובפרט במערכות הוכחה אינטראקטיביות.
אחת השאלות המרכזיות הפתוחות במדעי המחשב היא האם אקראיות עשויה לסייע לחישוב יעיל.
במילים אחרות, האם קיימת בעיה שנמצאת ב-BPP (דהיינו: קיים עבורה אלגוריתם אקראי עם זמן ריצה פולינומי) אך שאינה נמצאת ב-P (דהיינו: אשר לא קיים עבורה אלגוריתם דטרמיניסטי עם זמן ריצה פולינומי).
השאלה האם קיימת אקראיות אמיתית בטבע היא שאלה פילוסופית עתיקת יומין, ואף עמדה בבסיסן של אחת המחלוקות הגדולות בפיזיקה המודרנית.
עם זאת, ישנן מדידות פיזיקליות רבות אשר מהוות – לכל תכלית פרקטית – מספר אקראי; למשל – זוגיות מספר אלפיות השנייה שנדרש לאדם נתון להקיש על מקש במקלדת.
עם זאת, אלגוריתמי מחשב פרקטיים אינם משתמשים על פי רוב במדידות פיזיקליות, אלא במחולל מספרים פסאודו-אקראיים – אלגוריתמים לייצור סדרת מספרים אשר (באופן בלתי פורמלי) "נראים" כמו סדרה של מספרים אקראיים.
האלגוריתמים המוכרים ביותר הם ככל הנראה אלגוריתם המיון מיון מהיר (Quicksort) - אלגוריתם המיון המהיר ביותר בשימושים פרקטיים, על אף שזמן הריצה שלו במקרה הגרוע ביותר גדול יחסית - והאלגוריתם לבדיקת ראשוניות שאוזכר אף הוא לעיל.
לאקראיות ולאלגוריתמים אקראיים שימושים רבים, ובהם:
חישוב נומרי (שיטת מונטה קרלו)
אלגוריתם דטרמיניסטי במדעי המחשב הוא אלגוריתם המתנהג בצורה צפויה וניתנת לחיזוי.
כלומר, בהינתן קלט מסוים, המכונה עליה רץ האלגוריתם תבצע את אותם צעדים והפלט הסופי יהיה אותו פלט.
אלגוריתמים דטרמיניסטים משמשים בתחומים רבים ולאו דווקא במדעי המחשב.
דוגמה לאלגוריתם דטרמינסטי היא החילוק הארוך.
המושג "אלגוריתם דטרמיניסטי" הוא מונח חדש יחסית, והוא מתאר את מה שבמשך מאות שנים כונה פשוט "אלגוריתם".
הצורך במינוח זה נוצר בסביבות שנת 1976, עם תחילת חקירתם של אלגוריתמים אקראיים, מאחר שהיה צורך להבדיל בינם ובין אלגוריתמים שאינם אקראיים.
בכל זאת, ברוב המקרים בהם קיימת התייחסות לאלגוריתם כיום, הכוונה היא לאלגוריתם דטרמיניסטי.
כל המחשבים המודרניים הם מחשבים דטרמיניסטיים, כלומר ניתן להריץ עליהם רק תוכנות המהוות ייצוג של אלגוריתמים דטרמיניסטיים.
באופן פורמלי אלגוריתם דטרמינסטי יכול להיות מוגדר במונחי מכונת מצבים: מצב מתאר מה תעשה מכונה בזמן מסוים.
מכונת המצבים עוברת בין המצבים.
מיד לאחר מתן הקלט המכונה נמצאת במצב ההתחלתי שלה (הידוע גם כמצב התחלה).
במכונה דטרמיניסטית המצב הנוכחי והקלט קובעים מה יהיה המצב הבא אליו תעבור המכונה (כלומר סדר הפעולות בו תעבור המכונה קבוע מראש).
הטמעת אקראיות בתוך אלגוריתמים דטרמיניסטיים
מכיוון שתוכנות מחשב מבצעות אלגוריתמים דטרמיניסטיים, לא ניתן לחולל מספרים אקראיים באמצעות תוכנת מחשב.
קיימים יישומים בהם רוצים להשתמש באלגוריתם דטרמיניסטי, אך לא רוצים שהמצבים הבאים יהיו צפויים.
משחקי קלפים למשל הם דוגמה ליישום בו לא רוצים לתת את האפשרות לחזות את הקלפים הבאים בחפיסה.
לצורך כך, המחשב מייצר מספרים פסאודו-אקראיים המתקבלים באמצעות הפעלת פונקציה דטרמיניסטית על מספר התחלתי אקראי המכונה Seed.
מספרים אלה נחשבים אקראיים לכל שימוש מעשי אך הם למעשה סדרה דטרמיניסטית.
כדי להבטיח קבלת סדרה פסאודו-אקראית שונה בכל הרצה של התוכנית, על ה-Seed שבו היא משתמשת להגיע ממקור חיצוני לה שישתנה בין הרצות שונות - לרוב משתמשים בשעון של המחשב, או במידע על נתון "אקראי" כדוגמת הזזות העכבר של המשתמש.
בנוסף לכך למחשב יכולה להיות גישה למספרים אקראיים "אמיתיים" על ידי חיבור להתקן מדידה פיזיקלי המודד תהליך אקראי (כמו התפרקות רדיואקטיבית).
מכיוון שהאקראיות שבה המחשב משתמש אינה אקראיות "אמיתית" אלא ניפוח דטרמיניסטי של Seed שעשוי להגיע ממקור בעל חוקיות מסוימת (בפרט, שעון המחשב), לא ניתן למנוע באופן מוחלט מפעולת המחשב מלהיות צפויה עבור מי שמנסה לנתחה.
מכונה יכולה להיות דטרמיניסטית ועדיין לא לעצור לעולם.
התנאי היחיד להיותה של המכונה דטרמיניסטית היא שנוכל לדעת בכל שלב היכן תהיה המכונה.
אף על פי שכל בעיה אלגוריתמית פתירה, ניתנת לפתרון באמצעות אלגוריתם דטרמינסטי, בעבור חלק גדול מהבעיות האלגוריתמים הדטרמניסטיים הידועים איטיים יותר (במונחי סיבוכיות) ממשפחות אלגוריתמיות אחרות.
בתורת הסיבוכיות המחלקה המכילה את הבעיות שקיים אלגוריתם דטרמיניסטי הרץ בזמן סביר (פורמלית, זמן הריצה שלו הוא פולינום של גודל הקלט) מכונה P.
קיימות מגוון של בעיות שימושיות (בעיות תכנון מסלולים וזמנים, בעיות מספריות, בעיות מתורת הגרפים וכו') אשר לא ידועה דרך לפתור אותן בזמן סביר.
במידה וימצאו אלגוריתמים דטרמינסטיים לבעיות אלה ניתן יהיה לשפר יישומים מעשיים רבים (גרפיקה במשחקי מחשב, תכנון מסלול באמצעות תוכנת GPS).
אלגוריתם דייקסטרה הוא אלגוריתם למציאת המסלול האופטמיאלי ביותר מקודקוד מקור לקודקוד יעד בגרף ממושקל בעל משקלים חיוביים, או למציאת כל המסלולים האופטמיאלים ביותר מקודקוד מקור לשאר הקודקודים (בעיית המסלולים האופטימלים ממקור יחיד).
לעיתים מחליפים את המונח "מסלול אופטימאלי" ב"מסלול קצר" או "מסלול קל".
המסלול האופטמיאלי ביותר בין שתי נקודות מוגדר כמסלול שסכום משקלי הקשתות במסלול הוא הנמוך (או הגבוה) ביותר מבין כל המסלולים האפשריים.
האלגוריתם עובד על גרף מכוון או לא מכוון, שבו לכל קשת משויך משקל אי-שלילי.
בגרף המייצג רשת כבישים, המסלול האופטמיאלי הוא הדרך המהירה ביותר להגיע ממקום למקום.
ברשתות תקשורת, אלגוריתם דייקסטרה משמש בפרוטוקולי ניתוב למציאת מסלולי תקשורת אופטימליים (למשל Open Shortest Path First).
ניתן להמחיש את האלגוריתם בעזרת הקבלה לרשת תעלות.
אם משקל קשת מייצג אורך תעלה, ונניח שכל התעלות זהות וללא הבדלי גובה.
אז ניתן לדמיין שאלגוריתם דייקסטרה מזרים מים מהמקור, כך שהמים יתקדמו בקצב אחיד בתעלות.
כשמים מגיעים לקודקוד לראשונה, המסלול שהמים עשו מהמקור לקודקוד הוא המסלול האופטימלי.
האלגוריתם פועל על גרפים מכוונים או לא מכוונים, בעלי משקלים חיוביים.
האלגוריתם מקבל גרף וקודקוד מקור, ומוצא את המסלולים הקלים ביותר מהמקור לכל קודקוד אחר בגרף.
אלטרנטיבית, האלגוריתם יכול לקבל גם קודקוד יעד, ולמצוא את המסלול הקל ביותר מהמקור ליעד (לעיתים נקרא גם המסלול האופטימלי).
המסלול הקל ביותר לקודקוד u מוגדר כמסלול מהמקור ל-u, כך שסכום משקלי הקשתות לאורך המסלול הוא מינימלי מבין כל המסלולים.
סכום זה נקרא המרחק בין המקור ל-u.
בביטויי סיבוכיות, הביטויים E ו-V מתייחסים לגודל קבוצת הקודקודים והקשתות, ולא לקבוצות עצמן.
DistEst הוא מיפוי מקודקוד להערכת המרחק מהמקור.
Prev הוא מיפוי מקודקוד לקודקוד שקודם לו במסלול הקל ביותר שהתגלה עד כה.
הפסודו קוד מוצא את המסלול הקצר ביותר מהמקור לכל קודקוד בגרף.
אם המטרה היא למצוא רק את המסלול הקצר ביותר ממקור ליעד מסוים, ניתן לשנות את תנאי העצירה של הלולאה הראשית כך שיעצור לאחר שקודקוד היעד נשלף מ-Q.function Dijkstra(Graph, Source):
אלגוריתם דייקסטרה הוא מעין גרסה של חיפוש לרוחב שמתחשב במשקלי הקשתות.
במקום לשמור קודקודים לסריקה בתור (כמו בחיפוש לרוחב), דייקסטרה משתמש בתור קדימויות בו העדיפות נקבעת לפי הערכת מרחק מהמקור.
באתחול, כל הערכות המרחק מאותחלות כאינסוף, פרט להערכת המרחק למקור, שהיא 0 (המרחק מקודקוד לעצמו הוא 0).
בכל איטרציה, יישלף הקודקוד שהערכת מרחקו מינימלית.
בשלב זה המסלול הקל ביותר לקודקוד שנשלף הוא ידוע (נימוק מובא בהמשך).
לאחר מכן, ייבדקו שכניו של הקודקוד שנשלף, וייבדק האם ניתן לשפר את הערכת המרחק של השכנים: כלומר, מוסיפים למסלול הקל ביותר לקודקוד שנשלף את הקשת לשכן, ובודקים האם זה מניב מרחק שנמוך יותר מאומדן המרחק הנוכחי.
אם כן, הערכת המרחק לשכן תעודכן.
באיטרציה הראשונה יישלף קודקוד המקור (הערכת מרחקו היא מינמלית - 0, ושאר ההערכות הן אינסוף).
עבור הקודקודים שהם שכנים של המקור (כלומר יש צומת מהמקור אליהם), תחושב מחדש הערכת המרחק עבורם והעדיפות שלהם תעודכן.
באיטרציה השנייה, יישלף הקודקוד שמחובר למקור בקשת שמשקלה מינמלית (מבין הקשתות שיוצאות מהמקור).
המסלול העובר דרך קשת זו הוא המסלול הקל ביותר - כל מסלול אחר בהכרח עובר דרך קשת נוספת, שרק יכולה להכביד את המסלול (זכרו שכל המשקלים חיוביים).
בנוסף, עבור כל שכן של הקודקוד, ייבדק האם התגלה מסלול קל יותר לקודקוד השכן (מקור->u->שכן).
מצב זה יקרה אם השכן הוא קודקוד חדש שהחיפוש לא נתקל בו מקודם, או אם החיפוש כן נתקל בו מקודם אך המסלול שעובר ב-u הוא קל יותר.
וכך הלאה, בכל איטרציה, יישלף הקודקוד שהערכת מרחקו מינמלי, ובשלב זה ההערכה תהיה המסלול הקל ביותר האמיתי.
לאחר מכן, יעודכנו הערכות המרחק לקודקודים ששכנים של הקודקוד שנשלף.
מובטח שכשקודקוד נשלף מהתור, האלגוריתם אכן מצא את המסלול הקל ביותר אליו: אילו היה מסלול קל יותר, הקודקוד הלפני אחרון במסלול זה היה בעל הערכת מרחק נמוכה יותר, ולכן היה נשלף מהתור ראשון.
בגרף עם משקלים חיוביים, תת-מסלול לא יכול להיות קל יותר מהמסלול כולו (אינטואטיבית, הנסיעה מאילת לתל אביב דרך יטבתה לא יכולה להיות מהירה יותר מהנסיעה מאילת ליטבתה).
בסוף האלגוריתם, כל הקודקודים נשלפו מתור הקדימויות, ולכן המרחק לכולם ידוע.
כדי למצוא את המסלול עצמו ולא רק את המרחק, ניתן לשמור מיפוי מכל קודקוד לקודקוד שקודם לו במסלול הקל ביותר שהתגלה עד כה (המשתנה Prev בפסאודו קוד).
כך ניתן לשחזר את המסלול הקל ביותר - מתחילים מקודקוד היעד, בודקים מי קודם לו, וכך הלאה עד שמגיעים למקור.
דייקסטרה מגלה את המסלול הקל ביותר תחילה מהקודקודים הקרובים ביותר למקור, ולאחר מכן מקודקודים רחוקים יותר ויותר.
למשל, בדוגמת ההרצה הנ"ל תחילה מתגלה המסלול מקודקוד שמרחקו מהמקור הוא 7, לאחר מכן 9, וכו'.
בגרף גאומטרי (משקלים=מרחק גאומטרי), בדומה לדוגמת ההרצה שמופיעה בראש הערך, ניתן לדמיין שמשרטטים עיגול מסביב למקור, ומגדילים הדרגתית את רדיוס העיגול.
כשקודקוד נכנס לעיגול, דייקסטרה חישב את המסלול הקל ביותר אליו.
ניתן להיעזר באנלוגיה הפיזיקלית הבאה: מתחילים להזרים מים לרשת תעלות (נניח שכל התעלות בעלות קיבולת זהה, ואין הבדלי גבהים).
המים יבקרו בקודקודים באותו סדר שדייקסטרה מבקר בהם, וימצאו אותם מסלולים קצרים.
זוהי מעין גרסה "ממושקלת" של חיפוש לרוחב (ראה פירוט בהמשך הערך).
האלגוריתם מוצא עץ מסלולים מזעריים .
זהו תת-גרף שהוא עץ שמושרש בקודקוד המקור, וכל מסלול מהשורש לכל קודקוד אחר הוא מסלול קל ביותר בגרף המקורי.
אם הגרף קשיר, זהו עץ פורש.
סיבוכיות מקום: סיבוכיות המקום היא O(|V|), הנדרשים עבור תור הקדימויות Q והמילון DistEst.
אם אין מסלול מהמקור לקודקוד מסוים v, יתקיים DistEst[v]=inf ו-Prev[v]=nil.
הערכת המרחק תמיד גדולה או שווה למרחק האמיתי.
מאחר שכל מסלול קל ביותר מכיל תת-מסלולים שגם הם מסלולים קלים, לבעיה יש .
כלומר, הפתרון יכול להבנות מפתרון בעיות קטנות יותר.
בעיות מסוג זה מתאימות לפתרון בעזרת אלגוריתמים חמדניים ותכנון דינמי.
החמדנות של האלגוריתם באה לידי ביטוי בכך שהאלגוריתם בוחר את הקודקוד שנראה בשלב הנוכחי כקרוב ביותר.
ניתן לראות את הגישה החמדנית כפתרון יעיל של בעיית תכנון דינמי.
נסמן ב-S את קבוצת הקודקודים שנשלפו מתור הקדימויות.
נוכיח באינדוקציה על |S|, שלכל קודקוד ב-S, המסלול שהאלגוריתם מצא הוא אכן המסלול הקל ביותר.
נוכיח שלכל קודוקד שנשלף מהתור, המסלול שהאלגוריתם מצא הוא אכן המסלול הקל ביותר (נכון מהאיטרציה בה הוא נשלף מהתור).
ההוכחה תבוצע באינדוקציה על מספר הקודקודים שנשלפו מהתור.
בסוף ריצת האלגוריתם, כל הקודקודים נשלפו מהתור, ולכן האלגוריתם נכון.
כמו בפסאודו קוד הנ"ל, נסמן ב-DistEst[v] את הערכת המרחק מ-s ל-v.
בנוסף, נסמן ב-TrueDist[v] את המרחק הקל ביותר מ-s ל-v.
כשטרם נשלפו קודקודים מהתור, הטענה מתקיימת באופן ריק.
כשקודקוד אחד נשלף, אז בהכרח זהו קודקוד המקור s.
בגרף בעל משקלים אי-שליליים, המסלול הקל ביותר מ-s לעצמו הוא המסלול שמכיל רק את s.
נניח שנשלפו k קודקודים, כך שלכולם האלגוריתם מצא את המסלול הקל ביותר האמיתי (הנחת האינדוקציה).
נסמן ב-v את הקודקוד ה-k+1 שנשלף מהתור, ונוכיח שגם עבורו האלגוריתם מצא את המסלול הקל ביותר האמיתי.
יהי Q מסלול כלשהו מ-s ל-v.
נוכיח שמשקלו איננו קטן משל .
נסמן ב-u את הקודקוד שקודם ל-v במסלול הקל ביותר שהאלגוריתם מצא עד כה (Prev[v] בפסאודו קוד הנ"ל).
בנוסף נסמן ב-y את הקודקוד הראשון ב-Q שאיננו אחד מ-k הקודקודים הראשונים שנשלפו, וב-x את הקודקוד שלפני y במסלול Q.
בגלל שהקשת uv נשלפה מתור הקדימויות לפני xy, מתקיים (במילים: הערכת המשקלים של המסלול P קטנה או שווה להערכת המשקל של המסלול Q).
אחרת x היה נשלף מתור הקדימויות לפני u.
לפי הנחת האינדוקציה והעובדה שהאלגוריתם כבר ביקר ב-u ו-x, ניתן להציב את TrueDist במקום DistEst: .
כלומר, אפילו תת-המסלול של Q מ-s ל-y איננו עדיף על .
הוספת הקשתות הנוספות במסלול Q רק יכולה להגדיל את המשקל.
ולכן המשקל של המסלול שאלגוריתם דייקסטרה מצא קטן או שווה לכל מסלול אחר מ-s ל-v.
כאשר בגרף יש משקלים שליליים, לא מובטח שאלגוריתם דייקסטרה יימצא את המסלול הקצר ביותר.
בהוכחת הנכונות הנ"ל, הביטוי איננו נכון, משום שייתכן ש-w(xy) שלילי.
במילים אחרות, דייקסטרה מניח שהמסלול הקל ביותר ל-v חייב לעבור בקודקודים שקרובים יותר למקור.
אך כאשר יש צלעות שליליות, לא נכון להניח זאת.
כפי שניתן לראות בדוגמה, יכול להיות מסלול בו קשת חיובית כבדה ש"מחביאה" מדייקסטרה שאחריה יש קשתות שליליות, שיכולות לקזז את הקשת הכבדה, ואף להפוך את המסלול לקל ביותר.
סיבוכיות זמן ובחירת מבנה נתונים לתור הקדימויות
בביטויי הסיבוכיות בערך זה, V ו-E מתייחסים למספר הקודקודים והקשתות בגרף (בהתאמה), ולא לקבוצת הקודקודים\קשתות עצמה.
כל קודקוד מוכנס ומוצא מתור הקדימיות בדיוק פעם אחת.
בגרף מכוון, כל קשת תופיעה פעם אחת בלולאת ה-for (שורה 10), ולכן כמות הקריאות ל-DecreaseKey היא לכל היותר .
לכן סיבוכיות הזמן במקרה הגרוע היא:
נבחן כיצד הסיבוכיות תושפע מבחירת מבנה הנתונים לתור הקדימויות.
הבחירה הנאיבית ביותר היא רשימה (זהו גם המימוש שהיה ידוע בשנות החמישים, כשאלגוריתם דייקסטרה הומצא).
עלות EXTRACT_MIN היא , ו-DECREASE_KEY ב- (בהנחה שהקודקודים ממוספרים, או שניתן להגיע אליהם בזמן קבוע באמצעות מצביע).
סך הכל זמן הריצה של האלגוריתם הוא .
אם הגרף צפוף מאוד (), אז זוהי הסיבוכיות הטובה ביותר האפשרית, משום שאי אפשר להתחמק מלסרוק את כל הקשתות בגרף.
אך עבור המקרה הכללי, הומצאו מגוון תורי קדימויות יעילים יותר.
בחירה פופולרית היא ערימה בינארית, שהוצע על ידי וויליאמס ב-1964. בערימה בינארית האתחול לוקח זמן ליניארי, ופעולות ה-EXTRACT_MIN ו-DECREASE_KEY ניתנות לביצוע בזמן לוגריתמי.
לכן הסיבוכיות הכוללת של האלגוריתם היא .
סיבוכיות זו עדיפה על רשימה כל עוד .
אופציה נוספת היא ערימה d-ארית, מעין הכללה של ערימה בינארית עם סיבוכיות דומה.
על אף שזוהי לא הסיבוכיות מקרה גרוע הטובה ביותר, בפרקטיקה זו בחירה יעילה ופופולרית.
תורי הקדימויות המניבים את הסיבוכיות הטובה ביותר מסתמכים על ההבנחה הבאה: במקרה הגרוע, כמות הקריאות ל-DECRESE_KEY גדולה בסדר גודל מכמות הקריאות ל-EXTRACT_MIN (שכן כמות הקשתות בגרף יכולה להגיע לריבוע כמות הקודקודים).
כלומר, יש יתרון לתור קדימויות שמאפשר לבצע את DECREASE_KEY בזמן קבוע, ומשאיר את EXTRACT_MIN בזמן לוגריתמי.
בעזרת תור קדימויות כזה, אלגוריתם דייקסטרה רץ בזמן.
נחקרו מגוון תורי קדימויות נוספים, שהם מחוץ להיקף הערך.
במודל החישובי הסטנדרטי, לא ניתן לשפר את הסיבוכיות של אלגוריתם דייקסטרה מעבר ל-O(VlogV+E).
אחרת, יופר החסם תחתון למיון , שכן דייקסטרה סורק את הקודקודים לפי סדר מרחק עולה.
לכן דייקסטרה לא נופל מכל אלגוריתם מסלולים קלים אחר שמסתמך על מיון קודקודים.
+סיבוכיות מקרה גרועמבנה נתוניםאתחולEXTRACT_MINDECREASE_KEYאלגוריתם דייקסטרההערותרשימה -ערימה בינאריתערימת פיבונאצי, relaxed heapניתוח לשיעורין,
ביצועים פרקטיים וניתוח מקרה ממוצע
ערימת פיבונאצי (רגילה או חזקה) ותור ברודאל אינם נפוצים בפרקטיקה, משום שהם מורכבים למימוש וברוב המקרים אינם מניבים ביצועים טובים יותר (על אף הסיבוכיות מקרה גרוע הטובה יותר).
הסיבות לפער בין הביצועים האמפיריים לסיבוכיות מקרה גרוע ביותר נובעת מגורמים קבועים משמעותיים ש"מוחבאים" בסימון האסימפטוטי, ומפער בין המקרה הגרוע ביותר למקרים נפוצים יותר.
נבחן למשל את תור הקדימויות שנבחר בספריות קוד פופולריות: ערימה בינארית נבחרה בספריות בשפת פייתון (NetworkX), C#, ראסט, ו-Go; בעוד ש-Boost, ספריית C++ יעילה ופופולרית, משתמשת בערימה d-ארית (d=4).
העדפה זו נתמכת גם על ידי מחקרים אקדמיים שביצעו מבחנים אמפיריים.
ניתוח מקרה ממוצע עוזר לתת הסבר תאורטי לפער בין הביצועים בפרקטיקה לסיבוכיות מקרה גרוע.
במקרה הגרוע נעשה מספר יוצא דופן של קריאות ל-DECREASE_KEY, ביחס למקרה הממוצע.
בממוצע, מספר הקריאות הנוספות ל-DECREASE_KEY (ביחס ל-EXTRACT_MIN) איננו מספיק כדי להצדיק את הגדלת הגורמים הקבועים שנדרשים עבור EXTRACT_MIN (כפי שקורה בערימת פיבונאצ'י).
וטרג'אן (1996) הראו שמספר הקריאות הצפוי ל-DECREASE_KEY חסום על ידי , במודל בו ההנחה היחידה היא שעבור כל קודקוד, משקלי הקשתות מוגרלות באופן בלתי תלוי מאותה התפלגות.
זמן הריצה הצפוי של אלגוריתם דייקסטרה עם ערימה בינארית הוא לעומת עם ערימת פיבונאצי.
לערימת פיבונאצ'י יש יתרון (אסימפטוטי) רק כאשר, ואפילו אז היחס בין זמני הריצה הוא רק , שבפרקטיקה זניח לעומת הגורמים הקבועים בערימת פיבונאצ'י.
יש וריאציה של אלגוריתם דייקסטרה בעלת זמן ריצה ממוצע ליניארי (כאשר ידוע חסם למשקל המקסימלי, והמשקלים מתפלגים אחיד).
אם המשקלים הם מספרים שלמים, יש תורי קדימויות מיוחדים שיכולים לשפר את הסיבוכיות.
מאפשר לדייקסטרה לרוץ בזמן O(E+V*C), שכן הוא מאפשר לבצע DECREASE_KEY ב-O(1) ו-EXTRACT_MIN ב-.
תור דלי מנצל את כך שניתן לחלק את המפתחות בתור הקדימויות בין C+1 דליים (כאשר C הוא המשקל המקסימלי בגרף), שכל אחד מכיל רשימה מקושרת של קודקודים בעלי מפתח זהה.
ייתכן שהמפתח המזוהה עם דלי ישתנה, אך תמיד יהיה צורך רק ב-C+1 דליים.
המפתחות בתור תמיד יהיו בטווח בין המינימום הנוכחי ל-, או שהמפתח אינסופי (האלגוריתם טרם סרק את הקודקוד).
נוכיח טענה זו כ: באתחול טענה זו נכונה באופן טריויאלי.
בכל איטרציה, בתחילתה מבוצע EXTRACT_MIN שאיננו מקטין את המינימום, ולכן לא מפר את השמורה; ו-DECREASE_KEY גם איננו מפר את השמורה, שכן המפתח החדש הוא: .
תור דלי הוא דוגמה בסיסית ל, שהם תורי קדימויות המותאמים למקרים בהם ערך המינימום לא קוטן.
הנחה זו מתאימה לדייקסטרה, שסורק קודקודים בסדר עולה של מרחקם מהמקור.
תור קדימויות מונוטוני נוסף הוא , שמשפר את תור דלי בכך שדליים מכילים מספר מפתחות, אך דליים של מפתחות שקרובים יותר למינימום יהיו "צרים" יותר (יכילו פחות מפתחות).
זמן הריצה של דייקסטרה עם ערימת בסיס הוא , ואם משתמשים בערימת בסיס עם שתי רמות מתקבל זמן ריצה של .
עבור גרפים מכוונים, סיבוכיות המקרה הגרוע הטובה ביותר הושגה על ידי Thorup ב-2004: (O(E+Vloglog(min{V,C}).
יש וריאציה של דייקסטרה בעלת זמן ריצה ממוצע ליניארי O(E).
עבור גרפים לא מכוונים, ישנה אפילו וריאציה שרצה ב-O(E) במקרה הגרוע.
+סיבוכיות מקרה גרוע (משקלים שלמים)מבנה נתוניםEXTRACT_MINDECREASE_KEYאלגוריתם דייקסטרהתור דלי (שכבה אחת)O(C)O(1)O(E+VC)תור דלי (2 שכבות)O(sqrt(C))O(1)תור דלי עם k שכבותO(k)ערימת בסיס (שכבה אחת)O(logC)O(1)ערימת בסיס (2 שכבות)O(1)הערימה של Thorup (2004)O(1)O(loglogV)O(EloglogV)
כאשר הגרף מייצג רשת תקשורת, אלגוריתם דייקסטרה יכול לשמש כדי למצוא את נתיב התקשורת האופטימלי בין שתי רכיבים ברשת.
פרוטוקלי הניתוב Open Shortest Path First ו- משתמשים בדייקסטרה לצורך זה.
כאשר הגרף מיצג רשת כבישים, ניתן להשתמש בדייקסטרה כדי לחשב איך כדאי להגיע מנקודה לנקודה.
מציאת הנתיב הקצר ביותר שימושית עבור אפליקציות ניווט, בעיות לוגיסטיקת תחבורה, תכנון תנועה ברובוטיקה, ועבור שחקנים ממוחשבים במשחקי מחשב.
בעיית הניווט הייתה מהיישומים המוקדמים ביותר של האלגורתים (ראה פרק ההיסטוריה).
עד שנת 2011 שירות המפות של בינג השתמש ב"גרסה מותאמת" של דייקסטרה.
כיום ישנם אלגוריתמים טובים יותר מדייקסטרה, אך במקרים רבים הם עדיין בעלי זיקה כלשהי אליו (ראה המחשות בפרק האופטימיזציה).
ישנן בעיות מעשיות רבות שניתנות לפתרון על ידי דייקסטרה, אך פותחו עבורם אלגוריתמים יעילים יותר (לעיתים בסדרי גודל משמעותיים).
עם זאת, במקרים רבים האלגוריתמים היעילים הם בעלי קשר כלשהו לאלגוריתם דייקסטרה.
ייתכן שהקשר הוא רעיוני, שניתן לבצע רדוקציה גרפית, או שאפילו מתבצעת הרצה של אלגוריתם דייקסטרה באחד משלבי האלגוריתם היעיל.
נניח שאנו מעוניינים למצוא את המסלול הקל ביותר מקודקוד מקור לקודקוד יעד (אחד).
בדייקסטרה דו-כיווני, מבצעים 2 הרצות של דייקסטרה: אחד מתחיל מהמקור, ושני מתחיל מהיעד ומתייחס לכיוון הקשתות הפוך.
מקדמים את ההרצות באותו הקצב - כל פעם שההרצה מהמקור שולפת קודקוד מתור הקדימויות, גם ההרצה מהיעד שולפת קודקוד.
האלגוריתם עוצר כאשר 2 ההרצות נפגשות.
התמונות הבאות מדגימות את שיפור הביצועים.
בשמאל, הרצה של דייקסטרה קלאסי, מבצעת חיפוש בעיגול בעל רדיוס R.
בימין, הרצה של דייקסטרה דו-כיווני, מבצעת חיפוש ב-2 עיגולים בעלי רדיוס R/2. בדוגמה זו, דייקסטרה דו-כיווני מוצא את המסלול בפחות מחצי מהאיטרציות של דייקסטרה קלאסי.
ניתן לראות את אלגוריתם A* כוראיציה של דייקסטרה שמשתמשת בפונקציית יוריסטיקה כדי למצוא את המסלול הקצר ביותר ליעד ספציפי, תוך סריקת פחות קודקודים.
באלגוריתם A* נשלף הקודוקד v שממזער את DistEst[v]+h(v), כאשר h היא פונקציית יוריסטיקה האומדת את המרחק מ-v לקודקוד היעד.
השוו זאת לדייקסטרה, אשר שולף את הקודקוד שממזער את DistEst[v] בלבד.
במקרים רבים היוריסטיקה מאפשרת לאלגוריתם לנצל ידע חיצוני על הקודקודים.
למשל, אם הגרף מייצג מיקומים, ניתן להשתמש במרחק האוקלידי בין v ליעד בתור פונקציית היוריסטיקה.
כך אלגוריתם החיפוש יודע לוותר מראש על כיווני חיפוש מיותרים, ו"לכוון" ליעד.
עם זאת, כדי להבטיח פלט נכון, ישנם הגבלות מסוימות על פונקציית היוריסטיקה , ועבור קלטים מסוימים פונקציית המרחק האוקלידי לא מקיימת תנאים אלו.
אם פונקציית היוריסטיקה מקיימת לכל קשת , אז A* שקול להרצה של דייקסטרה עם הפחתת משקלי הקשתות: .
מאחר שניווט הוא אחד מהיישומים החשובים של מציאת המסלול הקל ביותר, פותחו אלגוריתמים שמנצלים תכונות של רשתות כבישים.
אופטימיזציה נפוצה בתחום זה היא transit node routing .
האופטימיזציה מותאמת לכך שידרשו לחשב מספר מסלולים קלים ביותר, ולכן משתלם לבצע עיבוד מקדים.
לרוב, לעיר יש מספר קטן של נקודות יציאה\כניסה.
לכן, נסיעות ארוכות לרוב תמיד יעברו באותה קבוצת מצומצמת של קודקודים שמשמשים לכניסה\יציאה מאזורים מיוחדים (למשל ערים).
קודקודים אלו נקראים transit nodes.
אלגוריתמי transit node routing מחשבים מראש את המסלולים הקצרים ביותר בין ה-transit nodes (ייתכן שבעזרת אלגוריתם דייקסטרה).
כשמתקבלת בקשה למציאת מסלול אופטימלי ממקור כלשהו, האלגוריתם מחפש את המסלול שמצמצם את: המרחק מהמקור ל-transit node בעיר של המקור + המרחק מה-transit node של המקור ל-transit node של היעד + המרחק מה-transit node של עיר היעד ליעד עצמו.
דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים
ניתן לראות את אלגוריתם דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים.
בפרט, אלגוריתם דייקסטרה שקול לאלגוריתם חיפוש לרוחב בגרף שבו כל המשקלים שווים ל-1.
סיבוכיות אלגוריתם חיפוש לרוחב היא O(V+E), בהשוואה ל-O(VlogV+E) של דייקסטרה.
כלומר, בעיית המסלול הקצר ביותר בגרף לא ממושקל היא קלה יותר מאשר בגרף ממושקל.
אלגוריתם חיפוש לרוחב יכול למצוא מסלול קצר ביותר בגרף ממושקל באופן הבא: ניצור גרף חדש, G', שבו עבור כל קשת e=uv ניצור w(e) קשתות חדשות בעלות משקל=1 המחברות את u ו-v דרך w(e)-1 "קודקודי דמה" חדשים.
אך שיטה זו מגדילה משמעותית את גודל הגרף שעליו צריך לבצע חיפוש.
ניתן לראות את דייקסטרה כאופטימיזציה של שיטה זו, אשר אינה דורשת הגדלה מלאכותית של הגרף.
האלגוריתם הקלאסי לבעיה זו הוא אלגוריתם בלמן-פורד.
נהוג ללמוד אלגוריתם זה לצד דייקסטרה בקורסי מבוא לאלגוריתמים רבים.
בלמן-פורד דומה במובנים מסוימים לדייקסטרה: גם הוא מיישם את התבנית האלגוריתמית של פורד לאלגוריתמים למציאת המסלול הקצר ביותר , וגם הוא אלגוריתם חמדן המשתמש בתכנון דינמי.
סיבוכיות הזמן של אלגוריתם בלמן-פורד היא O(VE).
זו הייתה הסיבוכיות מקרה גרוע הטובה ביותר שהייתה ידועה עד ל-2023, אז פורסם אלגוריתם אקראי בעל סיבוכיות זמן של Õ(EV^8/9) בסבירות גבוהה.
כלומר, בעיית המסלול הקצר ביותר היא קשה יותר כאשר יש בגרף משקלים שליליים.
האלגוריתם של ג'ונסון מוצא מסלולים קצרים ביותר בין כל זוג קודקודים בגרף, באמצעות שילוב כוחות בין בלמן-פורד ודייקסטרה.
עבור גרף לא מכוון, יש אלגוריתם אקראי שרץ ב- ב (כלומר, כשהקלט שואף לאינסוף, ההסתברות שואפת ל-1).
האלגוריתם הוא וריאציה על אלגוריתם דייקסטרה, שבה רק תת-קבוצה מצומצמת של הקודקודים נמצאת בתור הקדימויות.
בנוסף, ישנם מקרים פרטיים של גרפים מכוונים בהם ניתן למצוא אלגוריתם בעל סיבוכיות עדיפה מדייקסטרה.
ישנם גם שיפורים עבור גרפים מישוריים, גרפים חסרי מעגלים, וקלט גאומטרי.
המחקר המתמטי המודרני על מציאת המסלול הקל ביותר בגרף בעל משקלים חיוביים החל בשנות החמישים של המאה ה-20. ב-1956 חוקר ממכון ראנד פרסם תבנית לאלגוריתמים למציאת המסלול הקל ביותר, שאלגוריתם דייקסטרה מיישם.
אלגוריתם דייקסטרה פורסם באופן בלתי תלוי ב-1957 על ידי חוקרים ממכון CASE, ב-1959 בידי אדסחר דייקסטרה (שהגה את האלגוריתם כבר ב-1956) וב-1960 על ידי אנשי חקר ביצועים.
בנוסף, בתעשייה נעשה שימוש באלגוריתם זהה או דומה, לפחות בפרויקט אחד.
פורד (1956): תבנית לאלגוריתמים למציאת המסלול הקל ביותר
ב-1956 ממכון ראנד תיאר תבנית לאלגוריתמים למציאת המסלול הקל ביותר.
לתבנית זו תואמים אלגוריתם דייקסטרה, כמו גם אלגוריתם בלמן-פורד המסוגל לעבוד עם משקלים שליליים (וקרוי על שם פורד בזכות תבנית זו).
אך התבנית היא כללית, ויכולה להתאים באותה מידה גם לאלגוריתמים בעלי סיבוכיות אקספוננציאלית.
התבנית של פורד:פורד לא ציין אף כלל לבחירת הקשת .
אלגוריתם דייקסטרה בוחר את הקשת שממזערת את .
דייסקטרה תכנן את האלגוריתם ב-1956, במטרה להציג את יכולות המחשב בטקס החניכה החגיגי שלו.
דייסקטרה רצה לבחור בעיה אלגוריתמית שגם קהל לא מתמטי יוכל להבין.
הבעיה שבחר בה הייתה מציאת המסלול הקצר ביותר בין ערים הולנדיות.
דייסקטרה מספר שהוא תכנן את האלגוריתם בכ-20 דקות, בזמן הפסקת קפה שלקח כשעשה קניות עם ארוסתו.
דייסקטרה האמין שדווקא משום שלא היה יכול להשתמש בעפרון ונייר, הוא אולץ לחשוב על אלגוריתם פשוט ואלגנטי.
דייסקטרה פרסם את האלגוריתם רק כ-3 שנים לאחר המצאתו, ב-1959. תיאור האלגוריתם התפרס על פני עמוד אחד בלבד, מתוך מאמר בן 2.5 עמודים שכלל גם תיאור של אלגוריתם גרפי נוסף.
המאמר לא עסק בבחירת מימוש לתור הקדימויות (למעשה דייקסטרא כלל לא השתמש במונח זה), ולכן בטקסטים מודרניים לעיתים מתייחסים לסיבוכיות הזמן של האלגוריתם המקורי כ-.
דייסקטרה אמר שב-1956 "אלגוריתם למציאת המסלול הקל ביותר בקושי נחשב למתמטיקה: יש מספר סופי של מסלולים מ-A ל-B וברור שאחד מהם הוא הקצר ביותר, אז על מה כל המהומה?".
דייקסטרא החליט לפרסם מאמר על האלגוריתם 3 שנים לאחר המצאתו, כאשר עורך של כתב עת חדש, שעסק גם בנושאים שכיום ייחשבו כחלק ממדעי המחשב, פנה לדייסקטרה ושאל אם יש לו מה לתרום לכתב העת.
בתחילת שנות השישים דייסקטרה נתקל לראשונה בטקסט שקורא לאלגוריתם על שמו, בספר לימוד גרמני.
במקביל לדייקסטרה, חוקרים אחרים פיתחו את האלגוריתם ופרסמו אותו.
ב-1957 התפרסם תיאור של האלגוריתם במאמר של חוקרים מ באוהיו.
התיאור פורסם בדו"ח שנתי של פרויקט מחקר שבוצע עבור ה-Combat Development Department ב-Electronic Proving Ground של צבא ארצות הברית.
המאמר לא התבלט בזמן פרסומו, אך בהסתכלות היסטורית הוא זכור כתגלית עצמאית של אלגוריתם דייקסטרה.
ב-1960 Whiting & Hillier פרסמו מאמר נוסף שתיאר את האלגוריתם.
המאמר פורסם בכתב עת העוסק בחקר ביצועים, והמוטיבציה נבעה מבעיות תחבורה ותקשורת.
Dantzig פרסם אלגוריתם דומה ב-1960, אך הוא היה פחות יעיל.
LEO 1 היה מחשב בריטי שהחל לפעול ב-1951. המחשב היה שייך לתאגיד המזון J.
Lyons and Co., שגם השכיר את שירותי המחשוב לגורמים אחרים.
ב-1955 שכרו את שירותי המחשוב לטובת חישוב המרחק בין תחנות הרכבת שלהם.
בניסוח גרפי, זוהי הבעיה של מציאת המסלול הקצר ביותר בין כל זוג קודקודים.
על הבעיה עבד רוג'ר קולמן, תחת ניהולו של דייוויד קמינר.
כחלק מפתרון הבעיה, פותח אלגוריתם שאפשר להחשיב כגרסה מוקדמת של אלגוריתם דייסקטרה.
עם זאת, האלגוריתם של קולמן כלל הרבה התאמות לבעיה הספציפית של British Railways.
בנוסף, האלגוריתם מעולם לא פורסם, והידע שלנו עליו מתבסס על ראיונות שחובבי היסטוריית מחשוב ערכו עם קולמן בשנות האלפיים.
קולמן לא המשיך לעסוק במדעי המחשב, ועד לאותם ראיונות הוא לא ידע על קיומו של האלגוריתם של דייסקטרה ועל החשיבות ההיסטורית של המצאתו שלו.
אלגוריתם למפל-זיו הוא אלגוריתם לדחיסת נתונים שפותח על ידי אברהם למפל ויעקב זיו מהטכניון.
במשך השנים התפתחו אלגוריתמים שונים על בסיס אלגוריתם למפל-זיו, ואלו שיפרו את ביצועי דחיסת הנתונים בצורה משמעותית.
הדחיסה היא מסוג דחיסה משמרת מידע, המאפשרת את שחזור המידע הדחוס במלואו, ללא עיוות.
האלגוריתם מתבסס על חלוקת המחרוזת המקודדת לתת-מחרוזות הנקראות פסקאות בתהליך המכונה פיסוק.
כל פסקה מותאמת למחרוזת מעל אלפבית סופי ונבנה מילון בתהליך דינמי.
האלגוריתם הוא אוניברסלי, הדחיסה היא אסימפטוטית אופטימלית, ואין נדרש ידע קודם של התוכן הנדחס.
בריאיון עם פרופ' זיו הוא נתן כהמחשה לאלגוריתם את תפילת אבינו מלכנו המופיעה במחזורי התפילה היהודיים, שבה המילים "אבינו מלכנו" מופיעות רק במשפט הראשון, ואילו ביתר המשפטים מסתפקים באזכור והפניה אליהן.
האלגוריתם הוצג על ידי למפל וזיו בעבודתם בשנת 1977, מכונה גם Sliding Window LZ.
בדחיסה מוגדר מילון בגודל קבוע וחוצץ (Buffer) באורך קבוע.
החוצץ, שנקרא גם "חלון", מתקדם על המחרוזת בעזרת סמן (cursor) ונשמרים שלושה נתונים – מיקום ההתאמה הארוכה ביותר שמתחילה במילון ביחס לסמן, האורך של ההתאמה הארוכה ביותר, והתו הבא בחוצץ מעבר להתאמה הארוכה שנמצאה.
בתום שמירת הנתונים, החלון מקודם באורך ההתאמה שנמצאה ועוד 1. בצורה זו, החלון נע על המחרוזת ומכאן שמו הנוסף של האלגוריתם Sliding Window.
בפרישה, הפורש מחזיק את אותו המילון כמו הדוחס.
עוברים על הקידודים, כך שכל קידוד שנפרש משורשר לסוף המחרוזת שכבר נפרשה.[2] לדוגמה: עבור המילון ABCD, והקידוד (2,6,E) הפלט יהיה ABCDCDCDCDE כאשר 2 הוא המיקום, 6 הוא האורך ו- E הוא התו הבא.
אלגוריתם זה הוא בסיס להתפתחותם של אלגוריתמים יעילים יותר מאותה משפחה.
הנטל החישובי מצוי בשלב בו המקודד מחשב את ההתאמה ובונה את המילון.
מימוש ברוטלי לכל התאמה m כאשר m הוא גודל החוצץ.
מקובל השימוש בטבלת גיבוב לביצוע ההתאמות.
הקטנת החוצץ תגרום להקטנת הסיבוכיות אך ייתכן ויפגע קצב הדחיסה.
האלגוריתם ניתן למימוש באופנים שונים הנבדלים בטווחים של הזוגות אורך-מרחק ובאופן ייצוגם.
באלגוריתם המקורי משנת 1977, הפלטים הם שלושה ערכים בכל זמן: האורך והמרחק של ההתאמה הגדולה ביותר שנמצאה בחוצץ, והתו העוקב להתאמה.
אם שני תווים רציפים בקלט יכולים להידחס רק כתווים, אזי האורך של אורך-מרחק הוא 0.
אלגוריתם LZSS משפר את אלגוריתם LZ77 על ידי שימוש בדגל של ביט אחד לציון האם חתיכת המידע הבאה צריכה להיות מקודדת כתווים או כצמד אורך-מרחק ומקודדים לתווים אם הצמד אורך-מרחק ארוך יותר.
בפורמט PalmDoc הצמד אורך-מרחק מקודד על ידי רצף של שני בתים.
מתוך 16 הביטים הבונים את שני הבתים, 11 ביטים משמשים לקידוד המרחק, 3 ביטים משמשים לקידוד האורך, ושני הביטים הנותרים מציינים למפענח את תחילתם של שני הבתים אותם צריך לפענח.
במשחקים רבים של Electronic Arts הגודל בבתים של הצמד אורך-מרחק נשמר בתוך הבית הראשון המכיל את אורך-מרחק בעצמם, כתלות אם הבית הראשון מתחיל ב 0, 10, 110 או 111. אורך הצמד אורך-מרחק יכול להיות בין 1 ל-4 בתים.
משנת 2008, השיטה הפופולרית ביותר בשימוש אלגוריתם LZ77 לדחיסה הנה DEFLATE, המשלבת את LZ77 עם קוד האפמן.
תווים, אורכים וסמלים מציינים את סופו של בלוק המידע הנוכחי ומוחזקים במילון א"ב אחד, המרחקים מוחזקים במילון א"ב אחר.
מאחר שהמרחק מופיע רק לאחר האורך, לא ניתן לטעות עם סמל אחר ולהפך.
Lempel–Ziv–Storer–Szymanski LZSS הוא נגזרת של אלגוריתם LZ77. הוא נוצר בשנת 1982 על ידי ג'יימס סטורר ותומס זימנסקי.
ההבדל העיקרי בין LZSS ו-LZ77 הוא שבאחרון, ההפניות במילון יכולות להיות לעיתים ארוכות יותר מהקטע המקורי טרם הקידוד.
באלגוריתם LZSS אם הקטע המקודד הוא ארוך יותר מקטע המקור, אזי נשמר קטע המקור.
בנוסף, LZSS משתמש בדגל של ביט אחד לייצוג האם האיבר הבא שצריך לפענח הוא קוד המקור עצמו (בתים) או הצמד אורך-מרחק.
ארכיונים פופולריים כמו PKZip, ARJ, RAR, ZOO, LHarc משתמשים ב LZSS ולא ב LZ77.
גרסאות נוספות הן LZR, LZB, LZH .
הוצג על ידי למפל וזיו בשנת 1978 ומכונה גם בשם Tree Based Algorithm.
האלגוריתם משיג דחיסה על ידי החלפת מידע שחוזר על עצמו במצביע במילון למופע יחיד של אותו מידע.
כל כניסה במילון מחזיקה את הצמד אינדקס ותו כאשר אינדקס הוא אינדקס של כניסה קודמת במילון, והתו ישורשר לתו בכניסה אליה מצביע האינדקס.
לדוגמה עבור המילון D ו- "abc" מחרוזת הקלט כאשר אינדקס 0 מציין את התו הראשון של המחרוזת.
האלגוריתם מאתחל את האינדקס האחרון המתאים (last matching index) ב-0 והאינדקס הפנוי הבא (next available index) ב-1. עבור כל תו במחרוזת הקלט, המילון מחפש התאמה של הצמד {תו, אינדקס אחרון מתאים}.
אם נמצאה התאמה בכניסה מסוימת במילון, אזי האינדקס האחרון המתאים מקבל את ערך האינדקס של הכניסה שנמצאה.
אם לא נמצאה כניסה מתאימה, נוצרת כניסה חדשה במילון {תו, הכניסה האחרונה המתאימה} = [הכניסה הבאה הפנויה]D כאשר הכניסה האחרונה המתאימה מאופסת, והכניסה הבאה הפנויה מקודמת.
כאשר המילון מלא לא ניתן להוסיף כניסות חדשות.
כאשר מגיעים לסוף המחרוזת המקודדת, האלגוריתם מציין אינדקס אחרון מתאים.
המחרוזות מאוחסנות במילון בסדר הפוך והמפענח יודע להתמודד עם הפרישה.
למימוש יעיל של האלגוריתם משתמשים במעבר על עץ סיפות (עץ סיומות, Suffix Tree) או עץ Trie.
העץ ישמש כמילון השומר את המילים המקודדות, כאשר מבנה העץ הוא היררכי.
האלגוריתם LZW או Lempel-Ziv-Welch פותח על ידי אברהם למפל, יעקב זיו וטרי ולץ' (Terry Welch).
הוא פורסם על ידי ולץ' בשנת 1984 ומתבסס על האלגוריתם LZ78 שפותח על ידי למפל וזיו בשנת 1978. האלגוריתם פשוט למימוש ומספק שיפור משמעותי בביצועים מקודמו.
גרסה זו הפכה פופולרית והיא עומדת בבסיס רבות מכלי הדחיסה המסחריים בהם נעשה שימוש במאה ה-21, כדוגמת פורמט GIF.
במדעי המחשב, הפרד ומשול היא פרדיגמת תכנון אלגוריתמים חשובה.
היא מבוססת על שבירה רקורסיבית של הבעיה לשתיים או יותר תת-בעיות מאותה הצורה (או צורה דומה לה), עד שהבעיות הופכות לפשוטות דיין כדי שניתן יהיה לפתור אותן ישירות.
לאחר מכן הפתרונות לתת הבעיות משולבים יחד כדי לתת פתרון לבעיה המקורית.
שיטה זו היא הבסיס לאלגוריתמים יעילים רבים למגוון רחב של בעיות.
לדוגמה: מיון (אלגוריתם מיון מיזוג ואלגוריתם מיון מהיר), מציאת קמור, חיפוש (חיפוש בינארי) ועוד.
אלגוריתמי הפרד ומשול ממומשים בצורה טבעית בתור פרוצדורות רקורסיביות.
במקרה זה, הפתרון של תת-בעיה ניתן בצורה עקיפה כערך שאותו מחזירה הקריאה הרקורסיבית לאלגוריתם.
יחד עם זאת, אלגוריתמי הפרד ומשול יכולים להיות ממומשים גם כאלגוריתם לא רקורסיבי ששומר את פתרונות תת-הבעיות בתוך מבנה נתונים מסוים, כמו מחסנית, תור עדיפויות וכדומה.
גישה זו מאפשרת יותר חופש פעולה בבחירת תת-הבעיה הבאה שמנסים לפתור - דבר החשוב, למשל, באלגוריתמים של תכנון דינמי.
שיטת הפרד ומשול היא כלי חזק לפתרון בעיות סבוכות, דוגמת בעיית מגדלי האנוי: כל שנדרש הוא היכולת לפרק את הבעיה לתת בעיות דומות, היכולת לפתור את המקרים הטריוויאליים של הבעיה, והיכולת למזג את הפתרונות של תת-הבעיות כדי לקבל פתרון לבעיה המקורית.
כך ניתן להימנע מפתרון ישיר של הבעיה, שיכולה להיות מורכבת מאוד, כל עוד ניתן למצוא דרך לצמצם את ממדיה.
מציאת דרך לפרק את הבעיה לתת בעיות ואחר כך לשלב את פתרונותיהם של תת-הבעיות לפתרון לבעיה המקורית היא הקושי העיקרי בפתרון בעיות בשיטת הפרד ומשול.
לרוב שיטת הפרד ומשול נותנת פתרונות יעילים מאוד אסימפטוטית לבעיה הנתונה.
אם, למשל, הקלט לבעיה הוא מגודל , הזמן שנדרש כדי לפרק ולהרכיב מחדש את הבעיה לתת בעיות פרופורציונלי ל-, מספר תת-הבעיות הוא חסום והזמן שלוקח לטפל במקרים הטריוויאליים הוא קבוע, אז ריצת האלגוריתם כולו תהיה מסיבוכיות של - סיבוכיות הנחשבת לטובה למדי.
זה הוא המצב במקרה של מיון מיזוג, למשל.
אלגוריתמי הפרד ומשול מתאימים באופן טבעי למכונות המבוססות על חישוב מקבילי, במספר מעבדים בו זמנית - מכיוון שאין תלות בין תת-הבעיות, ניתן לפתור את תת-הבעיות בו זמנית על מספר מעבדים במקביל.
נטען לעיתים קרובות כי חיסרון בולט של שיטת הפרד ומשול הוא איטיות הרקורסיה - העלות של קריאות נשנות לתת פרוצדורות יחד עם שמירת הקריאה על מחסנית הקריאות עלולה לבטל את יתרונות השיטה.
עם זאת, בעיה זו תלויה בצורת המימוש של הרקורסיה.
אם מקרי הבסיס של הרקורסיה גדולים מספיק, העלות של הרקורסיה יכולה להפוך לזניחה עבור בעיות רבות.
בעיה נוספת של הפרד ומשול היא שעבור בעיות פשוטות, שיטה זו עלולה להיות מסובכת יותר מהגישה האיטרטיבית.
למשל, חיבור של N מספרים יותר פשוט לביצוע על ידי לולאה שסוכמת את המספרים מאשר באלגוריתם הפרד ומשול שמפרק את המספרים לשתי קבוצות, סוכם כל קבוצה בנפרד ואחר מחבר את שני הסכומים שהתקבלו.
אלגוריתמים המשתמשים בשיטת הפרד ומשול
אלגוריתם הפרד ומשול למציאת קמור
אלגוריתם בלמן-פורד הוא אלגוריתם הפועל על גרף מכוון וממושקל, ומשמש למציאת המסלול הקל ביותר מצומת אחד מסוים אל כל אחד משאר הצמתים בגרף.
בכך, אלגוריתם זה משיג אותה תוצאה כמו אלגוריתם דייקסטרה, אך בניגוד לאלגוריתם דייקסטרה הוא עובד גם כאשר הגרף מכיל קשתות בעלות משקל שלילי.
יתר על כן, אם הגרף מכיל מעגל שסכום משקלי קשתותיו שלילי (מה שגורם לכך שאין תשובה מוגדרת לשאלת המסלולים הקצרים) הוא מסוגל לזהות זאת ולהתריע על כך.
בגרף בעל צמתים ו- קשתות, זמן הריצה של האלגוריתם הוא , זמן ארוך יותר מאשר אלגוריתם דייקסטרה.
האלגוריתם משתמש בטכניקה המכונה "הקלה" (Relaxation), ומתבסס על הפעלת הקלה על כל קשתות הגרף עד אשר בוודאות נמצאו המסלולים הקלים ביותר.
לכל צומת בגרף אנו מתאימים משתנה שמייצג את משקל המסלול הקל ביותר שנמצא עד כה של מסלול מ- (הצומת ההתחלתי) ועד .
בתחילת ריצת האלגוריתם לכל צומת שאינו (כי עדיין לא נמצא מסלול כלשהו), ואילו (כי המסלול הטריוויאלי מ- אל עצמו שאינו מכיל קשתות הוא במשקל 0).
לכל צומת אנו שומרים גם משתנה שיצביע על הצומת הקודם לו במסלול הקל ביותר.
בתחילת הריצה כל המשתנים הללו מאותחלים ל-NULL, שפירושו שעדיין לא קיים צומת כזה.
בעזרת המשתנים הללו יהיה ניתן לשחזר את המסלולים הקלים ביותר לאחר סיום ריצת האלגוריתם.
כאשר מבצעים פעולת הקלה על קשת , בודקים האם מתקיים כאשר הוא משקל הקשת.
אם אי השוויון מתקיים, פירוש הדבר שהמסלול הקל ביותר אל שהיה ידוע עד כה הוא כבד יותר מאשר המסלול שמגיע אל במסלול הקצר ביותר שידוע עבורו, ואז עובר מ- אל באמצעות הקשת .
לכן, אם אי השוויון מתקיים, מעדכנים את להיות הקודם ל- במסלול הקל ביותר, ומעדכנים את להיות שווה ל-.
האלגוריתם של בלמן-פורד פועל כך: הוא מבצע איטרציות, כאשר בכל איטרציה הוא עובר על כל הקשתות בגרף ומבצע הקלה על כל אחת מהן.
כל איטרציה משפרת את רמת הדיוק של המסלולים הקלים שנמצאו עד כה, וניתן להוכיח כי לאחר איטרציות יימצאו המסלולים הקצרים ביותר, בתנאי שבגרף אין מעגלים שליליים.