תרגיל שנראה לי שהוא ידוע:קלוט מבוך. פתור אותו ע"י היצמדות לימין והחזר פתרון.

אני יודע איך לקלוט אותו, ולהצמד לימין עד....שיש מבוי סתום.

איך אני יכול לחזור אחורה??

(פתרון רקןרסיבי)

אלגוריתם backtracking.

תשמור רשימה של כל המקומות במבוך שבהם כבר היית. בכל פעם, תבדוק אם יש לך מקום שאתה יכול ללכת אליו, ועדיין לא היית בו. אם כן, לך אליו. אם לא, חזור אחורה צעד אחד.

אבל איך אני אוכל לחזור אחורה!?

אתה פשוט צריך להחזיק רשימה של כל הצעדים שעשית עד עכשיו. לחזור אחורה - לחזור למקום לפי הערך האחרון ברשימה, ואז תוציא אותו מהרשימה.

המממ...

תודה רבה, אני אנסה לעשות את זה(למרות שלא צריך רשימה, זה במערך).

רשימה הייתה במובן הרחב של המילה.

הפונקציה תקבל מיקום נוכחי (i,j)

האלג:

1) אם המקום הנוכחי הוא נק' הסיום הדפס אותו והחזר 1

2) סמן משבצת נוכחית כמשבצת שביקרת בה

3) עבור כל משבצת (k,l) מסביב ל(i,j). כלומר (k,l) היא אחת מ { (i,j+1),(i,j-1),(i+1,j),(i-1,j) } --- הסדר שבו תעבור על הארבע משבצות האלו יקבע את סדר הפניות

3.1) אם (k,l) היא קיר או ביקרת בה או שהיא מחוץ למבוך אז המשך

3.2) אחרת

3.2.1) קרא באופן רקורסיבי עם (k,l)

3.2.2) אם קריאה רקורסיבית חוזרת עם ערך אחד אז

2.2.3.1) הדפס את (k,l) וחזור עם 1

4) החזר 0

נכונות: צריך להראות שאם יש פתרון האלג' ימצא אותו ושאם אין אז האלג' לא ימצא. נשאיר כתרגיל אבל כמו ברוב הריקורסיות ההוכחה באידוקציה

יעילות: גם כתרגיל אבל שים לב מה קורה בכל קריאה רקורסיבית בשלב 2