趣谈模拟计算机和表决算法
Author: 宁波 陈剑波 Date: 1996-12-20
用一张坐标纸代替城市地图，方格线代表城市道路，交叉点代表路口，任取三个交叉点代表你的三个朋友的住处，现在你如何选择一个最佳的住处，使得你与三个朋友住处的距离之和为最短(沿方格线行走)”有一个称之为“表决算法”的好方法可以帮你很快找到这一点：先任意取一个看上去比较合理的点，然后尝试从这一点移动到下一点，让三个朋友投票表决，认为你离他更近的朋友投“赞成”，认为更远的投“反对”，如果“赞成”票多于“反对”票，则这个移动是对的，而当“反对”票占多数时，你就应该尝试往另外一个方向移动，如此移动，直到最后有一路口使得你向任何方向移动都将遭到大多数人的反对，因此，这最后的路口就是你最佳的住处。比这更为一般的问题是：给定平面上任意几个点的位置，如何找到最佳点使该点到其它所有各点的直线距离之和为最短?这个问题显然与第一个问题不同，这里没有预先设定的路线，因此上述表决算法就不再适用。但是我们可以借助于一种模拟计算机来求解，这种模拟计算机其实是这样一种机械装置：用桌面代替平面，在桌面上按比例定好这几个点的位置，然后在每一点下面钻一个孔，拿一些细绳穿过这些孔，细绳下悬挂着同样重的物体，细绳的上端都系在一起，放手后，这个模拟计算机就会给出问题的答案：细绳结头最终稳定下来停留的位置就是最佳的点的位置!这里，同样重的几个物体好比几张有着同等权力的“表决票”，最佳的地点得由它们决定。更进一步，如果每一点的权重不一样，比如A点有10个学生，B点有20个学生，C点有30个学生，这60个学生到某个地方去上学，要使他们所走过的路的直线距离之和为最小(假设可以沿着两点之间的直线行走)，如何确定这个校址?用上述的模拟计算机同样能够很快地“算出”答案，只要使每一个点下面悬挂的物体的重量正比于该点的人数即可。理论上，这个模拟计算机是很高效的，但在实际中，多于三个点的话，由于摩擦阻力损耗的原因，这个简陋的系统将不能很有效地工作，实际应用的模拟计算机比这个要复杂的多。然而如果由数字计算机通过编程来求解这类问题，恐怕是相当繁琐而低效的。
(宁波 陈剑波)