Message No. 147
Correctness of the structural formula at DP
Dear students,

Pay attention to the two following points relevant to the correctness proof of the structural formula at the dynamic programming approach:

1) The structural formula and its correctness are fully MATHEMATICAL issues, with no relation to algorithms and programming. Simply one value EQUALS a formula on other values, and this needs a proof.

2) You should use explicitly the fact that a part of an optimal solution is itself an optimal solution to a sub-problem, and its value is denoted by opt(…).

Yefim

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

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

published on 13/10/2014 16:02:50 by Yefim Dinitz