Bidirectional Iterative Deepening Heuristic Search

הרקע לפרויקט:

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

מטרת הפרויקט:

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

תכולת הפרויקט:

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

קורסי קדם:

- מבני נתונים
- אלגוריתמים
- תכנות - C, C#, Java, Python וכדומה

דרישות נוספות:

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

מקורות:

1. https://www.cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf
2. https://arxiv.org/pdf/1907.13062
3. https://ojs.aaai.org/index.php/AAAI/article/view/10436/10295