חיפוש לא מושכל הוא מחלקה של אלגוריתמי חיפוש למטרות כלליות הפועלות בכוח גס. לאלגוריתמי חיפוש חסרי ידע אין מידע נוסף על מצב או מרחב חיפוש מלבד הדרך לחצות את העץ, ולכן זה נקרא גם חיפוש עיוור.
להלן הסוגים השונים של אלגוריתמי חיפוש חסרי ידע:
1. חיפוש רוחב ראשון:
- חיפוש רוחב ראשון הוא אסטרטגיית החיפוש הנפוצה ביותר למעבר בין עץ או גרף. אלגוריתם זה מחפש לרוחב בעץ או בגרף, ולכן הוא נקרא חיפוש רוחב ראשון.
- אלגוריתם BFS מתחיל לחפש מצומת השורש של העץ ומרחיב את כל הצומת היורשים ברמה הנוכחית לפני המעבר לצמתים של הרמה הבאה.
- אלגוריתם החיפוש הראשון הוא דוגמה לאלגוריתם חיפוש כללי.
- חיפוש רוחב ראשון מיושם באמצעות מבנה נתוני תור FIFO.
יתרונות:
- BFS יספק פתרון אם קיים פתרון כלשהו.
- אם יש יותר מפתרון אחד לבעיה נתונה, אז BFS תספק את הפתרון המינימלי הדורש את מספר השלבים המינימלי ביותר.
חסרונות:
- זה דורש הרבה זיכרון מכיוון שכל רמה של העץ חייבת להישמר בזיכרון כדי להרחיב את הרמה הבאה.
- BFS זקוק להרבה זמן אם הפתרון נמצא רחוק מצומת השורש.
דוגמא:
במבנה העץ להלן, הצגנו את מעבר העץ באמצעות אלגוריתם BFS מצומת השורש S לצומת המטרה K. אלגוריתם החיפוש של BFS עובר בשכבות, כך שהוא יעקוב אחר הנתיב שמוצג על ידי החץ המקווקו, וה נתיב שנחצה יהיה:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
מורכבות זמן: ניתן לקבל את מורכבות הזמן של אלגוריתם BFS לפי מספר הצמתים שעברו ב-BFS עד לצומת הרדוד ביותר. כאשר d= עומק הפתרון הרדוד ביותר ו-b הוא צומת בכל מצב.
T (ב) = 1+ב2+ב3+.......+ בד= O (בד)
מורכבות החלל: מורכבות החלל של אלגוריתם BFS ניתנת על ידי גודל הזיכרון של הגבול שהוא O(bד).
שְׁלֵמוּת: BFS הושלם, כלומר אם צומת המטרה הרדוד ביותר נמצא בעומק סופי כלשהו, אז BFS ימצא פתרון.
אופטימליות: BFS הוא אופטימלי אם עלות הנתיב היא פונקציה לא יורדת של עומק הצומת.
2. חיפוש עומק ראשון
- חיפוש עומק ראשון הוא אלגוריתם רקורסיבי למעבר בין עץ או מבנה נתונים של גרף.
- הוא נקרא חיפוש עומק ראשון מכיוון שהוא מתחיל מצומת השורש ועוקב אחר כל נתיב לצומת העומק הגדול ביותר שלו לפני שהוא עובר לנתיב הבא.
- DFS משתמש במבנה נתונים מחסנית לצורך הטמעתו.
- התהליך של אלגוריתם DFS דומה לאלגוריתם BFS.
הערה: מעקב לאחור היא טכניקת אלגוריתם למציאת כל הפתרונות האפשריים באמצעות רקורסיה.
יתרון:
מיין רשימת מערך ב-java
- DFS דורש פחות זיכרון מכיוון שהוא רק צריך לאחסן ערימה של הצמתים בנתיב מצומת השורש לצומת הנוכחי.
- לוקח פחות זמן להגיע לצומת המטרה מאשר אלגוריתם BFS (אם הוא עובר בנתיב הנכון).
חִסָרוֹן:
- קיימת אפשרות שמדינות רבות חוזרות ונשנות, ואין ערובה למציאת הפתרון.
- אלגוריתם DFS הולך לחיפוש עמוק ומתישהו הוא עשוי לעבור ללולאה האינסופית.
דוגמא:
בעץ החיפוש שלמטה, הצגנו את זרימת החיפוש של עומק-ראשון, והוא יפעל לפי הסדר:
צומת שורש--->צומת שמאל ----> צומת ימין.
הוא יתחיל לחפש מצומת שורש S, ויעבור את A, ואז B, ואז D ו-E, לאחר חציית E, הוא יחזור על העץ מכיוון של-E אין יורש אחר ועדיין צומת המטרה לא נמצא. לאחר החזרה לאחור הוא יחצה את צומת C ולאחר מכן G, וכאן הוא יסתיים כאשר הוא מצא את צומת המטרה.
שְׁלֵמוּת: אלגוריתם החיפוש של DFS הושלם בתוך מרחב מצב סופי מכיוון שהוא ירחיב כל צומת בתוך עץ חיפוש מוגבל.
מורכבות זמן: מורכבות הזמן של DFS תהיה שווה ערך לצומת שעבר האלגוריתם. זה ניתן על ידי:
T(n)= 1+ n2+ n3+.........+ nM=O(nM)
כאשר, m= עומק מקסימלי של כל צומת וזה יכול להיות הרבה יותר גדול מ-d (עומק הפתרון הרדוד ביותר)
מורכבות החלל: אלגוריתם DFS צריך לאחסן רק נתיב בודד מצומת השורש, ומכאן שמורכבות החלל של DFS שווה ערך לגודל מערך השוליים, שהוא O(bm) .
אוֹפְּטִימָלִי: אלגוריתם החיפוש של DFS אינו אופטימלי, מכיוון שהוא עשוי ליצור מספר רב של שלבים או עלות גבוהה להגיע לצומת המטרה.
3. אלגוריתם חיפוש מוגבל לעומק:
אלגוריתם חיפוש מוגבל לעומק דומה לחיפוש עומק ראשון עם מגבלה קבועה מראש. חיפוש מוגבל לעומק יכול לפתור את החיסרון של הנתיב האינסופי בחיפוש העומק הראשון. באלגוריתם זה, הצומת במגבלת העומק יטפל מכיוון שאין לו צמתים ממשיכים יותר.
ניתן לסיים חיפוש מוגבל בעומק עם שני תנאי כשל:
- ערך כשל סטנדרטי: זה מציין שלבעיה אין שום פתרון.
- ערך כשל חתך: הוא לא מגדיר פתרון לבעיה בתוך גבול עומק נתון.
יתרונות:
חיפוש מוגבל לעומק הוא יעיל בזיכרון.
חסרונות:
- לחיפוש מוגבל לעומק יש גם חסרון של חוסר שלמות.
- ייתכן שזה לא יהיה אופטימלי אם לבעיה יש יותר מפתרון אחד.
דוגמא:
שְׁלֵמוּת: אלגוריתם החיפוש של DLS הושלם אם הפתרון הוא מעל מגבלת העומק.
מורכבות זמן: מורכבות הזמן של אלגוריתם DLS היא O(בℓ) .
מורכבות החלל: מורכבות החלל של אלגוריתם DLS היא O (ב�ℓ) .
אוֹפְּטִימָלִי: ניתן לראות חיפוש מוגבל בעומק כמקרה מיוחד של DFS, והוא גם לא אופטימלי גם אם ℓ>ד.
4. אלגוריתם חיפוש בעלות אחידה:
חיפוש בעלות אחידה הוא אלגוריתם חיפוש המשמש למעבר בין עץ או גרף משוקלל. אלגוריתם זה נכנס לפעולה כאשר עלות שונה זמינה עבור כל קצה. המטרה העיקרית של החיפוש בעלות אחידה היא למצוא נתיב לצומת היעד בעל העלות המצטברת הנמוכה ביותר. חיפוש בעלות אחידה מרחיב צמתים בהתאם לעלויות הנתיב שלהם מהצומת השורש. ניתן להשתמש בו כדי לפתור כל גרף/עץ שבו העלות האופטימלית מבוקשת. אלגוריתם חיפוש בעלות אחידה מיושם על ידי תור העדיפות. זה נותן עדיפות מרבית לעלות המצטברת הנמוכה ביותר. חיפוש עלות אחיד שווה ערך לאלגוריתם BFS אם עלות הנתיב של כל הקצוות זהה.
יתרונות:
- חיפוש עלויות אחיד הוא אופטימלי מכיוון שבכל מדינה נבחר הנתיב בעל העלות הנמוכה ביותר.
חסרונות:
- לא אכפת לו ממספר השלבים הכרוכים בחיפוש והוא מודאג רק לגבי עלות הנתיב. בשל כך אלגוריתם זה עשוי להיות תקוע בלולאה אינסופית.
דוגמא:
שְׁלֵמוּת:
החיפוש בעלות אחידה הושלם, למשל אם יש פתרון, UCS תמצא אותו.
מורכבות זמן:
תן C* הוא עלות הפתרון האופטימלי , ו ה הוא כל שלב להתקרבות לצומת המטרה. אז מספר הצעדים הוא = C*/ε+1. כאן לקחנו 1+, כאשר אנחנו מתחילים ממצב 0 ומסיימים ל-C*/ε.
לפיכך, מורכבות הזמן הגרועה ביותר של חיפוש בעלויות אחידות היא O(ב1 + [C*/e])/ .
מורכבות החלל:
אותו היגיון נוגע למורכבות החלל, כך שמורכבות החלל הגרועה ביותר של חיפוש בעלות אחידה היא O(ב1 + [C*/e]) .
אוֹפְּטִימָלִי:
חיפוש בעלות אחידה הוא תמיד אופטימלי מכיוון שהוא בוחר רק נתיב עם עלות הנתיב הנמוכה ביותר.
5. העמקה איטרטיבית בעומק חיפוש ראשון:
אלגוריתם ההעמקה האיטרטיבי הוא שילוב של אלגוריתמי DFS ו-BFS. אלגוריתם החיפוש הזה מגלה את מגבלת העומק הטובה ביותר ועושה זאת על ידי הגדלת הגבול בהדרגה עד למציאת מטרה.
אלגוריתם זה מבצע חיפוש עומק ראשון עד ל'גבלת עומק' מסוימת, והוא ממשיך להגדיל את מגבלת העומק לאחר כל איטרציה עד שנמצא צומת המטרה.
אלגוריתם חיפוש זה משלב את היתרונות של החיפוש המהיר של חיפוש רוחב ראשון ויעילות הזיכרון של חיפוש עומק ראשון.
אלגוריתם החיפוש האיטרטיבי הוא חיפוש חסר מידע שימושי כאשר שטח החיפוש גדול, ועומק צומת המטרה אינו ידוע.
יתרונות:
- זה משלב את היתרונות של אלגוריתם חיפוש BFS ו-DFS במונחים של חיפוש מהיר ויעילות זיכרון.
חסרונות:
- החיסרון העיקרי של IDDFS הוא שהוא חוזר על כל העבודה של השלב הקודם.
דוגמא:
מבנה העץ הבא מציג את ההעמקה האיטרטיבית של החיפוש הראשון. אלגוריתם IDDFS מבצע איטרציות שונות עד שאינו מוצא את צומת המטרה. האיטרציה שמבצע האלגוריתם ניתנת כ:
איטרציה ראשונה-----> א
איטרציה שניה----> A, B, C
איטרציה שלישית------>A, B, D, E, C, F, G
איטרציה רביעית------>A,B,D,H,I,E,C,F,K,G
באיטרציה הרביעית, האלגוריתם ימצא את צומת המטרה.
שְׁלֵמוּת:
אלגוריתם זה הושלם אם גורם ההסתעפות הוא סופי.
מורכבות זמן:
נניח ש-b הוא גורם ההסתעפות והעומק הוא d ואז מורכבות הזמן במקרה הגרוע היא O(בד) .
מורכבות החלל:
מורכבות החלל של IDDFS תהיה O(bd) .
אוֹפְּטִימָלִי:
אלגוריתם IDDFS הוא אופטימלי אם עלות הנתיב היא פונקציה לא יורדת של עומק הצומת.
6. אלגוריתם חיפוש דו-כיווני:
אלגוריתם חיפוש דו-כיווני מריץ שני חיפושים בו-זמניים, מצב התחלתי אחד שנקרא חיפוש קדימה ואחר מצומת המטרה שנקרא חיפוש אחורה, כדי למצוא את צומת המטרה. חיפוש דו-כיווני מחליף גרף חיפוש בודד בשני תת-גרפים קטנים שבהם האחד מתחיל את החיפוש מקודקוד ראשוני והשני מתחיל מקודקוד המטרה. החיפוש נפסק כאשר שני הגרפים הללו מצטלבים זה את זה.
חיפוש דו-כיווני יכול להשתמש בטכניקות חיפוש כגון BFS, DFS, DLS וכו'.
יתרונות:
- חיפוש דו-כיווני מהיר.
- חיפוש דו-כיווני דורש פחות זיכרון
חסרונות:
- יישום עץ החיפוש הדו-כיווני קשה.
דוגמא:
בעץ החיפוש למטה, מוחל אלגוריתם חיפוש דו-כיווני. אלגוריתם זה מחלק גרף/עץ אחד לשני גרפים משנה. הוא מתחיל לעבור מצומת 1 בכיוון קדימה ומתחיל מצומת יעד 16 בכיוון אחורה.
האלגוריתם מסתיים בצומת 9 שבו שני חיפושים נפגשים.
שְׁלֵמוּת: החיפוש הדו-כיווני הושלם אם אנו משתמשים ב-BFS בשני החיפושים.
מורכבות זמן: מורכבות הזמן של חיפוש דו-כיווני באמצעות BFS היא O(בד) .
מורכבות החלל: מורכבות החלל של חיפוש דו-כיווני היא O(בד) .
אוֹפְּטִימָלִי: חיפוש דו-כיווני הוא אופטימלי.