过桥问题之——信使模型

作者:jcmp      发布时间:2021-06-09      浏览量:0
最近看动态规划,发现经典的过桥问题,描述

最近看动态规划,发现经典的过桥问题,描述如下: 【例题1】在一个夜黑风高的晚上,有n(n <= 50)个小朋友在桥的这边,现在他们需要过桥,但是由于桥很窄,每次只允许不大于两人通过,他们只有一个手电筒,所以每次过桥的两个人需要把手电筒带回来,i号小朋友过桥的时间为T[i],两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

*解法解析(摘引)

每次过桥的时候最多两个人,如果桥这边还有人,那么还得回来一个人(送手电筒),也就是说N个人过桥的次数为2*N-3(倒推,当桥这边只剩两个人时只需要一次,三个人的情况为来回一次后加上两个人的情况…)。有一个人需要来回跑,将手电筒送回来(也许不是同一个人,realy?!)这个回来的时间是没办法省去的,并且回来的次数也是确定的,为N-2,如果是我,我会选择让跑的最快的人来干这件事情,但是我错了…如果总是跑得最快的人跑回来的话,那么他在每次别人过桥的时候一定得跟过去,于是就变成就是很简单的问题了,花费的总时间:

T = minPTime * (N-2) + (totalSum-minPTime)。

来看一组数据 四个人过桥花费的时间分别为 1 2 5 10,按照上面的公式答案是19,但是实际答案应该是17。

具体步骤是这样的:

使用传统动态规划方法,可以参考 https://blog.csdn.net/u013309870/article/details/75193592。

一、思考:

通过上面的分析,其实这个问题可以这么理解,由于每次过桥必须有人陪同,那么陪同的人当然是时间越短越好,假设每个人过桥时间排序之后,最短的两个为a1,a2。 为了节约时间,我假设需要有个拿手电筒的信使,用来帮助将手电筒送回,这也很容易理解,为了尽量减少返程送手电筒的时间。那么我们就可以这么处理: 假设a1为主人(安排全局,因为他最快),a2就是a1主人养的信使,专门用来送手电筒,好了,下面介绍过程:

那么假设时间为 a1, a2, a3, a4,总时间为 (a2+a1)+(a4+a2)+(a2 + 0),本题中,带入时间为(1+2)+(2+10)+(2+0)=17。

如果人数为奇数,时间为a1, a2, a3, a4,a5,总时间为 (a2+a1)+(a2+a4)+(a2 + a1)+(a5+0)。