|
|
עמוד:8
f ( s ) = Min { C + f _ * ( j ) } n = 1 , 2 , 3 , 4 sj n " העלות האופטי- עלות ( sj ) מלית שנמצאים מעבר קעותות בעיר j ונותרו מעיר s ברשת עוד -1וו שלבים לעיר נ ליעד נוסחה זו אומרת , שעל הסוכן הנוסע לבחון בכל מצב שהוא נמצא את העלות למעבר לעיר מסויימת במדינה הבאה פלוס העלות האופטימלית מאותה עיר עד ליעד , ו לעבור לאותה עיר הנותנת סה"כ עלות מינימלית . בעייתו הכללית תיפתר עם מציאת , f d ) היות וזו בדיוק העלות ^ המינימלית הכוללת שהוא נמצא בעיר מספר , 1 דהיינו עיר המוצא , ונותרו לו עוד 4 שלבים לעבור עד שיגיע ליעדו . תהליך החישוב בתהליך החישוב של בעיות בתכנות דינמי מסוג זה אנו נעזרים בטבלאות עבור כל שלב . ( n = 1 , 2 , 3 , 4 ) n צורת הטבלה היא כדלקמן : עבור כל מצב אפשרי בשלב מסויים קיימת שורה , בעוד שכל עמודה מיצגת אפשרות החלטה . בדוגמא שלנו כל עמודה תייצג עיר , שאליה ניתן לעבור בשלב הבא , מהעיר בה אנו נמצאים בשלב זה . שתי העמודות האחרונות תייצגנה את ההחלטה האופטימלית עבור כל מצב ואת העלות האופטימלית , הנובעת מההחלטה האופטימלית בשלב מסויים ובמצב מסויים . עבור ח-1 , דהיינו שנותר עוד שלב אחד לסוף , קיימות שתי שורות - עבור מצבים , 9 - ו 8 וקיימת עמודה אחת , עבור מצב ( עיר ) , 10 היות ומערים 9 - ו 8 ניתן לעבור רק לעיר . 10 המספרים בתוך כל טבלה מייצגים את הסכום של העלות המיידית , C לעבור מעיר s לעיר , j פלוס העלות האופטימלית f * _ , ( j ) להגיע ב -1 - וו השלבים הבאים מעיר j ליעד . בכל שורה אנו בוחנים מספרים אלו ומסמנים בשתי העמודות האחרונות , מהי
|
|