לאלגוריתם החיפוש לעומק יתרונות על אלגוריתם חיפוש לרוחב אם קיימת היוריסטיקה שמסוגלת לעזור לחיפוש. למשל, בחיפוש היציאה ממבוך, אם יופעל חיפוש לרוחב מאמצע המבוך תימצא היציאה רק בשלב האחרון של האלגוריתם. לעומת זאת, בחיפוש לעומק ניתן יהיה למצוא את היציאה כבר בתחילת ריצת האלגוריתם, עוד לפני שיהיה עליו לשוב על עקבותיו, ובפרט אם יש לו דרך טובה להעריך מהו הכיוון הנכון של היציאה. עוד יתרון הוא שסיבוכיות הזיכרון של אלגוריתם חיפוש לעומק היא לכל היותר ליניארית ביחס לרמה בו הוא נמצא ברגע נתון וכמות הפיצולים הממוצעת, בעוד שבחיפוש לרוחב היא אקספוננציאלית ביחס אליהם.
לעומת זאת, אלגוריתם חיפוש לעומק סובל מחסרונות כאשר הגרפים עליהם הוא פועל הם גדולים מאוד. בפרט, בגרפים בעלי מסלולים אינסופיים, האלגוריתם עלול שלא לעצור גם אם האיבר שהוא מחפש נמצא בגרף כי המסלול שבו הוא יבחר עלול להיות מסלול אינסופי שבו האיבר שמחפשים לא נמצא, ואז האלגוריתם יתקדם ללא הפסקה באותו מסלול מבלי לחזור על עקבותיו, וזאת להבדיל מחיפוש לרוחב שמובטח בו שיגיע אל האיבר אותו מחפשים, עם זאת חיפוש לעומק איטרטיבי מעמיק ימנע בעיה זו. כמו כן האלגוריתם לא מבטיח את מציאת המסלול הקצר ביותר בגרף אל המטרה, בשונה מאלגוריתם חיפוש לרוחב.
ניתן להשתמש באלגוריתם חיפוש לעומק בתור בסיס לאלגוריתמים רבים שפועלים על גרפים. למשל, מציאת רכיבים קשירים היטב בגרף, מציאת מסלול אוילרי ומעגלים בגרף או מיון טופולוגי שלו.
אלגוריתם זה נמצא בשימוש באופטימיזציה הרמונית.
תיאור פורמלי.
כאן נציג מימוש רקורסיבי. כל צומת מסומן באחד משלושה צבעים: לבן פירושו שהוא טרם נבדק, אפור פירושו שהוא או צאצאיו בבדיקה ושחור פירושו שהצומת וצאצאיו כבר נבדקו.
function DFS(Start, Goal)
Color(Start, Grey)
if Start = Goal
return True
for Child in Expand(Node)
if not Colored(Child)
if DFS(Child, Goal)=True
return True
Color(Start, Black)
return False
תיאו ואן-גוך
מוזס וילהלם שפירא
מוזס וילהלם שפירא (1830 – 9 במרץ 1884) היה אספן וסוחר עתיקות שחי ופעל בירושלים העות'מאנית במחצית השנייה של המאה ה-19. שפירא, יהודי שהמיר את דתו לנצרות, התפרסם כזייפן עתיקות בינלאומי שעמד במרכזן של שתי פרשות זיוף עתיקות אשר הסעירו את עולם הארכאולוגיה וחקר המקרא בבריטניה, בצרפת ובגרמניה.
בשערורייה הראשונה שהסתבך בה, ב-1873, התברר כי אוסף חרסים מואבי בן אלפי פריטים שמכר למוזיאון בברלין אינו אלא עבודת זיוף זולה של קדרים בני התקופה. עשור לאחר מכן, לאחר ששיקם את המוניטין שלו כסוחר עתיקות מומחה, הסתבך בשנית כשניסה ב-1883 להציע למכירה למוזיאונים אחדים באירופה אוסף מגילות שנתגלו, לכאורה, במערות באזור ים המלח. כאשר שפירא עמד על סף סגירת עסקה עם המוזיאון הבריטי בלונדון, נקבעו המגילות בידי מומחים כמזויפות בחוות דעת שהביאה לכישלון העסקה, להתאבדותו של שפירא ולאובדן המגילות.
64 שנים מאוחר יותר נתגלו מגילות מדבר יהודה במערות בקומראן, ועלתה התהייה שמא הקביעה בשעתה כי מגילותיו של שפירא מזויפות הייתה נמהרת מדי, ואולי אף הייתה אחת ההחמצות הגדולות בתולדות הארכאולוגיה. תהייה זו נותרה בלתי פתורה עד היום.
חייו.
מיהודי ברוסיה לנוצרי בירושלים.
משה שפירא נולד כיהודי בקמניץ פודולסק שבאימפריה הרוסית (כיום באוקראינה) למשפחה אדוקה, מתלמידי הגאון מווילנה. בבגרותו החל נודד ברחבי אירופה, התנצר, ושינה את שמו למוזס וילהלם שפירא. ב-1856 הגיע לירושלים, שם נחשף להשפעתו של המיסיון האנגליקני של "החברה הלונדונית להפצת הנצרות בקרב היהודים" שפעל בעיר. הוא הצטרף לכנסיית המשיח שברובע הנוצרי, ולמד ועבד בבית המלאכה של המיסיון תחת הדרכתו של קונרד שיק, לימים האדריכל הנודע ובונה ירושלים.
ב-1861 נשא שפירא לאישה את רוזטה יקל, אחות גרמניה ממסדר הדיאקוניסות, אותה הכיר כשסעדה אותו במחלתו עת אושפז בבית החולים הפרוטסטנטי. ב-1865 נולדה בתם הבכורה אוגוסטה-לואיזה-וילהלמינה, וכעבור 4 שנים, ב-1869, נולדה הבת הצעירה מריה-רוזטה (לימים הסופרת מרים הרי). המשפחה התגוררה בבית בתוך מתחם כנסיית המשיח.
ירושלים של אותה תקופה מלאה אנשי דת, צליינים נוצרים, חוקרי מקרא למיניהם, דיפלומטים ממעצמות העולם, וכולם שלחו ידיהם בארכאולוגיה ובאיסוף עתיקות ומזכרות שהביקוש להם באירופה היה רב. שפירא נתוודע לעולם זה, גילה חוש עסקי ממולח, שאפתנות ושליטה בשפות רבות, והחליט לבנות את עתידו כסוחר. בהיותו מומר, נידתה אותו הקהילה היהודית בעיר וכינתה אותו "המשומד" ו"עבד המיסיון".
בשנת 1869 פתח שפירא חנות ברחוב הנוצרים, רחוב המסחר הראשי של הרובע הנוצרי בעיר העתיקה. בחנותו מכר מזכרות תיירים ועתיקות שרכש מאיכרים ערבים, כשלצידו עוזרו-שותפו סלים אל-ח'ורי, דרגומן ומדריך תיירים ערבי-נוצרי שכבר רכש לעצמו שם של נוכל ערמומי. בעזרתו של אל-ח'ורי השכיל שפירא ליהנות מפירות גל הצליינות ששטף את העיר ולעשות חיל בעסקיו. שפירא, ששנים אחדות קודם לכן הגיע לעיר בחוסר כל, היה לסוחר אמיד ששמו הלך לפניו כמומחה לעתיקות. הוא שכר את "טירת אגא רשיד" בעיר החדשה, וילה מפוארת עם גן רחב ידיים (לימים בית טיכו), ועבר לגור בו עם אשתו רוזטה ושתי בנותיו, אוגוסטה ומריה. הוא בנה לעצמו מערך קשרים בינלאומי שכלל מוזיאונים, אוניברסיטאות ומוסדות מחקר במדינות אירופה, אנשי דת ותאולוגים נוצריים ששהו או ביקרו בירושלים, שייח'ים בדואים ברחבי מדבריות המזרח התיכון, קהילות יהודיות נידחות, אספנים שונים, ארכאולוגים מקצועיים וחובבים, ובין אלה רכש, מכר, תיווך, ייעץ והתייעץ. השלט בחזית חנותו ברחוב הנוצרים ציין שהוא "סוכן מורשה של המוזיאון הבריטי".
פרשת חרסי מואב.
בשנת 1868 התגלה בדיבון שבמואב, בעבר הירדן, לוח אבן בזלת שחורה עם כתובת, שנודע עד מהרה בשם "מצבת מישע" ועורר עניין אדיר בעולם הארכאולוגיה. גם שפירא גילה עניין רב בתגלית, ואף שלא היה שותף לגילויה, היה עד לחילוצה ושחזורה בידי הארכאולוג והדיפלומט הצרפתי שארל קלרמון-גנו, יחד עם עוזרו סלים. בחושיו העסקיים הבחין בפוטנציאל המסחרי הטמון בעתיקות מואביות, קשר קשרים עם שייחים בדואים בעבר הירדן, ותוך זמן קצר הופיעו בחנותו מאות חרסים נושאי כתובות מואביות. ב-1872 הצליח למכור 1,700 חרסים מואביים למוזיאון הישן בברלין תמורת סכום נאה, וחרסים נוספים לאספנים פרטיים.
שמחתו של שפירא לא האריכה ימים. הארכאולוג קלרמון-גנו, שמלכתחילה פקפק בשפירא ובאל-ח'ורי, ראה בחנותו של שפירא קבוצת חרסים זהה לחלוטין לזו שנמכרה למוזיאון בברלין והצליח להוכיח כי החרסים המואביים של שפירא מזויפים. לטענתו של קלרמון-גנו, הוא הגיע בחקירתו אל בתי מלאכה של קדרים מקומיים, שהעידו בפניו על ייצור החרסים. ב-1876 פרסמו בלשני השפות השמיות אלברט סוצין ואמיל קאוטש את תוצאות המחקר שערכו בכתובות שעל "חרסי מואב" וקבעו שהן מעשה זיוף. שפירא הנבוך גלגל את כל האחריות לזיוף לפתחו של סלים אל-ח'ורי וטען שהיה קורבן תמים, אך המוניטין שלו כסוחר הגון נפגמו.
שפירא התאושש מהחשיפה המביכה והמשיך בעסקיו. פתיחת תעלת סואץ הגבירה את זרם הצליינים לירושלים, וחנותו של שפירא פרחה. הוא התמקד עתה ברכישה ומכירה של כתבי יד עתיקים. חלק ניכר מזמנו הקדיש למסעות לקהילות המזרח לרכישת גווילי קלף, ולארצות אירופה, למכירתם. בין היתר רכש את כתב היד של פירוש הרמב"ם למשנה, ומכר אותו בברלין. במסעותיו הגיע גם אל קהילות יהודיות בתימן וקיבל מהם ספרי תורה ישנים שיועדו לגניזה בארץ הקודש, ובהם סחר מאוחר יותר. עדויות של תימנים שהגיעו לארץ ישראל, טענו ששפירא הציג עצמו אצלם כרב, והשתתף בתפילותיהם. לפי אחת הטענות, כשנתקל בסירוב למסור או למכור כתבי יד, לא היסס לשחד את אנשי השלטונות העותמאניים כדי שיוציאו בכוח את כתבי היד מידי בני הקהילה.
פרשת המגילות.
ב-1883 טען שפירא כי בידיו 15 מגילות קלף קדומות שרכש מבדואים שמצאום במערה בנחל ארנון בעברו המזרחי של ים המלח, ולטענתו תוארכו למאה השביעית לפנה"ס. ככאלה, היוו לטענתו את כתב היד המקראי הקדום ביותר שנתגלה עד אז. במגילות הופיעה גרסה שונה במקצת של ספר דברים מזו שבנוסח המסורה המוכר לנו, שכללה את עשרת הדיברות ובה דיבר אחד נוסף. המגילות היו בידיו של שפירא מאז 1878, והוא ניסה כבר אז לעניין בהן את המלומד הגרמני קונסטנטין שלוטמן מאוניברסיטת האלה, אך שלוטמן, שהיה אחד המומחים הגרמנים שניכוו והובכו בפרשת חרסי מואב, דחה בבוז את פנייתו וטען שמדובר בזיוף. את הפקפוקים שעלו באשר לאותנטיות של המגילות אמנם דחה שפירא בטענה כי רכש אותן בפרוטות, ולא יעלה על הדעת כי ישקיע אדם מאמץ כה רב בזיוף כזה תמורת רווח כה זעום, אולם הוא המתין חמש שנים נוספות טרם החליט לנסות לצאת איתן שוב להערכת מומחים.
שפירא הגיע עם המגילות לגרמניה ביוני 1883 וניסה מחדש לעניין את הגרמנים בקנייתן. בעודו ממתין להחלטתם ותוצאות בדיקתם, הגיע ב-24 ביולי גם למשרדי הקרן לחקר ארץ ישראל (PEF) שמושבה בלונדון, שם בחנו את המגילות מזכיר הקרן וולטר בזנט, קלוד קונדר ומלומדים נוספים. בזנט הפנה את שפירא אל המוזיאון הבריטי שגילה עניין רב במגילות, ואף הציג שתיים מהן לציבור הרחב, בעוד מומחי המוזיאון בודקים את המגילות האחרות. הידיעה על התעניינות המוזיאון הבריטי והצגת המגילות בו הכתה גלים בבריטניה וברחבי אירופה, ואלפים הגיעו לבקר בתערוכה, ובהם ראש הממשלה ויליאם גלאדסטון. הסכום שנדרש עבור רכישת המגילות היה גבוה מאוד: מיליון ליש"ט, למרות הספקות ההולכים ומתרבים אצל מומחים ביחס למקוריותן.