Question

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

Answer 1

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

解：設(shè)各城市至B城市所需時(shí)間的最短時(shí)間為S(x)，x為城市記號(hào)，則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城所需時(shí)間最少為48 h,其最短的路線是A—C₂—D₂—E₁—B.