整理道路與時間
整理道路與行車時間
先確認任務的要求,再把表中的聯絡道路與時間列出來,看清楚每一站能從哪裡到達。
任務要求從 $A$ 站出發,最後停留在 $E$ 站,且 $B, C, D, E$ 每一站至少經過一次,路線可以重複。
由表格,聯絡道路與所需時間為:
$A\leftrightarrow B$ 需 $1$ 小時,$A\leftrightarrow C$ 需 $1$ 小時,$A\leftrightarrow D$ 需 $2$ 小時,$B\leftrightarrow E$ 需 $5$ 小時,$C\leftrightarrow D$ 需 $1$ 小時,$C\leftrightarrow E$ 需 $1$ 小時,$D\leftrightarrow E$ 需 $1$ 小時。
特別注意:與 $B$ 相連的道路只有 $A\leftrightarrow B$($1$ 小時)與 $B\leftrightarrow E$($5$ 小時)。
規劃路線
規劃一條 $5$ 小時的路線
要讓總時間最少,就盡量使用時間短的道路。
規劃路線:
$$A\xrightarrow{1} B\xrightarrow{1} A\xrightarrow{1} C\xrightarrow{1} D\xrightarrow{1} E$$
此路線經過所有站點 $A, B, C, D, E$,且終點為 $E$,總時間為
$$1+1+1+1+1=5\text{ 小時}$$
證明時間下界
說明不可能少於 $5$ 小時
每條道路至少要 $1$ 小時,所以只要說明至少要走 $5$ 段路即可。
除了出發的 $A$ 之外,還要到達 $B, C, D, E$ 四站,所以至少要走 $4$ 段路。
若恰好走 $4$ 段路,則 $B, C, D$ 各只經過一次,且 $B$ 在路線中間,前後兩站都必須與 $B$ 相連,也就是只能是 $A$ 或 $E$。但 $A$ 只在起點出現、$E$ 只在終點出現,$B$ 前後兩站不可能都是 $A$ 或 $E$,矛盾。
例如先走 $A\to C\to D\to E$ 再返回去 $B$,因為 $B$ 只能從 $A$($1$ 小時)或 $E$($5$ 小時)到達,需要額外的往返時間,總時間必定超過 $5$ 小時。
因此至少要走 $5$ 段路,每段至少 $1$ 小時,總時間至少 $5$ 小時;而上面的路線恰好 $5$ 小時,所以最少要花 $5$ 小時,故選 (2)。