בתשובה ליובל נוב, 14/01/22 8:55
מי האיש הכי לא משפיע בהיסטוריה שכולנו מכירים? 745583
זה נכון. אבל יש לך דוגמא לאלגוריתם תכנון דינמי שהוא לא "שימוש טריוויאלי של תכנון דינמי"?

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

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

ואם זה מה שאתה חושב על נידלמן-וונש, אני תוהה מה יש לך לומר על backpropagation (:
מי האיש הכי לא משפיע בהיסטוריה שכולנו מכירים? 745585
>> יש לך דוגמא לאלגוריתם תכנון דינמי שהוא לא "שימוש טריוויאלי של תכנון דינמי"?

שאלה טובה. לפני עשרים שנה (אללי!) לקחתי במסגרת הדוקטורט קורס שרובו היה על תכנות‏1 דינמי. אני לא זוכר משם הרבה, אבל כן זוכר שהיו מקרים שאחרי שרושמים את משוואות בלמן, אפשר להוכיח כל מיני תוצאות על המבנה של הפתרון האופטימלי, וההוכחות היו לפעמים לא טריוויאליות.

כמובן שאני לא מתנגד לשימושים טריוויאליים בתכנות דינמי, ב-alignment או בתחומים אחרים. גם אם היה צריך תובנה יחסית עמוקה כדי לבחור ב-DP בשביל alignment, זה קצת צורם בעיניי לקרוא לשורה התחתונה של הגישה הזאת "אלגוריתם נידלמן וונש".
_____________
1. תכנות או תכנון? אני נצמד לגירסא דינקותא שלי מהטכניון.

חזרה לעמוד הראשי המאמר המלא

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