An Optimal Systolic Algorithm for Generating Permutations in Lexicographic Order

A systolic algorithm is described for generating all permutations of n elements in lexicographic order. The algorithm is designed to be executed on a linear array of n processors, each having constant size memory, and each being responsible for producing one element of a given permutation. There is a constant delay per permutation, leading to an O(n!) time solution. This is an improvement over the best previously known techniques in two respects: the algorithm runs on the (arguably) weakest model of parallel computation, and is cost optimal (assuming the time to output the permutations is counted). The algorithm is extended to run adaptively, i.e., when the number of available processors is other than n.     

A Lexicographic Optimization Algorithm

The sequential optimization of lexicographic approach to solving multi-criteria problems is implemented by finding the generalized solutions of a system of inequalities defining the sequential optimization stages. The algorithm effectively generates an optimal solution at every sequential optimization stage.     

A Two-Criterion Lexicographic Algorithm for Finding All Shortest Paths in Networks

An algorithm for finding all shortest paths in an undirected network is considered. The following two criteria are used: the minimum number of arcs in a path and a minimum path length. The algorithm is analyzed for complexity, and it is empirically shown that, with increasing the network density, its computational efficiency becomes higher than that of the Floyd algorithm adequately modified to find the shortest path with the use of a two-step criterion.     

A Random Base Change Algorithm for Permutation Groups

A new random base change algorithm is presented for a permutation group G acting on n points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random generator Rand(G) producing a random element of G with the uniform distribution and so that the time for each call to Rand (G) is bounded by some function f(n, G). The random base change algorithm has probability 1 - 1/|G| of completing in time O(f(n, G) log |G|) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering. The algorithm requires O(n log |G|) space and the data structure produced can be used to test group membership in time O(n log |G|). Since the output of this algorithm is a data structure allowing generation of random group elements in time O(n log |G|), repeated application of the random base change algorithms for different orderings of the permutation domain of G will always run in time O (n log² |G|). An earlier version of this work appeared in Cooperman and Finkelstein (1992b).     

一种基于字典树的传感器节点关联规则的挖掘算法

无线传感器网络中节点密集,分布范围广,长期监测使得信息量巨大,如何从大量的感知数据中提取或"挖掘"有用的知识,就成为无线传感器网络中信息处理的核心问题。本文提出一种新的关联规则挖掘算法PLT-STREAM,用来发现节点之间的有用关联,以此消除节点之间信息的冗余。该算法能帮助用户对数据进行有效的融合、分类、查询、分析、理解和决策。实验结果表明,该方法能够有效减少信息处理中通信和计算所消耗的能量,缩短数据查询响应的时间,从而延长整个网络的寿命。     

最佳并行排列组合算法

本文给出两个新的最佳并行排列组合算法。这里所说的排列组合均指从n个元素中取m个元素的排列和组合处理。算法可运行于一种非常简单的并行计算模型上,它由k个同步运行的处理机构成,其中1≤k≤N,N为要处理的元素个数。当1≤k≤N/n,算法需O(「N/k」·h)时间。     

SIMD数据置换操作的自动生成和优化

SIMID指令能够高效开发数据级并行,因此当前绝大多数通用微处理器都支持这种机制。但是应用程序和算法的一些固有特性,如访存地址不对齐、非连续存储访问以及控制流等,使得编译器或程序员必须借助置换指令重新组合向量的各个元素,才能得到符合SIMD指令要求的操作数。这些冗余的置换指令已成为当前挖掘数据级并行的主要性能瓶颈。提出一种自动的数据置换指令生成和优化算法,以有效地减少置换指令带来的性能损失。该算法基于提出的一种新中间表示形式,其中包含有足够的操作数地址信息,因此可以将置换指令的生成转换为数据流图中冲突边的识别问题,而将置换指令的优化转化为用最少的置换指令来删除所有冲突边的问题。面向一组典型多媒体程序进行测试的结果表明,提出的算法可平均获得7%的性能加速。     

面向置换检验的冗余对比模式过滤算法

置换检验方法在进行对比模式挖掘时,返回结果中存在许多冗余对比模式。利用Charm方法挖掘样本集合中的对比模式,提出基于固定属性置换的FSPRP和FEPRP算法,依次为不同长度的对比模式构建零分布,从而过滤冗余对比模式。FSPRP算法通过生成一定数量的置换样本集合构建零分布,FEPRP算法则通过计算每个模式的对比性度量值分布合并建立零分布。实验结果表明,FSPRP和FEPRP算法相较于比较约束法能够过滤较多数量的冗余对比模式,并且FEPRP算法生成的零分布更接近精确零分布。     

An Efficient Algorithm for Gray-to-Binary Permutation on Hypercubes

Both Gray code and binary code are frequently used in mapping arrays into hypercube architectures. While the former is preferred when communication between adjacent array elements is needed, the latter is preferred for FFT-type communication. When different phases of computations have different types of communication patterns, the need arises to remap the data. We give a nearly optimal algorithm for permuting data from a Gray code mapping to a binary code mapping on a hypercube with communication restricted to one input and one output channel per node at a time. Our algorithm improves over the best previously known algorithm (J. Parallel Distrib. Comput. 4, 2 (Apr. 1987), 133-172) by nearly a factor of two and is optimal to within a factor of n(n − 1) with respect to data transfer time on an n-cube. The expected speedup is confirmed by measurements on an Intel iPSCI2 hypercube.     

全排列的递归算法实现

递归算法的设计与实现是非常重要的内容,全排列是组合数学中最常见的问题。提出了基于递归算法并通过c语言编程实现了计算机解题,实例数据表明程序非常高效。     

全排列递归算法在算法教学中的重要性

全排列递归算法简洁,清晰,可读性强。针对该算法在递归算法的设计以及回溯法中的应用．讨论了全排列递归算法在算法教学中的重要作用。     

洗牌交换置换网络SEP的一种新的路由算法

1引言与sEP网络的定义 众所周知,Cayley图和Cayley陪集图在计算机互连网络的设计与分析中起着重要的作用[1～3].例如:熟知的环(ring)网络,圆环面(torus)网络,超圆环面(super-torus)网络[7],星图(star graph)网络,超立方体网络(hypercube),立方体连接圈(cubeconnected cycles)网络[2]均可看作是Cayley图.而de Bruijn网络与洗牌交换网络[8]可作为Cayley陪集图的例子.     

求解总拖期时间最小化流水车间调度问题的多智能体进化算法

针对总拖期时间最小化的置换流水车间调度问题（Total tardiness permutation flow-shop scheduling problem） 提出了一种基于多智能体的进化搜索算法. 在该算法中,采用基于延迟时间排序的学习搜索策略（Tardiness rank based learning）,快速产生高质量的新个体,并根据概率更新模型进行智能体网格的更新进化. 同时通过实验设计的方法探讨了算法参数设置对算法性能的影响. 为了验证算法的性能,求解了Vallada标准测试集中540个测试问题,并将测试结果与一些代表算法进行比较,验证了该算法的有效性.     

Automatic Generation of Redundant Models for Permutation Constraint Satisfaction Problems

If we have two representations of a problem as constraint satisfaction problem (CSP) models, it has been shown that combining the models using channeling constraints can increase constraint propagation in tree search CSP solvers. Handcrafting two CSP models for a problem, however, is often time-consuming. In this paper, we propose model induction, a process which generates a second CSP model from an existing model using channeling constraints, and study its theoretical properties. The generated induced model is in a different viewpoint, i.e., set of variables. It is mutually redundant to and can be combined with the input model, so that the combined model contains more redundant information, which is useful to increase constraint propagation. We also propose two methods of combining CSP models, namely model intersection and model channeling. The two methods allow combining two mutually redundant models in the same and different viewpoints respectively. We exploit the applications of model induction, intersection, and channeling and identify three new classes of combined models, which contain different amounts of redundant information. We construct combined models of permutation CSPs and show in extensive benchmark results that the combined models are more robust and efficient to solve than the single models.     

基于字典顺序式多目标遗传算法的预测控制

在多目标遗传算法中引入动态适应度函数,以解决字典顺序式优化问题,并以此设计多目标控制器.以Shel标准控制问题为研究对象,验证算法的有效性,并研究在模型增益摄动及出现大扰动的情况下算法的性能.