几何问题中的离治法

4.5几何问题中的离治法4.5.1最近对问题

4.5.2凸包问题4.5.1最近对问题

设p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。严格地讲，最接近点对可能多于一对，简单起见，只找出其中的一对作为问题的解。

用离治法解决最近对问题，很自然的想法就是将集合S分成两个子集S1和S2，每个子集中有n/2个点。然后在每个子集中途归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合S中最接近的两个点都在子集S1或S2中，则问题很容易解决，如果这两个点分别在S1和S2中，问题就比较复杂了。为了使问题易于理解，先考虑一维的情形。此时，S中的点退化为x轴上的n个点x1,x2,…,xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数相同。途归地在S1和S2上求出最接近点对(p1,p2)和(q1,q2)，如果集合S中的最接近点对都在子集S1或S2中，则d=min{(p1,p2),(q1,q2)}即为所求，如果集合S中的最接近点对分别在S1和S2中，则一定是(p3,q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。为了使问题易于理解，先考虑一维的情形。此时，S中的点退化为x轴上的n个点x1,x2,…,xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数相同。途归地在S1和S2上求出最接近点对(p1,p2)和(q1,q2)，如果集合S中的最接近点对都在子集S1或S2中，则d=min{(p1,p2),(q1,q2)}即为所求，如果集合S中的最接近点对分别在S1和S2中，则一定是(p3,q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。按这种离治策略求解最近对问题的算法效率取决于划分点m的选取，一个基本的要求是要遵循平衡子问题的原则。如果选取m=(max{S}+min{S})/2，则有可能因集合S中点分布的不均匀而造成子集S1和S2的不平衡，如果用S中各点坐标的中位数（即S的中值）作为分割点，则会得到一个平衡的分割点m，使得子集S1和S2中有个数大致相同的点。下面考虑二维的情形，此时S中的点为平面上的点。为了将平面上的点集S分割为点的个数大致相同的两个子集S1和S2，选取垂直线x=m来作为分割线，其中，m为S中各点x坐标的中位数。由此将S分割为S1={p∈S|xp≤m}和S2={q∈S|xq＞m}。途归地在S1和S2上求解最近对问题，分别得到S1中的最近距离d1和S2中的最近距离d2，令d=min(d1,d2)，若S的最近对(p,q)之间的距离小于d，则p和q必分属于S1和S2，不妨设p∈S1，q∈S2，则p和q距直线x=m的距离均小于d，所以，可以将求解限制在以x=m为中心、宽度为2d的垂直带P1和P2中，垂直带之外的任何点对之间的距离都一定大于d。

4.5.2凸包问题

设p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n个点构成的集合S，并且这些点按照x轴坐标升序排列。几何学中有这样一个明显的事实：最左边的点p1和最右边的点pn一定是该集合的凸包顶点（即极点）。设p1pn是从p1到pn的直线，这条直线把集合S分成两个子集：S1是位于直线左侧和直线上的点构成的集合，S2是位于直线右侧和直线上的点构成的集合。S1的凸包由下列线段构成：以p1和pn为端点的线段构成的下边界，以及由多条线段构成的上边界，这条上边界称为上包。类似地，S2中的多条线段构成的下边界称为下包。整个集合S的凸包是由上包和下包构成的。

p1pmaxpn快包的思想是：首先找到S1中的顶点pmax，它是距离直线p1pn最远的顶点，则三角形pmaxp1pn的面积最大。S1中所有在直线pmaxp1左侧的点构成集合S1,1，S1中所有在直线pmaxpn右侧的点构成集合S1,2，包含在三角形pmaxp1pn之中的点可以不考虑了。途归地继续构造集合S1,1的上包和集合S1,2的上包，然后将求解过程中得到的所有最远距离的点连接起来，就可以得到集合S1的上包。接下来的问题是如何判断一个点是否在给定直线的左侧（或右侧）？几何学中有这样一个定理：如果p1=(x1,y1),p2=(x2,y2),p3=(x3,y3)是平面上的任意三个点，则三角形p1p2p3的面积等于下面这个行列式的绝对值的一半：当且仅当点p3=(x3,y3)位于直线p1p2的左侧时，该式的符号为正。可以在一个常数时间内检查一个点是否位于两个点确定的直线的左侧，并且可以求得这个点到该直线的距离。311223321321332211111yxyxyxyxyxyxyxyxyx---++=蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

为什么小小的蚂蚁能够找到食物？他们具有智能么？如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物；其次，需要让他们遍历空间上的所有点；再次，计算所有可能的路径并且比较它们的大小；你要小心翼翼的编程，这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时，该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等，显示了其适用于组合优化类问题求解的优越特征。多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发，该算法现己被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通等领域。美国五角大楼正在资助关于群智能系统的研究工作-群体战略(SwarmStrategy)，它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力，让自己的军队在敌人后方不被察觉地安全进行。英国电信