凸包问题之蛮力解法

来自计算思维百科
跳转至: 导航搜索
凸包问题之蛮力解法.png

如果我们有n个点的集合,我们需要确定一个边界,能把所有的点包在里面。这个边界我们要求是凸的。所谓凸的就是右图中左边的那个图,在这个边界中的任意两点的连线都包含在这个边界中,反之,右边的图就不是凸的。

基本概念

凸集合:对于平面上的一个点集合,如果以集合中任意两点P、Q为端点的线段都属于该集合,则称这个集合是凸的。

凸包:对于平面上的n个点的集合,包含所有这些点的最小凸多边形。

凸包问题是一种没有明显算法解法的一个问题,但由于线段构成了凸包的边界,可以基于这个设计一个直接简单的算法,即这里将介绍的蛮力法解决。蛮力法的思想就是在任意两点之间化一条线,如果所有的点都在这条线的上面或下面,这条线就是凸包多边形的一条边。我们把所有的边都进行这种测试,留下那些测试合格的线,这些线就构成了凸包。

应用范围

凸包问题应用十分广泛,很多最优化问题可抽象为凸包问题模型;可用于人际关系网络的最小化搜索,也可用于计算机图形图像处理,边缘检测等等。

使用方法及步骤

对于含n个点的点集P,其中的点为Pk(k=1~n)。对于其中的两个点Pi、Pj,当且仅当集合中的其他点都位于穿过这两点的直线的同一边时,他们的连线是凸包边界的一部分。对集合中每一对点做如此检测,满足条件的即构成凸包的边界。

  1. 得到n个点的组合集,从第一对点开始;
  2. 判断其他点是否在两点构成的直线的一侧
  3. 若所有点在当前直线一侧,则当前两点为极点是边界的一部分,结束换下对点继续2;否则,换下一对点继续2

应用案例

应用1-如何用最短的栅栏围住n头熟睡的老虎

案例:有n头熟睡的老虎,如何尽量用最少的栅栏去把n头老虎围住,不能把老虎惊醒,即不能碰到老虎。

解决步骤:

  1. 每只老虎就是一个点,从一对老虎开始;
  2. 判断其他老虎是不是都在当前这对老虎的连线一侧
  3. 若是,则可以在当前这对老虎边钉上栅栏,下一对组合继续2;否则,下一组合继续2

应用2-如何用最低的成本去建一个果园

案例:某农夫打算建一个果园,已经种了果树,果树的价格已经确定,现在就想从篱笆上节约成本,即该怎么做,使得所有树围在篱笆里且开销最少?

解决步骤:

  1. 每棵果树就是一个点,从第一组果树开始,在果树间连上一条够长的绳子;
  2. 判断其他果树是不是在绳子的一侧;
  3. 若是,则对两棵树做标记,换另一组树继续2;若不是,则换一组树继续2;直到所有组合都检测过。

最后依据被标记的树围成的边界来建篱笆即可。

可以体现的计算思维

凸包问题在生活中和计算机很多方面都很有用,就像上面的案例就可以转化成一个凸包问题;而在这里我们给的是最直接的求解方法即按照机械式的思维,一步一步的去接近问题的答案。在此问题的解法中,体现了计算思维中的抽象特点和按部就班地机械化特点。