博文
四人过桥问题
|||
两座山中间有一座桥，桥下面是一条很深的峡谷。现在有甲乙丙丁四个人想在夜晚过桥，单独过桥的时间分别是8分钟、5分钟、2分钟、1分钟，只有一个手电筒，桥很窄，每次只能容许两人通过，问最快多长时间能全部过去。大多数人乍一看，丁走的最快，所以该让他多跑，于是就出来了方案1，T1=8+5+2+1*2=17分钟。甲和丁一起过需要8分钟，对于甲来讲没有什么，可是对于丁来讲是资源的极大浪费，也就是最快的和最慢的一起，这显然不合理。所以应该让最快的两个分到一组先过，最慢的两个分到一组后过，丙和丁分别回来送手电筒，最后一起过，于是出来了方案2，T2=2+1+8+2+2=15分钟。显然T2<T1。这样保证每组的特征距离最小，即Ta-Td>Ta-Tb，所以方案2要优于方案1。也就是俗话说的“物以类聚，人以群分”，专业说法叫“高内聚、低耦合”。这不是分类的最好例子？看似是一个运筹的问题，实则是一个分类的问题，当然更确切的说法是无指导分类或称之为聚类。
注：文字描述中的甲乙丙丁对应着图中的ABCD。
https://m.sciencenet.cn/blog-91591-43917.html
上一篇：国内外知识抽取研究进展综述
下一篇：同年同师谓之何？
