Tip:
Highlight text to annotate it
X
כאן ניתן לכם את ההסבר למה
פונקציה האוריסטית אופטימית, h, מוצאת את את המסלול הזול ביותר.
כשA מסיים, הוא מחזיר את המסלול p עם עלות מוערכת c.
מסתבר שc הוא גם העלות האמיתי של אותו מסלול
בגלל שבמצב המטרה הרכיב h הוא 0,
אז מה שהפונקציה בעצם מעריכה הוא רק העלות הכוללת של המסלול.
עכשיו, לכל המסלולים שבחזית
יש עלות מוערכת שהיא גדולה יותר מc
ואנחנו יודעים זאת בגלל שהסדר בו החזית נבחנת הוא מהזול ליקר.
אם h אופטימית, אז העלות המוערכת
היא פחותה מהעלות האמיתית,
כך שהמסלול p חייב להיות עם עלות קטנה יותר מאשר המחיר האמיתי
של כל אחת מהעלויות של המסלולים האחרים בחזית.
כל מסלול שממשיך מעבר לחזית
חייב להיות עם עלות גדולה יותר
בגלל ההנחה שכל צעד הוא עם עלות 0 או יותר.
זה אומר ש המסלול p חייב להיות המסלול עם העלות המינימלית.
הטיעון הזה, יש לציין, תקף רק
לגבי חיפושי עץ.
עבור חיפושים גרפיים הטיעון קצת מורכב יותר,
אבל ההסבר הכללי עובד באותה צורה.