נתונה קבוצה של n ערים a1,…,an ומטריצה C[i,j] עבור n≥i,j≥1 שנותנת את עלות הנסיעה הישירה מai לaj (בלי תחנות ביניים). אם אין אפשרות לנסיעה ישירה מai לaj, אז C[i,j]=∞. נרצה לבנות מטריצה D[i,j] שנותנת את עלות הנסיעה הזולה ביותר מai לaj, כאשר מותר להשתמש בתחנות ביניים (אין צורך לפרט מיהן התחנות על המסלול).
רמז: תכנות דינמי.
א. (13) הגדירו נוסחה רקורסיבית E(i,j,k) עבור n≥k≥0, n≥i,j≥1, שתחזיר את עלות הנסיעה הזולה ביותר מai לaj, כאשר מותר להשתמש בתחנות ביניים רק מתוך הקבוצה {1,2,…,k}; יש לכלול את תנאי העצירה בנוסחה.
ב. (6) הגדירו את המטריצה D שברצוננו לבנות במונחים של הנוסחה הרקורסיבית E(i,j,k).
ג. (6) מהן סיבוכיות הזמן וסיבוכיות המקום הנדרשות עבור אלגוריתם התכנות הדינמי? נמקו. שימו לב כי אין צורך לשחזר את המסלולים.