A new polynomial algorithm for a parallelidentical scheduling problem

A precedence order is defined based on the release dates of jobs＇ direct successors. Using the defined precedence order and Heap Sort, a new polynomial algorithm is provided which aims to solve the parallel scheduling problem P｜pj = 1, r j, outtree｜ ∑Cj Cj. The new algorithm is shown to be more compact and easier to implement.

Heap Sorting Based on Array Sorting

A kind of heap sorting method based on array sorting was proposed. Some advantages and disadvantages of it were discussed. It was compared with the traditional method of direct application. In the method, the ordered keywords in the array are put into the heap one by one after building an empty heap. This method needs relatively less space and is fit for ordered sequence.

树状结构在数据流求均值中的应用

数据采集过程中,随着数据的增加,数据的平均值持续发生变化。为了研究平均值的变化过程,分析平均值序列的计算方法是有必要的。传统的方法是使用线性顺序存储方式计算均值序列,总的时间复杂度高达O(n2)。提出利用树状结构存储方法求取均值序列,并介绍其实现方法,该方法时间复杂度大大降低,仅为O(n*lnn)。

基于改进A^(*)算法的路径规划研究

研究了A^(*)算法在二、三维模型路径规划中的优化方法。通过实时阈值法和惩罚因子法减少开放列表中不必要的搜索空间和冗余路径;采用自定义优先级队列、二叉堆法和哈希表替代传统A^(*)算法中的处理方式;在对二维地图的研究中,采用局部A^(*)算法避免大面积搜索。实验结果表明,经过改进的A^(*)算法显著提高了搜索和路径规划速度,减少了计算时间和内存消耗,验证了该算法的可行性和有效性。

改进Moser法射线追踪

地震波场正演模拟、层析成像、偏移成像经常需要用到射线追踪，本文在基于图形理论的Ｍｏｓｅｒ法基础上，改进其网格节点的划分、追踪时路径的选取，并增加直射线追踪以消除在速度变化不大时射线受节点布置影响出现不合理的折曲现象．

内存管理机制的高效实现研究

为了高效地管理内存,防止内存泄漏、越界访问等问题的出现,在分析传统动态内存管理机制的基础上,提出了一种基于Windows虚拟内存管理的高效动态内存管理机制。通过创建内存管理器来维护虚拟地址空间和处理内存申请和释放请求,改进了传统动态内存分配与回收算法,并在VC++6.0开发平台上实现了该动态内存管理机制。测试结果分析表明,该方法有效降低了申请与释放内存的时间耗费,减少了内存碎片的产生,提高了动态内存管理效率。

计算任意最大值堆的枚举总数目的实用算法

给出了一个最大值堆（当它为一棵满二叉树时）的枚举计数公式，提出了计算任意一个最大值堆的枚举总数目的一个实用算法。

基于方向A~*算法的温室机器人实时路径规划

针对复杂环境下的温室机器人路径规划问题,重点研究了生成路径的平滑设计、碰撞检测和算法实时性,提出一种方向A~*算法。首先采用"视野线"平滑原则优化路径,消除锯齿效应并避免部分碰撞;其次应用"圆弧—直线—圆弧"转弯策略,避免机器人本体宽度影响;最后基于二叉堆加速算法,提升算法计算效率。仿真实验结果表明,方向A~*算法满足平滑要求且能有效避免碰撞,加速算法平均提速4~7倍。同时,机器人在真实实验环境下能实现安全自主导航,跟踪误差小于0.15 m,验证了所提方法的可行性。

堆的路径二分搜索算法

本文提出堆的路径二分搜索算法．当用堆来实现优先队列时，此算法可用较少的比较次数完成插入及删除最大元素等操作．

最优堆排序算法

本文讨论了堆的若干性质 ,提出对堆排序算法的改进 .改进后的堆排序算法是一个最优排序算法 ,在最坏情况下需要 nlogn+nα3(n) +O(n)次元素比较和 nlogn+O(n)

最大值堆的枚举计数公式及其实现

根据堆的定义,在构造与最大值堆对应的n元排列的过程中推导出了n个结点最大值堆的枚举总数目的计算公式,讨论了当堆为满堆时的情况,给出了一个复杂度为O(n)的算法实现了任意最大值堆的枚举计数公式。

基于堆的最小连通支配集高效近似算法

提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法。利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造。通过计算堆操作次数,分析算法在平均情况下的时间复杂度。在随机网络模型上的模拟实验结果表明,与已有算法相比,该算法可以得到点数更少的连通支配集。

基于堆排序的PQ+CBWFQ路由器排队调度算法

研究具有QoS特征、易于实现的排队算法一直是优化带宽的重要手段,也是提高宽带IP网络性能的主要途径。文章提出基于堆排序的PQ+CBWFQ网络路由器排队调度算法进行具体实现,并给出低成本的硬件实现方案,对未来的高性能路由器设计具有重要的参考价值。

基于GIS优化Dijkstra算法在物流中心选址中的研究

基于传统的Dijkstra算法,提出了一种采用二叉堆结构和网络边存储模型的优化Dijkstra算法。实验结果表明:优化后的算法是切实有效的,将其应用到物流中心选址中得到了较满意的选址方案。

Dijkstra算法的一种高效率实现

Dijkstra提出单源点最短路径算法即计算一个节点到其他所有节点的最短路径。算法结构过于复杂且效率较低。采用最小堆对Dijkstra最短路径算法进行优化,优化后的算法比起经典算法在时间复杂度和空间复杂度上都有明显的提高。

一种适用于海量多波束测深数据的中值滤波算法

针对CUBE算法中的数据中值滤波排序问题,设计了一种基于堆结构的中值滤波算法。这种方法以初始滤波窗口中间数据为支点,把滤波序列划分为2个堆,进而把查找滤波窗口中间位置数据转化为在两个堆中进行排序并输出根节点的操作。实验结果表明,这种方法的滤波速度约为基于二分查找的中值滤波算法的2~4倍,适合应用于海量数据的滤波处理。

动态拓扑网络最短路径启发式算法

针对动态拓扑网络的最优路径规划中存在的问题,研究了最短路径搜索算法的快速实现技术,提出了一种启发式快速最优路径规划算法。在分析经典迪杰斯特拉最短路径搜索算法和A*启发式搜索算法的基础上,利用椭圆曲线参数设定启发函数初始值,进一步缩小搜索范围。采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了算法的执行效率。仿真试验结果表明该算法具有良好的性能。

基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法

在深入分析传统Ｄｉｊｋｓｔｒａ算法的基础上，提出了利用基于ｋ 叉堆的优先级队列对算法进行改进的思想，并对３ 种可合并堆进行了比较，从理论上证明了四叉堆在ｋ 叉堆中的最优性，设计了基于四叉堆优先级队列及逆邻接表、顾及路段方向阻抗的改进型Ｄｉｊｋｓｔｒａ最短路径算法，将Ｄｉｊｋｓｔｒａ 算法复杂度降为Ｏ（ｎｌｏｇｎ）。针对ＧＩＳ－Ｔ应用系统的动态特征，提出了Ｄｉｊｋｓｔｒａ 算法的逆序计算方法，通过构造逆序最短路径树。

Dijkstra算法的一个改进

本文得到了一种Dijkstra算法的改进算法,如果最短路问题具有n个点和m条边,那么改进算法把问题的计算复杂性从原来的O(nlogn+m)降低为O(nlogn+M)(M≤m)。

求数据流中位数序列的算法分析

中位数求法通常利用排序算法获取,其时间复杂度达到O(n*ln n)甚至O(n^2)。对于数据流,逐点利用排序法求中位数序列,时间复杂度更高,当数据量很大时,运行极其费时,文中提出利用堆结构获取数据流中位数序列的方法。描述基本思想,分析堆的构造方法,详细介绍算法实现过程。其时间复杂度仅为O(n*ln n),较常用的排序算法有较大的改进。最后,通过实验进一步证实该算法的优越性。