247 resultados para K-connectivity
Resumo:
最优路径问题是计算机科学、运筹学、工程设计等领域很多问题的基础。它的应用包括网络路由、电路设计、交通运输、机器人运动规划、事务调度中关键路径的计算以及VLSI设计等。同时，它也为很多最优化问题提供了解决框架，如背包问题、分子生物学中的序列比对、内接多边形的构造和长度受限的霍夫曼编码等都可以转化成最优路径问题进行求解。 求解网络中最优路径的方法可以分为两大类。一种是标号设定算法（label setting ,LS）,另一种是标号改变算法（label correcting ,LC）。由于网络路径算法的应用越来越强调动态性和及时性，使得高效求解最优路径问题变得越来越重要。在这里，我们利用一种高效的网络划分方法，实现了基于网络划分的LS/LC并行算法。实验结果表明，基于这种网络划分的并行算法对于求解最优路径有很好的加速比和扩展比。 在许多更加复杂的应用中，不仅要求计算出最优路径，而且要求给出前K优路径。K优路径是长期研究的泛化最优路径问题，即不但要求得到最优路径，还要得到次短、再次短等路径。 节点s到节点t的K优路径问题可以分为两大类：一类是求解K优非简单路径，即得到的路径可以包含环路；另一类是求解K优简单路径，即路径是简单通路，不包含环路。经过大量学者的研究，求解K优非简单路径相对容易。Fox 于1975年提出了复杂度为O(m+nlogn) 的求解K优非简单路径的算法，最近， Eppstein于1998年给出了一种优化的求解K优非简单路径的算法，时间复杂度达到了O(m+nlogn+k) ，基本上达到了理论下限。 在2000年对E 的算法进行并行化，时间复杂度为 。求解K优简单路径已被证明是更为具有挑战性，这个问题最先由Hofman和Pavley 在1957年进行开始研究，但几乎所有试图解决该问题的算法时间复杂度都达到指数时间。众所周知，Yen提出了一结果比较好的算法，利用现代的数据结构达到O(kn(n+nlogn)) 时间复杂度。John Hershberger于2007年给出了一个新的求K优路径的算法，该算法基于有效率的替代路径算法,相对于以前的替代路径算法，其加速比可达到O(n) 。在本文中，我们基于John Hershberger给出的K优路径算法，尝试给出其并行的方法，并在SMP的高性能计算机上进行了测试。 关键词 并行算法、最优路径、K优路径、网络划分
Resumo:
完整性是数据质量的一个重要维度,由于数据本身固有的不确定性、采集的随机性及不准确性,导致现实应用中产生了大量具有如下特点的数据集:1)数据规模庞大;2)数据往往是不完整、不准确的.因此将大规模数据集分段到不同的数据窗口中处理是数据处理的重要方法,但缺失数据估算的相关研究大都忽视了数据集的特点和窗口的应用,而且回定大小的数据窗17容易造成算法的准确性和性能受窗口大小及窗口内数据值分布的影响.假设数据满足一定的领域相关的约束,首先提出了一种新的基于时间的动态自适应数据窗口检测算法,并基于此窗口提出了一种改进的模糊k-均值聚类算法来进行不完整数据的缺失数据估算.实验表明较之其他算法,不仅能更适应数据集的特点,具有较好的性能,而且能够保证准确性.
Resumo:
Tianjin University of Technology
