求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析

旅行商问题(Traveling Salesm an Prob lem,TSP)是组合优化中最典型的NP难问题之一,长期以来人们都在寻求快速高效的近似算法以在合理的计算时间内准确地解决大规模问题,并设计出许多高效实用的启发式和宏启发式算法,其中循环LK算法是性能最好和最具代表性的算法之一.作者研究了该算法的运行时间分布:通过对TSPLIB中大量不同规模的TSP实例的运行时间分布的统计分析和拟合,发现求解TSP问题的循环LK算法的运行时间分布很好地服从W e ibu ll分布,并进一步给出了该分布对求解TSP问题的物理意义.作者同时首次给出了循环LK算法求解TSP问题得到的解的性能分布以及由此得到的一些有实际指导意义的结论.

一个三维地形飞行浏览系统

采用顶点缓存技术和贴图压缩技术来提高计算机对大规模三维场景的处理速度,实现了一个三维地形飞行浏览系统,能够在微机上以自然流畅的速度实现整个淮河流域的三维地形飞行浏览。为了在飞行浏览时不致于迷失方向和位置,本系统还提供了整个淮河流域的鸟瞰图,具有用户交互和自动导航两种工作方式。

求解QAP问题的近似骨架导向快速蚁群算法(英文)

QAP(quadratic assignment problem)问题是经典的组合优化问题之一,广泛应用于许多领域中.针对QAP问题,提出了一种新的蚁群算法——近似骨架导向的快速蚁群算法(ABFANT).该算法的基本原理是通过对局部最优解的简单相交操作得到QAP问题实例的近似骨架(approximate-backbone),利用这些近似骨架可以极大地缩小QAP问题的搜索空间,而同时不降低搜索的性能,最后对这个缩小后的搜索空间,直接用当前求解QAP问题最好的启发式算法之一??快速蚁群算法(FANT)求解得到问题的解.在QAPLIB中的典型实例上的实验结果表明,近似骨架导向的快速蚁群算法明显优于快速蚁群算法.此外,指出基于近似骨架的算法思想可以很容易地被移植到其他求解QAP问题的启发式算法中.

不确定性MPI/PVM程序的完全调试(英文)

讨论如何完全地调试不确定性 MPI/ PVM并行程序 .在循环调试过程中 ,不确定性导致前次遇到的错误在以后的执行中很可能无法再现 .基于 MPI/ PVM的 FIFO通信模型 ,给出一种记录 -重放技术的实现 .通过可控制的重放 ,用户可以覆盖所有可能的程序执行路径 ,从而达到完全调试的目的 .和其它方法相比 ,所提供的方法所需时空开销要小得多 .此技术已在两种消息传递体系结构上得到实现 :一种是曙光 - 2 0 0 0超级服务器 (由国家智能计算机研究中心开发 ) ,它由单处理器 (Power PC)结点经 MESH网互联而成 ;另一种是国家高性能计算中心 (合肥 )的工作站 (Power PC/ AIX)机群系统 .

一种基于MPP的并行归并算法

文中提出并分析了并行归并算法ＰＭＦＳ（ｐａｒａｌｅｌｍｅｒｇｉｎｇｂｙｆｉｘｅｄｓａｍｐｌｉｎｇ）；基于曙光－１０００大规模并行计算机系统，给出了ＰＭＦＳ算法应用实例的实验结果，并将ＰＭＦＳ算法推广得到的并行归并排序算法与ＰＳＲＳ算法进行了比较．

一种三维地层模型的表示和生成方法

如何方便地在计算机上输入有限的地层信息，并且根据这些信息生成三维地层模型，是石油地震勘探模拟系统所要解决的问题。文章讨论了一种三维地层模型的表示和生成方法，这种方法简单有效，已经实现于“基于模型的三维地震采集方案交互设计系统（ＰＤＳＳＭ）”中，在实际应用中取得了良好的效果。

一种在无线传感器网络中构造有效连通支配集的算法

构造连通支配集是解决数据收集问题的一种较有效方法,现有算法在构造连通支配集时只考虑支配集的大小,造成支配集有效期短,易产生盲点及传输数据能耗大.针对如上缺陷,综合考虑支配集的大小、节点能量及节点到基站的路径,提出了一个基于广度优先搜索生成树的算法.模拟实验表明,该算法的系统生命期比现有算法提高20%左右,延迟缩短17%左右.

改进的八叉树数据结构

1 引言随着计算机图形学的飞速发展,三维物体的有效表示变得越来越重要,其中,八叉树表示法(octreerepresentation)以其数据结构简单、算法实现方便等特点,成为最广泛使用的三维物体的表示法之一。八叉树表示法产生于70年代末、80年代初,然而原有的八叉树数据结构存在着冗余。

二维线段裁剪的概率模型

相对于矩形窗口的二维线段裁剪是计算机图形学中的基本操作之一 ,已有多种裁剪算法 .由于这些算法在不同情况下各具优劣 ,一般只能分不同情况比较算法的性能 ,无法比较算法的平均性能 .本文首先分析了线段与窗口之间位置关系的概率分布 ,从而得到二维线段裁剪的概率模型 .接着使用该模型计算出一些常用算法的平均运算次数 ,并对算法的平均性能进行比较 .

可重构造的网孔机器上的k-选择

对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵，文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法，其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ），而对于一般的ｌ元集，文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ，该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地，当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数），则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．

如何测量SMP机群可扩放性(英文)

可扩放性是并行计算的一个重要性能标准,但是传统的可扩放性准则并不适用于SMP机群.如何测量SMP机群的可扩放性?试图提出该问题的一个解决方案.首先找出并验证问题的根源处理器集合不等价性.然后,采用处理器集合的观点来全面、正确地观察系统的行为,而并非像传统的做法那样仅仅使用处理器数来描述并行系统.通过引入性能参考因子的概念,扩展了传统的准则以适应SMP机群体系结构.实验结果显示,扩展后的度量准则适用于SMP机群,且具有较高的准确性.

CORBA服务支撑的远程协同教学环境的研究与实现

一种由CORBA服务支撑的远程协同教学环境模型及其实现,采用基于CORBA的三层分布式对象系统结构,支持Web环境下的协同教学,为用户提供了一个界面友好的协同工作环境。

异构环境下MPI程序Cache访问的单机模拟

Cache模拟工具可以在单机上模拟运行于异构环境下的并行程序的Cache访问。用户依照自己的需求指定Cache模型参数及替换算法,对每个进程中的某一段进行模拟,使并行程序中每个或每组子进程/线程分别对应一个Cache模型,从而同时得到每个或每组子进程/线程的Cache访问参数。使用单机Cache模拟环境降低了并行程序的Cache模拟对实际并行环境的依赖。同时,用户还可以很方便地在其基础上扩展并使用自行开发的替换算法或进程通信模块功能,适应了不同用户对并行程序Cache模拟工具的需要。