改进Dijkstra算法在GIS导航应用中最短路径搜索研究

研究GIS在电子导航系统应用中的最短路径搜索效率问题。在电子导航系统中对最短路径的搜索效率要求很高。随着城市发展交通线路剧增,传统的基于Dijkstra算法的GIS导航系统不能适应日益复杂的交通线路,存在最短路径搜索效率过低的问题。考虑到GIS空间分布的特性,提出了改进的Dijkstra算法用以解决GIS导航中的最短路径搜索问题。改进算法不仅避免了传统Dijkstra算法逐个节点遍历搜索,而且根据方向优先特性缩小搜索范围,大大减少了搜索工作量,并通过改变搜索节点存储的数据结构提高了最短路径的搜索效率。实验表明,这种改进算法较之传统算法能够有效提高最短路径的搜索效率,满足了电子导航系统对最短路径搜索效率的要求,取得了满意的结果。     

迷宫最短路径问题新算法

提出了求解迷宫最短路径问题的新算法,该算法抛弃了经典算法(深度优先搜索和广度优先搜索)中繁杂低效的递归、回溯思想。通过合理的变换,将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试,显示出该算法易于理解、易于编程、时间空间复杂度低等优点。     

基于宽度优先搜索的路径生成算法

宽度优先搜索和深度优先搜索是图论中常用的两种搜索算法.两者各有优势,但深度优先搜索算法的效率在低连通度图中会大大降低,这时更适合采用宽度优先搜索算法.本文提出了一种基于宽度优先搜索的路径生成算法,具有较好的时间复杂性和空间复杂性.     

基于方向优先和对向搜索的改进Dijkstra算法

传统Dijkstra算法在搜索最短路径时需要逐一遍历网络图中所有顶点,计算量大,占用存储空间大,搜索效率很低。因此,针对交通网络的空间特性和传统算法的不足,改进存储结构,采用“方向优先+对向搜索”相结合的搜索方法,以减少存储空间,缩小搜索范围,从而加快搜索速度,提高算法的搜索效率。实验数据表明：与传统算法相比,改进的算法能够更有效地搜索交通网络中的最短路径,具有更好的实用价值。     

公交车网络的最短路径算法及实现

最短路径问题是图论研究中的一个经典算法问题．旨在寻找图中任意两结点之间的最短路径。一般在交通道路网络中最短路径问题就是单纯地求解两点问的最短路径。为了保证实用性，公交车网络的最短路径算法以转车次数最少为首要目的。文中借鉴广度优先搜索的思路来求解最短路径，即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次。首先说明了算法的计算机实现方法，再举例详细说明其过程，最后指出此算法的扩充用途。     

公交车网络的最短路径算法及实现

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中任意两结点之间的最短路径.一般在交通道路网络中最短路径问题就是单纯地求解两点间的最短路径.为了保证实用性,公交车网络的最短路径算法以转车次数最少为首要目的.文中借鉴广度优先搜索的思路来求解最短路径,即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次.首先说明了算法的计算机实现方法,再举例详细说明其过程,最后指出此算法的扩充用途.     

过必经节点集的动态剪枝搜索算法

针对过必经节点集的最短路径问题,提出一种基于动态减枝策略的深度优先搜索算法（Depth First Search based on Dynamic Pruning,DP-DFS）,该算法构建一个二维矩阵,每搜索一个节点,比较当前路径的权值和与矩阵中已保存的权值,如果当前路径的权值小于矩阵中保存的权值,则更新矩阵中权值为当前较小的路径权值,否则进行剪枝。该算法比较适合较大规模的图搜索,实验表明,必经节点个数在50以内时,利用该算法可以在30?s内找到一条近似最优的最短路径。     

基于备选路径集的在线最短耗时公交换乘方法

面向城市公交出行者,在给定出行起讫点及起始时间的情况下,提出一种基于备选路径集的在线最短耗时公交换乘方法：在预处理阶段离线地运用双向广度优先搜索方法得到点对之间的静态备选路径集;结合实时公交到站时间预测数据或发车间隔等静态的公交运营数据,进行最短耗时评估,在线地从中选择耗时最短的路径。将该方法运用于沈阳公交路网案例中（公交到站时间预测数据仿真生成）,并嵌入沈阳市公交出行查询系统,结果表明了其实用性。     

一种SRIO网络负载均衡最短路径路由算法

在串行RapidIO传输过程中,路由选路算法是影响传输性能的重要因素之一。针对串行高速输入-输出(SRIO)网络深度优先搜索分配路径非最优问题,提出一种负载均衡最短路径路由算法。通过广度优先搜索对SRIO网络中的节点进行枚举并建立网络拓扑信息,以路由跳数定义路由的成本,根据改进Floyd-WarShall算法计算并保存交换节点间的K最短路径。给出预期负载的概念和链路上的路由路径数量来定义链路的负载,采用负载均衡算法从K最短路径中进行选路,建立SRIO网络最短路径约束的负载均衡路由。实验结果表明,与深度遍历路由算法、最小跳数算法相比,该算法在网络传输平均跳数、链路平均负载和链路负载均衡方面有更好的表现,能够有效提升SRIO路由网络的稳定性。     

基于图的最短路径跨域数据交换实现

最短路径查找的效率决定了跨域数据交换的效率。针对通道较少（e〈n（n-1））的跨域数据交换最短路径查找的问题,文中实现了一种基于图的最短路径查找方法。设计了域标识模型、域表和通道表,建立了域表与通道表的关系模型,根据面向对象的方法基于邻接表存储结构构造了域及通道的邻接表。基于深度优先搜索遍历原理,定义邻接表对象、路径集合,记录域访问历史、路径长度,以递归的方式实现了跨域最短路径的查找。实现了电子政务跨域数据交换时域间最短路径的查找,证实了文中方法的有效性。     

A disruption recovery plan in a three-stage production-inventory system

This paper proposes a recovery plan for managing disruptions in a three-stage production-inventory system under a mixed production environment. First, a mathematical model is developed to deal with a disruption at any stage while maximizing total profit during the recovery-time window. The model is solved after the occurrence of a disruption event, with changed data used to generate a revised plan. We also propose a new and efficient heuristic for solving the developed mathematical model. Second, multiple disruptions are considered, where a new disruption may or may not affect the recovery plans of earlier disruptions. The heuristic, developed for a single disruption, is extended to deal with a series of disruptions so that it can be implemented for disruption recovery on a real-time basis. We compare the heuristic solutions with those obtained by a standard search algorithm for a set of randomly generated disruption test problems, and that show the consistent performance of our developed heuristic with lower computational times. Finally, some numerical examples and a real-world case study are presented to demonstrate the benefits and usefulness of our proposed approach.     

BL-代数的弱（相对）零化子

基于格的相对零化子概念提出了[BL-]代数的弱相对零化子概念。讨论了弱相对零化子的基本性质,证明了弱相对零化子是[BL-]代数的滤子,给出了弱相对零化子的表示定理。进一步提出了弱零化子概念,给出了零化子等价于弱零化子的充要条件,刻画了[BL-]代数全体滤子集的结构。结论为今后研究[BL-]代数的弱广义相对零化子提供了基础。     

Image Manifolds which are Isometric to Euclidean Space

Recently, the Isomap procedure [10] was proposed as a new way to recover a low-dimensional parametrization of data lying on a low-dimensional submanifold in high-dimensional space. The method assumes that the submanifold, viewed as a Riemannian submanifold of the ambient high-dimensional space, is isometric to a convex subset of Euclidean space. This naturally raises the question: what datasets can reasonably be modeled by this condition? In this paper, we consider a special kind of image data: families of images generated by articulation of one or several objects in a scene—for example, images of a black disk on a white background with center placed at a range of locations. The collection of all images in such an articulation family, as the parameters of the articulation vary, makes up an articulation manifold, a submanifold of L ². We study the properties of such articulation manifolds, in particular, their lack of differentiability when the images have edges. Under these conditions, we show that there exists a natural renormalization of geodesic distance which yields a well-defined metric. We exhibit a list of articulation models where the corresponding manifold equipped with this new metric is indeed isometric to a convex subset of Euclidean space. Examples include translations of a symmetric object, rotations of a closed set, articulations of a horizon, and expressions of a cartoon face. The theoretical predictions from our study are borne out by empirical experiments with published Isomap code. We also note that in the case where several components of the image articulate independently, isometry may fail; for example, with several disks in an image avoiding contact, the underlying Riemannian manifold is locally isometric to an open, connected, but not convex subset of Euclidean space. Such a situation matches the assumptions of our recently-proposed Hessian Eigenmaps procedure, but not the original Isomap procedure.     

COS:度量分布式大数据处理系统的效率

【目的】在大数据处理领域,分布式计算系统得到广泛应用,它们的可扩展性得到重点关注,但其绝对性能往往没有得到重视。我们希望提出科学合理、与时俱进的度量标准,对分布式系统的性能进行评估。【方法】本文通过对比特定任务的单机实现和分布式实现来讨论分布式系统的性能,提出COS(Configuration that Outperforms a Single machine)这一指标,来衡量分布式系统在达到单台机器的性能时,需要的硬件资源数量。我们选取k-means聚类和逻辑回归两个经典机器学习算法,对其进行单机多线程实现,并通过向量化计算、优化内存分配与访问等方式对性能进行了优化,为分布式多机系统的性能提供参考。【结果】以Apache Spark作为对标系统,实验发现无论是使用其原生编程接口,还是经过悉心优化的机器学习库,都要使用数倍甚至数百倍的机器,才能达到单机多线程实现的性能。【局限】分布式系统与单机实现进行性能对比并不是完全公平的,分布式系统的额外开销客观存在。【结论】但COS指标仍能反映分布式系统存在的绝对性能较差、没有充分利用硬件优势等问题。     

A class of new transforms tailored for the hypergeometric series

A new class of transforms, tailored for the hypergeometric series, is proposed and tested on a number of series. From a knowledge of a given number of terms of a sequence, these transforms reproduce the functions with a better accuracy than the Levin-like transforms. Though there exists a correlation between the approximative power of a rational approximant and its ability to predict the leading terms of a series, there are exceptions to this, especially in the case of divergent series. The new transforms can, in most cases, predict a number of extra terms not used in the construction of the approximants.     

ROD-based hybrid TH precoding and combining for mmWave large-scale MIMO systems

Hybrid precoding is one of key techniques for millimeter wave (mmWave) large-scale multiple-input multiple-output (MIMO) systems. This paper considers a nonlinear hybrid precoding architecture which consists of a nonlinear unit, a reductive digital precoder and a constant modulus radio frequency (RF) precoder, and presents a novel hybrid Tomlinson-Harashima (TH) precoding and combining algorithm. Firstly, due to the intractability of the sum rates maximization problem for such a nonlinear hybrid precoding architecture, a tractable three-stage optimization problem is constructed through the lower bound of the sum rates, which allows the digital precoding matrix, the RF precoding matrix and the RF combining matrix to be optimized sequentially and independently. Then, in order to solve the three-stage optimization problem effectively, a novel row orthogonal decomposition (ROD) is defined. Based on the ROD, it is interesting that the necessary and sufficient condition of the optimal digital precoding matrix can be obtained, and a near-optimal RF precoding matrix can be derived. Finally, the optimization of the RF combining matrix is reformulated as a unimodular quadratic programming and solved by a generalized power method. Theoretical analyses and simulations indicate that the proposed ROD-based hybrid TH precoding and combining algorithm can offer a higher sum rates and a lower bit error rate with a comparable complexity in comparison to the previous works.     

Learning criterion and inductive behaviour

Inductive behaviours may be classified according to their aim. We intend to show that there are at least two kinds of inductive behaviours. Most of the publications seem to take into consideration only one of these: to copy as exactly as possible the behaviour of a probability process. After a brief discussion to explain the necessity of a learning criterion and a recall about one criterion, representative of most of them, we shall define a new criterion, and show why it is better fitted to learn the laws of a deterministic process from a set of observations.This criterion has been used to implement a program which builds an acceptor of natural language sentences in a CAI environment using a tutorial strategy, and then for a question answering device. As attractive as the results are, their improvement requires a semantic model. We give the basic principles of a model which we currently develop, and whose main feature is approximation.     

Robust estimation of continuous nonlinear plants with discrete measurements

In this work the problem of designing a state estimator for completely or partially observable continuous nonlinear plants with discrete measurements is addressed. The combination of a geometric approach with a stability analysis yields an estimator design methodology with a nonlinear detectability condition susceptible of testing, a systematic estimator construction, a robust convergence criterion coupled with a simple tuning scheme, as well as a rationale to explain the interplay between sampling time, estimator gains, and estimator functioning. Comparing with the continuous measurement case where the convergence is attained by tuning the gain above a low limit, in the discrete measurement case the loss of information due to the measurement sampling increases the size of the lower gain limit, and imposes sampling time and high gain limits. The proposed methodology is applied to address the estimation problem of a class of solution homopolymerization reactors, and is tested with a methyl-methacrylate polymerization run taken from a previous extended Kalman filter implementation study with experimental data.     

Performance study of a water ramjet engine

A performance study of a water ramjet engine is described.The engine is powered by the reaction of a magnesium-based propellant and ingested water.In this study,a solid propellant,which consisted of a large percentage of magnesium,a binder and a small amount of oxidant,was used as a hydro reactive fuel.Cold water was injected into the combustion chamber as a main oxidant.A scaled-down experimental engine was tested in a direct-connect ground testing system to characterize the factors influencing the engine ...