Question

【題目】小軍每天堅(jiān)持步行上學(xué)，下圖是小軍家A到學(xué)校B的路線圖，每段路上的數(shù)字是小軍走這段路所需的分鐘數(shù)，請幫小軍設(shè)計(jì)一條到校的耗時(shí)最少路線？

Answer 1

【答案】線路一：A—C—D—E—B，耗時(shí)9+4+7+12=32(分)；

線路二：A—C—F—E—B，耗時(shí)9+8+3+12=32(分)；

線路三：A—C—F—I—B，耗時(shí)9+8+7+7=31(分)；

線路四：A—G—F—I—B，耗時(shí)8+10+7+7=32(分)；

線路五：A—G—F—E—B，耗時(shí)8+10+3+12=33(分)；

線路六：A—G—H—I—B，耗時(shí)8+3+15+7=33(分)。

故耗時(shí)最少的路線為：A—C—F—I—B，共需時(shí)31(分)。

【解析】當(dāng)方案有限時(shí)，枚舉是找到最優(yōu)方案的有效途徑。枚舉也要進(jìn)行必要的分析，在盡可能小的范圍內(nèi)枚舉，少做無用功。

要從A到B，一定要走AG或AC，IB或EB，中間還有D、F、H三個(gè)中轉(zhuǎn)點(diǎn)。要耗時(shí)最少，就要少走彎路(不走四邊形中的三邊)，這里不走彎路的線路共有6條，列出并計(jì)算所需的時(shí)間，再加以比較即可得最佳路線。