תכנות דינמי, את העקרונות הבסיסיים

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

השיטה

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

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

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

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

השיטה משפרת את הביצועים של משימות להיפתר באמצעות גרסאות, או רקורסיה.

אלגוריתם משימת בניין

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

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

שיטת היישום

תכנות דינמי מוחל כאשר יש שתי תכונות אופייניות:

• אופטימלי עבור משימות משנה;
• נוכחות בעיית חופפים subproblems.

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

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

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