A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs

An edge ranking of a graph G is a labeling r of its edges with positive integers such that every path between two different edges eu, ev with the same rank r(eu)=r(ev) contains an intermediate edge ew with rank r(ew)>r(eu). An edge ranking of G is minimum if the largest rank k assigned is the smallest among all rankings of G. The edge ranking problem is to find a minimum edge ranking of given graph G. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of trees. In this paper, we first show, on a general graph G, a relation between a minimum edge ranking of G and its minimal cuts, which ensures that we can obtain a polynomial time algorithm for obtaining minimum edge ranking of a given graph G if minimal cuts for each subgraph of G can be found in polynomial time and the number of those is polynomial. Based on this relation, we develop a polynomial time algorithm for finding a minimum edge ranking on a 2-connected outerplanar graph.     

A polynomial time algorithm for an exact encoding of space containing

We address the problem of collision free navigation of a point robot among polygonal obstacles in a bounded known terrain in two dimensional space. The obstacles could be convex or concave polygons. We consider a combinatorial approach to the problem and focus on partitioning the terrain into distinct regions and encoding these regions. We then build a region-graph whose nodes represent the regions and every pair of neighbouring regions (nodes) are connected by an edge. We propose an o(n ₄) preprocessing algorithm to do this. This converts the problem of navigation from a source point to a destination point into a problem of finding a path in a planar graph from one of its nodes to another in O (n ₂ log n) time. The shortest path is derivable in 0(n ₄) time. The extension of the algorithm for three-dimensional space is also discussed.     

大整数取模的快速运算

大整数取模运算是密码学应用的一种基本运算,尤其是在基于因子分解假设的公钥密码学中占有极其重要的地位。提出的m位和n位两个大整数快速取模算法,是利用分治法思想,将n位的大整数分解为n个独立十进制整数的组合,通过八次大整数乘法建立一个预处理表,能够有效地将大整数取模的计算复杂度降为[O(n(m-n))],经大量实验数据验证该算法的合理性和高效性。     

A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) provides an excellent algorithmic framework for solving multi-objective optimization problems. It decomposes a target problem into a set of scalar sub-problems and optimizes them simultaneously. Due to its simplicity and outstanding performance, MOEA/D has been widely studied and applied. However, for solving the multi-objective vehicle routing problem with time windows (MO-VRPTW), MOEA/D faces a difficulty that many sub-problems have duplicated best solutions. It is well-known that MO-VRPTW is a challenging problem and has very few Pareto optimal solutions. To address this problem, a novel selection operator is designed in this work to enhance the original MOEA/D for dealing with MO-VRPTW. Moreover, three local search methods are introduced into the enhanced algorithm. Experimental results indicate that the proposed algorithm can obtain highly competitive results on Solomon׳s benchmark problems. Especially for instances with long time windows, the proposed algorithm can obtain more diverse set of non-dominated solutions than the other algorithms. The effectiveness of the proposed selection operator is also demonstrated by further analysis.     

求解带软时间窗车辆路径问题的融合算法

设计了遗传算法与变异蚂蚁算法的一个融合算法,该算法采用优良基因保护策略,引入蚂蚁寻径变异机制,并改进了信息素的更新方式,提高了寻径速度以及寻径的全局性。经过对比实验,验证了本融合算法可以有效而快速地获得问题模型的最优解或近似最优解。     

A polynomial time algorithm to detect PQI interval orders

Let S be a P Q I preference structure on a finite set A , where the relations P , Q , I stand for 'strict preference', 'weak preference' and 'indifference,' respectively. Two specific preference structures: P Q I semi orders and P Q I interval orders, have been considered and characterised recently in such a way that is possible to associate to each element of A an interval such that P holds when one interval is completely to the right of the other, I holds when one interval is included to the other and Q holds when one interval is to the right of the other, but they do have a non empty intersection ( Q medelling the hesitation). While the detection of a P Q I semiorder is straightforward, the case of the P Q I interval order is more difficult as the theorem of existence consists in a second-order formula. The paper presents an algorithm for detecting a P Q I interval order and demonstrates that it is backtracking free. This result leads to a matrix version of the algorithm which can be proved to be polynomial.     

回归型支持向量机的简化算法

针对支持向量机应用于函数估计时支持向量过多所引起的计算复杂性,提出一种简化算法,可以大幅度地减少支持向量的数量,从而简化其应用.采用简化算法还可以将最小平方支持向量机算法和串行最小化算法结合起来,达到学习效率高且生成的支持向量少的效果.     

A simple linear hidden-line algorithm for star-shaped polygons

A very simple, linear-running-time algorithm is presented for solving the hidden-line problem for star-shaped polygons. The algorithm first decomposes the visibility regions into edge-visible polygons and then solves the hidden-line problem for these simpler polygons. In addition to simplicity the algorithm possesses the virtue of affording a very easy proof of correctness. Some applications where this problem arises are mentioned.     

An optimal online algorithm for halfplane intersection

The intersection of N halfplanes is a basic problem in computational geometry and computer graphics,The optimal offline algorithm for this problem runs in time O(N log N).In this paper,an optimal online algorithm which runs also in time O(N log N) for this problem is presented.The main idea of the algorithm is to give a new definition for the left side of a given line,to assign the order for the opoints of a convex polygon.and then to use binary search method in an ordered vertex set.The data structure used in the algorithm is no more complex than array.     

不确定车辆数的有时间窗车辆选径问题的混合算法

针对标准遗传算法在求解车辆选径问题中出现的早熟、收敛、易陷入局部极值点的问题，提出了一种由遗传算法结合模拟退火算法的混合算法求解车辆选径问题，并与遗传算法进行了比较。该算法利用了模拟退火算法具有的较强的局部搜索能力的特性，有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明，该算法具有计算效率高、收敛速度快和求解质量优的特点，是解决车辆选径问题的有效方法。     

有时间窗车辆路径问题的捕食搜索算法

有时间窗车辆路径问题是当前物流配送系统研究中的热点问题,该问题具有NP难性质。难以求得最优解或满意解,在建立有时间窗车辆路径问题数学模型的基础上。设计了一种模仿动物捕食策略的捕食搜索算法．该算法利用控制搜索空间的限制大小来实现算法的局域搜索和全局搜索,具有良好的局部集中搜索和跳出局部最优的能力．通过实例计算,并与相关启发式算法比较．取得了满意的结果．     

有时间窗车辆路径问题的混合智能算法

有时间窗的车辆路径问题属于组合优化领域中的NP-hard问题。在对该问题进行分析的基础上,为之建立了数学模型,提出了一种求解该问题的混合智能算法。该算法通过使用蚁群算法和遗传算法交替优化,并且及时交换信息,弥补了蚁群算法和遗传算法各自的不足,达到了优势互补的效果,增强了算法的寻优能力,避免了停滞现象。实验结果表明,该算法能有效解决有时间窗的车辆路径问题。