一种求解欧式平面TSP问题的混合算法

TSP问题是一个经典的组合优化问题。本文采用基于凸多边形的插入方法来构造路径,然后使用调整算法对路径进行调整以缩短回路长度,最后采用遗传算法中的交叉算子,再对路径进行优化。实验结果表明,该算法具有较高精度和较强实用性。     

一种凸多边形的修剪与填充算法

本文给出了一种凸多边形的填图算法,它集修剪与填充功能于一体,也可单纯完成对凸多边形的修剪任务。     

带障碍物情况下两点间最短距离的求解方法

带障碍物聚类问题的关键是求解存在障碍物情况下两点间的最短距离。针对该问题提出边缘可见点概念,给出一种解决方法,从一点依次寻找障碍物上的边缘可见点,顺次连接这些点,可以形成上边缘最短路径和下边缘最短路径,最终的最短路径是这两者中的较短者。实验结果验证了该方法的有效性。     

判定凸多边形可碰撞的最优算法

设P与Q是平面内任意二互不相交的凸多边形,d为任一给定方向,本文研究P沿d以平移方式运动可否与Q碰撞的判定问题.文中定义了凸多边形顶点集上的偏序关系,给出了判定可碰撞性的新的充分必要条件,据此采用四分搜索方法构造了判定可碰撞的算法.在最坏情况下算法的复杂度为O(logn),在不计常数因子的情况下,这是最优的.     

一种求凸多边形宽度的优化算法

提出了一种优化的线性时间算法计算凸多边形的宽度。首先证明了凸多边形的宽度只可能介于“点边式”跨度之间,缩小了宽度的计算范围。其次提出了一种距离比较算法,降低了凸多边形跨度的计算量。最后,在“点边式”基本算法和距离比较算法的基础上,提出了计算宽度的优化算法。仿真分析表明,提出的优化算法提高了计算凸多边形宽度的效率,算法的时间复杂性降为O(n)。     

中轴求凸多边形直径算法

在研究中轴性质的基础上,给出了一种全新的求解凸多边形直径算法。该算法首先求出凸多边形的中轴,再根据中轴的两个端点确定直径。算法简单,并在无预处理的情况下达到了O（n）。     

基于直线斜率的凸多边形线裁剪算法

凸多边形的线裁剪算法在计算机图形学中占据着很重要的地位,现在的许多领域均有很重要的应用。本文提出了一种非常有效的基于直线斜率的凸多边形线裁剪算法,并与Cyrus—Berk算法进行了比较。结果表明：本算法更加简单、高效。     

WSN中一种改进的节点部署方案

节点部署是无线传感器网络的基本问题之一,关系到网络的感知范围和信息传输服务质量。现有的部署算法需要额外探测和修复边界上的覆盖空洞,从而增加了网络部署的成本而且使得节点分布不均匀。针对这一问题,提出了一种改进的节点部署方案,首先进行边界部署,以保证边界上的完全覆盖和连通;然后在感应区域内生成一个新的凸多边形区域,在此新区域上再递归调用边界部署算法,直到整个感应区域被完全覆盖。理论分析和仿真实验表明,在部署节点个数和可扩展性方面均优于已有的部署方案。     

关于Catalan数的几种求法

本文通过不同的模型，给出了Ｃａｔａｌａｎ数的三种不同的求法，其中利用组合意义和生成函数两种方法都是比较巧妙的方法。     

如何编程求两凸多边形的公共面积

一、问题 2001年第7期擂台赛给出了这样一个问题:给定两凸多边形,则两凸多边形的相交部分也一定是一个凸多边形,请编程求出它们公共相交的凸多边形的面积。 (二)预备讨论 首先介绍后面要用到的几个子问题的解法。 第一,如何判断一个点是否在一个凸多边形内部?