למה להשתש במימוזציה?

למה להשתש במימוזציה?

עומר סבאח (guest) 10 Dec 2015 10:34

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

Ariel (guest) 10 Dec 2015 20:09

Hi,

Let's observe the following list: 1,2,3,4.
Our possible routes are: 1->2->3->4, 1->4, 1->2->4, 1->3->4. Thus we will compute in our naive recursion solution 3->4 twice, meaning we will initialize 2 recursive functions rather than just one.

From the lectures we may recall the following:
"For this reason, we will also introduce techniques to get rid of recursion…"
"This is highly wasteful and causes a huge overhead." (computing values over and over)
"The technique of storing values instead of re-computing them has different names in different contexts: It is known as memorization…"

Furthermore, from Wikipedia:
"n computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again."