במדעי המחשב, אומרים שלבעיה יש בעיות משנה חופפות אם ניתן לפרק את הבעיה לתת-בעיות שבהן נעשה שימוש חוזר מספר פעמים או שאלגוריתם רקורסיבי לבעיה פותר את אותה תת-בעיית שוב ושוב ולא תמיד מייצר חדשות בעיות משנה.
מהן תת-מבנה אופטימלי ותתי-בעיות חופפות בתכנות דינמי?
לבעיה יש תכונת תת-מבנה אופטימלית אם ניתן להשיג פתרון אופטימלי לבעיה הנתונה על ידי שימוש בפתרון האופטימלי של בעיות המשנה שלה. תכנות דינמי מנצל את המאפיין הזה כדי למצוא פתרון.
מהי בעיית משנה חופפת בתכנות דינמי?
1) בעיות משנה חופפות:
תכנות דינמי משמשת בעיקר כאשר יש צורך בפתרונות של אותן בעיות משנה שוב ושוב. בתכנות דינמי, פתרונות מחושבים לבעיות משנה מאוחסנים בטבלה כך שאין צורך לחשב אותן מחדש.
מה ההבדל בין תת-מבנה אופטימלי לבין בעיות משנה חופפות?
אני מבין את גישת היעד עבור שתי השיטות שבהן Optimal Substructure מחשבת את הפתרון האופטימלי על סמך קלט n בעוד שבעיות משנה חפיפה ממקדות את כל הפתרונות עבור טווח הקלט למשל מ- 1 עד n.לבעיה כמו בעיית חיתוך המוט.
איזו מהטכניקות האלה משתמשת בחפיפה של בעיות משנה?
תכנות דינמי היא טכניקה לפתרון בעיות עם בעיות משנה חופפות. בכך, אנו מאחסנים את התוצאה של הבעיה המשנה שנפתרה פעם אחת לשימוש חוזר עתידי. הטכניקה של אחסון פתרונות משנה לבעיות נקראת זיכרון.
