光学向量矩阵乘法研究

向量矩阵乘法运算是数值计算中基本的运算,广泛应用于线性方程组求解、图像处理、数字信号处理、人工智能等多个领域。目前向量矩阵乘法的实现方法有很多种,其中用光学方式实现向量矩阵乘法的方法因其所特有的并行性和乘法性质,在解决这类二维信息处理问题时独具优势而受到研究者们的青睐。对光学向量矩阵乘法的研究进行了深入的分析和总结,综述国内外各种光学矩阵乘法实现的理论和方法,并阐述作者研究的基于三值光学逻辑处理器的实现方法,该方法具有结构简单、易于微型化、计算精度高等优点。     

最短路径的可达矩阵算法

为了提高传统最短路径算法的效率,文中在细致分析传统算法的基础上,提出了一种在业务流程中计算最短路径及寻找不合理活动环的新方法,此方法被称为最短路径的可达矩阵算法.与原有的最短路径算法相比,该方法将可达矩阵的思想引入到最短路径的计算中,可以在矩阵中显示出活动环及活动路径值.文中还详细描述了该方法所涉及的定义及运算规则.最后,将该方法应用于具体实例,并快速地找到了活动环及活动路径,为业务流程再造提供了一种新的解决方案.     

一种新的城市交通路径搜索算法

针对我国城市交通道路实际情况,提出一种新的基于邻接矩阵的交通路径搜索算法,算法利用邻接矩阵的特点及其相乘原理,在[n]阶[An]-矩阵中找出交通中的“途径线路”,结合道路上网络节点的相关权值,计算得出一条最佳交通路径。通过算法分析和仿真实验,结果表明,算法运行效率高,设计简单,实用性强。     

矩阵运算的面向对象实现

矩阵数据及矩阵运算在科学计算中出现频度很高,但目前最常使用的C++语言,因不具备二维数组的动态分配能力,致使其在矩阵数据的定义、参数传递、访问安全控制及矩阵运算方面存在一定的不便。如果采用C++的面向对象思想,利用其“类”数据类型,定义一“矩阵类”,将矩阵数据及矩阵运算封装起来,问题则迎刃而解。     

基于非传递路径的次序一致性判断与修正

为了修正非次序一致性矩阵,定义了非传递路径数和非传递路径贡献数两个概念.提出利用非传递路径矩阵来进行模糊判断矩阵的次序一致性判断方法.同时,根据非传递路径数的大小来确定模糊判断矩阵中的最不合理元素,这样模糊判断矩阵的次序一致性判断和修正可以一体化实现.最后,用1个中小板上市公司的非财务指标体系构建作为实例进行说明.     

基于开关路径集的形成动态简单回路的算法

电力网络中影响断点求取算法效率的关键步骤是简单回路的求取.在基于回路线性组合提出的形成简单回路的方法上,利用跟踪开关变位,在获得开关变量形式的基本回路矩阵基础上,利用一定的运算规则,形成电路系统结构中动态的简单回路;并应用同或运算对形成的动态简单回路加以处理,得到形成的简单回路相对应的开关变量函数,进而提出基于开关路径集的形成简单动态回路的新算法.算例证明了文中思想和算法的正确性.     

双层优化A*算法与动态窗口法的动态路径规划

为满足动态环境中移动机器人既要动态避障抵到终点,又要尽可能地做到全局最优的路径规划需求,提出了一种双层优化A*算法与动态窗口法相结合的移动机器人路径规划算法。在传统A*算法求得的全局路径轨迹基础上,首先通过一层全局优化,计算路径节点间斜率,提取关键转折点,大幅度减少路径转折点数量;再通过二层全局优化,延长路径段求得路径交点,判断交点是否通过障碍物的方法,将路径转折点数降到最低;设计动态窗口法的轨迹评价函数,解决了机器人容易陷入“凹”“C”形障碍物的问题,同时保证了障碍物安全距离并选取全局最优的路径轨迹。最后分别在静态与动态的二维栅格地图中对传统A*算法、一层优化A*、二层优化A*以及融合算法进行仿真实验。实验结果表明一层优化A*算法大幅度降低了转折次数;二层优化A*算法将转折点数降到最低,但是路径长度小幅度增加;融合算法实现了机器人实时动态避障抵到终点,而且在保证安全距离的同时更加贴近全局最优规划。     

基于改进蚁群算法的越野路径规划

针对车辆的越野路径规划问题,研究并分析了地形坡度和地表属性对于车辆路径规划的综合影响。引入了“窗口移动法”对地形进行先期的坡度计算和通行性分析,就轮式车辆和履带式车辆分别建立了地表属性的粗糙度评价指标,并采用“面积占优法”将地表属性栅格化。通过建立禁忌表,叠加了坡度与粗糙度的约束影响以减少搜索范围,提高搜索效率。构造了改进蚁群算法的估价函数,并结合路径表设计了考虑坡度和粗糙度约束的路径优化算法。仿真结果表明,该算法能够快速有效地实现符合真实地形环境的越野路径规划。     

矩形网格上二元矩阵切触有理插值的新方法

熟知的矩阵切触有理插值的方法都与连分式有关,不仅计算繁琐,而且难以避免出现“极点、不可达点”。用网格点构造有理插值基函数,用型值点构造具有承袭性的各阶矩阵插值算子,通过插值基函数与插值算子作线性运算,构造出二元矩阵各阶切触有理插值函数,有效避免了有理插值的“极点、不可达点”问题。若选择适当的参数,还可以任意降低插值函数的次数,数值例子表明了该方法简单、有效、实用性强。     

基于C 的稀疏矩阵乘法运算器的实现

稀疏矩阵是指那些多数元素为零的矩阵。本文利用稀疏矩阵"稀疏"特点进行存储和计算可以大大节省存储空间,提高计算效率。通过采用标准C 语言设计实现了稀疏矩阵乘法运算器。     

Solving an algebraic path problem and some related graph problemson a hyper-bus broadcast network

The parallel computation model upon which the proposed algorithms are based is the hyper-bus broadcast network. The hyper-bus broadcast network consists of processors which are connected by global buses only. Based on such an improved architecture, we first design two O(1) time basic operations for finding the maximum and minimum of N numbers each of size O(log N)-bit and computing the matrix multiplication operation of two N×N matrices, respectively. Then, based on these two basic operations, three of the most important instances in the algebraic path problem, the connectivity problem, and several related problems are all solved in O(log N) time. These include the all-pair shortest paths, the minimum-weight spanning tree, the transitive closure, the connected component, the biconnected component, the articulation point, and the bridge problems, either in an undirected or a directed graph, respectively     

Shortest path and closure algorithms for banded matrices

A fast algorithm is given for the all-pairs shortest paths problem for banded matrices having band-width b. It solves the negative-cycle problem and calculates all path lengths within the band in O(nb²) time and calculates all other path lengths in O(n²b) time.     

On planar path transformation

A flip or edge-replacement is considered as a transformation by which one edge e of a geometric object is removed and an edge f (f≠e) is inserted such that the resulting object belongs to the same class as the original object. Here, we consider Hamiltonian planar paths as geometric objects. A technique is presented for transforming a given planar path into another one for a set S of n points in convex position in the plane. Under these conditions, we show that any planar path can be transformed into another planar path by at most 2n−5 flips. For the case when the points are in general position we provide experimental results regarding transformability of any planar path into another. We show that for n?8 points in general position any two paths can be transformed into each other. For n points in convex position we show that there are n²n−2 directed Hamiltonian planar paths. An algorithm is presented which uses flips of size 1 and flips of size 2 to generate all such paths with O(n) time between the generation of two successive paths.     

PH-graphs for analyzing shortest path problems with correlated traveling times

This paper presents a new approach to model weighted graphs with correlated weights at the edges. Such models are important to describe many real world problems like routing in computer networks or finding shortest paths in traffic models under realistic assumptions. Edge weights are modeled by phase type distributions (PHDs), a versatile class of distributions based on continuous time Markov chains (CTMCs). Correlations between edge weights are introduced by adding dependencies between the PHDs of adjacent edges using transfer matrices. The new model class, denoted as PH graphs (PHGs), allows one to formulate many shortest path problems as the computation of an optimal policy in a continuous time Markov decision process (CTMDP). The basic model class is defined, methods to parameterize the required PHDs and transfer matrices based on measured data are introduced and the formulation of basic shortest path problems as solutions of CTMDPs with the corresponding solution algorithms are also provided. Numerical examples for some typical stochastic shortest path problems demonstrate the usability of the new approach.     

Output-threshold coupled neural network for solving the shortest path problems

This paper presents a coupled neural network, called output-threshold coupled neural network (OTCNN), which can mimic the autowaves in the present pulsed coupled neural networks (PCNNs), by the construction of mutual coupling between neuron outputs and the threshold of a neuron. Based on its autowaves, this paper presents a method for finding the shortest path in shortest time with OTCNNs. The method presented here features much fewer neurons needed, simplicity of the structure of the neurons and the networks, and large scale of parallel computation. It is shown that OTCNN is very effective in finding the shortest paths from a single start node to multiple destination nodes for asymmetric weighted graph, with a number of iterations proportional only to the length of the shortest paths, but independent of the complexity of the graph and the total number of existing paths in the graph. Finally, examples for finding the shortest path are presented.     

Regular path queries under approximate semantics

We give a general framework for approximate query processing in semistructured databases. We focus on regular path queries, which are the integral part of most of the query languages for semistructured databases. To enable approximations, we allow the regular path queries to be distorted. The distortions are expressed in the system by using weighted regular expressions, which correspond to weighted regular transducers. After defining the notion of weighted approximate answers we show how to compute them in order of their proximity to the query. In the new approximate setting, query containment has to be redefined in order to take into account the quantitative proximity information in the query answers. For this, we define the approximate containment, and its variants k-containment and reliable contain-ment. Then, we give an optimal algorithm for deciding the k-containment. Regarding the reliable approximate containment, we show that it is polynomial time equivalent to the notorious limitedness problem in distance automata.     

分段可压缩路径的切换优化算法

针对切换控制系统可渐近稳定的充分条件的难题,提出了一种分段可压缩路径的搜索算法。分析了压缩路径的切换控制规律,并对常规可压缩路径的切换控制进行了优化,提出了最短和加权平均可压缩优化路径算法及峰值控制优化算法。通过实例Matlab程序仿真寻找可压缩路径的优化参数,比对切换实验数据,演示不同优化算法下的切换率稳定和收敛状况。     

Two-way D algorithm for path planning and replanning

Inspired by the Witkowski’s algorithm, we introduce a novel path planning and replanning algorithm — the two-way D^∗ (TWD^∗) algorithm — based on a two-dimensional occupancy grid map of the environment. Unlike the Witkowski’s algorithm, which finds optimal paths only in binary occupancy grid maps, the TWD^∗ algorithm can find optimal paths in weighted occupancy grid maps. The optimal path found by the TWD^∗ algorithm is the shortest possible path for a given occupancy grid map of the environment. This path is more natural than the path found by the standard D^∗ algorithm as it consists of straight line segments with continuous headings. The TWD^∗ algorithm is tested and compared to the D^∗ and Witkowski’s algorithms by extensive simulations and experimentally on a Pioneer 3DX mobile robot equipped with a laser range finder.     

具有树和路约束的平行机排序问题

考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论：在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。     

面向图数据的结构化正则路径查询方法

正则路径查询是一种应用正则表达式在图数据上进行查询的技术,通常利用有限状态自动机实现查询匹配。现有正则路径查询方法的匹配结果为顶点对的序列,未能充分保留图的结构,为了解决这一问题,提出了一种面向图数据的结构化正则路径查询方法,通过在不同的序列间加以结构化约束,使得查询结果由路径转变为子图。为了实现这一目的,首先定义了一种结构化的正则路径查询语言,并设计了结构化的查询解析以及基于此结构的匹配算法。实验在模拟数据集和真实数据集上进行了测试与分析,验证了网络规模对查询速度的影响,并设置了对照实验。实验结果表明,提出方法能够在保证满足正则表达式约束的前提下实现结构化查询。