扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最短路径中等
单选题
2017年5月第41题
收藏
分享
#数学与经济管理
#最短路径
#凯恩建议了解即可
#教材之外（超纲）
加工某种零件需要依次经过毛坯、机加工、热处理和检验四道工序。各道工序有多种方案可选，对应不同的费用。下图表明了四道工序各种可选方案（连线）的衔接关系，线旁的数字表示该工序加工一个零件所需的费用（单位：元）。从该图可以推算出， 加工一个零件的总费用至少需要（__）元。
问题（1）
正确答案B
凯恩解析
本题考察的是最短路径（分层图/用Dijkstra或动态规划） 的求解方法。
思路是自左向右逐层累计最小费用，直到终点I。
起点A到各中间点的最小费用：到B为50，到C为40。
到机加工层：到D=min(50+30, 40+40)=80；到E=min(50+40, 40+60)=90；到F=min(50+40, 40+40)=80。
到热处理层：到G=min(80+40, 90+20, 80+40)=110（经E最优）；到H=min(80+50, 90+40, 80+50)=130。
到终点I：min(110+20, 130+10)=130。
因此最短路径可为A→B→E→G→I，总费用50+40+20+20=130元。
因此，最小总费用为130元。