|
|
עמוד:7
הסוכן הנוסע בחן את בעייתו וקיבל את עיקרון האופטימליות של התכנות הדינמי הטוען : למדיניות אופטימלית חייבת להיות התכו נה הבאה : ללא תלות בדרך שנקטנו בה , אשר הביאה אותנו למצב מסויים , ההחלטות הנותרות חייבות ליצור מדיניות אופטימלית ממצב זה והלאה . ומכאן שהוא ידע , שדרך אופטימלית ליציאה מעיר מספר 6 לא תלויה בדרך שבה הוא הגיע לעיר , 6 ויתר על כן באם הוא היה יודע דרכים אופטימליות ליציאה מערים מספר , 7 - ו 6 , 5 אזי הוא יכול לחשב העלויות בקלות דרך __ יציאה C _ , , אופטימלית ו C __ - לעלויות מעיר מספר האופטימליות , 3 ו זאת , על הידועות ידי חיבור לגבי ערים , 7 - ו , 6 , 5 ובחירת העלות המינימלית מבין שלושתן . בעזרת עיקרון האופטימליות של התכנות הדינמי ודרך פיתרון זו ניתן לפתור את הבעיה הכוללת נגדיר : - f ( s ) עלות מינימלית כאשר אנו במצב s ( בעיר s בדוגמא שלנו ) ועלינו לעבור עוד n ) wriv n מדינות בדוגמא שלנו , ( עד ליעד . nuVnnn x ( s ) בשלב ה -וו הנותנת תוצאה של . f ( s ) הסוכן , לאחר שהגדיר גדלים אלו , יו < וה מיד כי : ( f ( 10 ) = 0 היות ובהימצאו בעיר מספר , 10 אין לו יותר שלבים o לעבור . עצור , ^( 10 ) = היות והוא הגיע ליעדו . באותה צורה הוא יכול לחשב את , f ( 9 ) - ו f ( 8 ) היות והם בדיוק f ( 10 ) פלוס . nnNiini CQ ,. ? 1 C . .. באופן דומה הוא 0 את 9 , 10 8 , 10 יכול לחשב , ^( 6 ) לאחר ידיעת ^( 9 ) - ו ^( 8 ) וכן הלאה . ניתן להציג שיטת חישוב זו על ידי הנוסחה הדקורטיבית טל תכנות דינמי .
|
|