שיחה:תכנון דינמי

השאלה אם לבחור ב"תכנות" או "תכנון" (גם כאן וגם בתכנון לינארי) היא עתיקת יומין. לטעמי, עדיף להשתמש ב"תכנון", משתי סיבות עיקריות: הראשונה, שבאמת מה שנעשה כאן הוא תכנון ולא בדיוק תכנות, במובנים שבהם יש למילים אלו משמעות בעברית, והשני, שכך בחרה האוניברסיטה הפתוחה בתרגום של "מבוא לאלגוריתמים" של קורמן, לייזרסון וריבסט, ואני נוטה לראות בספר (הרציני למדי) הזה מקור טוב לבדיקת תרגומים. כמובן ש"תכנות דינאמי" צריך להיות דף הפניה לכאן. גדי אלכסנדרוביץ' 07:29, 29 אפר' 2005 (UTC)

הפרד ומשול

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

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

חוץ מזה, יש לי בעיית לטך בדוגמא לחישוב בלתי יעיל של (fib(n. מסיבה כלשהי, החצי השמאלי של ה"נוסחא" לא נראה בדף. יובל מדר 13:37, 1 יולי 2005 (UTC)

אני חושב שהבדל מהותי, שהופך את התכנון הדינמי ליוצא דופן, הוא העובדה כל תת בעיה עשוייה להיפתר מספר רב של פעמים, אפילו אקספוננציאלי, ועל ידי זה שאנחנו לא מחשבים שוב ושוב את אותו דבר אלא זוכרים אותו בצד אנחנו מאפשרים לפתרון להיות פולינומיאלי. זה בהחלט לא משהו שמוצאים באלגוריתמי הפרד ומשול בסיסיים. גדי אלכסנדרוביץ' 13:54, 1 יולי 2005 (UTC)

אני רואה שכבר תיקנת את הערך בהתאם... עבודה יפה. גדי אלכסנדרוביץ' 13:58, 1 יולי 2005 (UTC)

שיניתי רק כמה חלקים מהערך, על מנת להבהיר יותר את ההבדל בין השיטות. אבל את המשפט הראשון (המבדיל בין שיטת הפרד ומשול לתכנון הדינמי) לא שיניתי.

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

ומה בנוגע לבעית הלטך? יש לך מושג איך ניתן לטפל בה? (אתה רואה את הבעיה, בכלל?) יובל מדר

הבעיה היחידה שאני רואה היא שכתבת את סימן השווה פעמיים. אם תשאל אותי, להראות חישוב של פיבונאצ'י 6 זה יותר מדי ומספיק 5 כדי להבין את הרעיון בלי להציף במספרים שלאף אחד אין חשק לקרוא. אולי אחרי שתשנה את זה, הבעיה תסתדר. בקשר לשינוי השורה הפותחת, אני נוטה להסכים. נכון יותר לכתוב "שיטת הפרד ומשול נאיבית" או משהו דומה. גדי אלכסנדרוביץ' 15:25, 1 יולי 2005 (UTC)

שאלה

האם יש קשר בין תכנון דינמי במדעי המחשב, המתואר כאן, ובין תכנון דינמי בחקר ביצועים, או שיש לפריד לשני ערכים עם דף פירושונים? דוד שי 18:51, 14 נובמבר 2005 (UTC)

אני חושש שאני לא מסוגל לענות על השאלה הזו לבדי. מישהו שמבין בחקר ביצועים יצטרך להסביר מה פירוש "תכנון דינמי" עבורם. גדי אלכסנדרוביץ' 19:44, 14 נובמבר 2005 (UTC)

למיטב הבנתי ובזהירות המתחייבת, המונח המקובל: dynamic programming (תכנות דינמי או תכנון דינמי) מתייחס לדיסציפלינה אחת, היא המתוארת בערך זה. אין חלוקה בין המונח בהתייחס לחקר ביצועים לבין המונח בהתייחס למדע המחשב. חד הם. דני גולדמן - שיחה 15:05, 16 באפריל 2013 (IDT)

לא מדויק

"פותרים את הבעיה על ידי פתרון כל תתי הבעיות - ממקרי הקצה שהפתרונות שלהם ידועים מראש "כלפי מעלה" - עד שמגיעים לבעיה המקורית".

זה ממש לא הכרחי. אפשר פשוט להוסיף לפתרון קוד שאומר שברגע שבו נפתרה תת בעיה כלשהי, שומרים את הפתרון בטבלה. אין הכרח להתחיל "מלמטה" (בפועל אפשר לקחת קוד "למעלה למטה" קיים ולהוסיף לו שתיים-שלוש שורות שישמרו את המידע, מבלי לשנות את יתר הקוד). גדי אלכסנדרוביץ' - שיחה 14:46, 19 בספטמבר 2009 (IDT)

הצעת שיפור

על הכיפאק. אולי כדאי להוסיף גם את הדוגמה של ה knapsack עם ערכים שלמים. הודעה זו נכתבה באמצעות מערכת המשוב. 
84.229.160.37 01:34, 8 בדצמבר 2011 (IST)

לא ידעתי שprogramming בעברית זה "תכנון"

תמיד ידעתי שאני בתור איש מדעי המחשב יותר חזק במתמטיקה מאשר בלשון, אבל מאז ומעולם הייתי בטוח שprogramming זה "תכנות" ולא "תכנון" שנרים טלפון לאבשלום קור? ―אנונימי לא חתםמש:אנונימי ‌ 00:00, 10 בינואר 2000 (IST)

שווה להוסיף את הפסקה מוויקיפדיה האנגלית שמתארת את מקור המילה - ״תכנון״ כמו תכנון לוגיסטי. המילה ״תכנות״ היא אחד התרגומים של המילה הזאת. המובנים האלה קרובים, מן הסתם. --87.69.114.251 16:38, 4 בפברואר 2019 (IST)

משוב מ-29 בדצמבר 2018

מוסבר טוב