过桥问题是统筹规划问题中的一种,合理安排进程使所需时间最少的问题,类型是几个人想要过桥,分别需要不同的时间.因为天黑,必须借助于手电筒过桥,可是他们总共只有一个手电筒,并且桥的载重能力有限,每次最多过两个人.怎样安排过桥顺序,使过桥时间最短的问题.
甲、乙、丙、丁四个人过桥,分别需要1分钟,2分钟,5分钟,10分钟.因为天黑,必须借助于手电筒过桥,可是他们总共只有一个手电筒,并且桥的载重能力有限,最多只能承受两个人的重量,也就是说,每次最多过两个人.现在希望可以用最短的时间过桥,怎样才能做到最短呢?你来帮他们安排一下吧.最短时间是多少分钟呢?
解决这类问题需要注意三点要求
1、所需时间相近的人分一组;
2、让速度快的人承担往返送手电筒的任务;
3、所需时间少的一组先过桥,再分别回来送手电筒.
如例题中,让甲、乙搭配,丙、丁搭配比较节省时间.让甲和乙先过桥,用时2分钟,再由甲返回送手电筒,需要1分钟,然后丙、丁搭配过桥,用时10分钟.接下来乙返回,送手电筒,用时2分钟,再和甲一起过桥,又用时2分钟.所以花费的总时间为:2+1+10+2+2=17分钟.