Question

下圖是一人出差從A城出發到B城去，沿途可能經過的城市的示意圖，通過兩城市所需時間標在兩城市之間的連線上（單位:h），試求此人從A城出發到B城所需時間最少要多少小時？

Answer 1

思路分析：如果從A開始逐一計算所有可能的路線所需的時間，工作量顯然較大，且易出現遺漏.注意到最優路線圖中的某一城市必存在這樣的事實：不管前面的路線如何，從本城市出發到終點的路線耗時仍然是最短的，否則就會存在耗時更短的路線，產生與最優路線的假設相矛盾.這就啟示我們可以從終點B出發，倒溯著局部選擇耗時最短的最優路線.

解：設各城市至B城市所需時間的最短時間為S(x)，x為城市記號，則S(E₁)=12,S(E₂)=18,S(D₁)=17+S(E₁)=29,S(D₂)=min{10+S(E₁),5+S(E₂)}=22,S(D₃)=9+S(E₂)=27,S(C₁)=min{6+S(D₁),13+S(D₂)}=35,S(C₂)=min{11+S(D₂),7+S(D₃)}=33,S(A)=min{14+S(C₁),15+S(C₂)}=48.故從A城到B城所需時間最少為48 h,其最短的路線是A—C₂—D₂—E₁—B.