This paper presents a general purpose algorithm for solving the Unfriendly Beehive Game. The proposed algorithm will utilize an artificial neural network to solve the problem. The neural network will use a simple part...
详细信息
This paper presents a general purpose algorithm for solving the Unfriendly Beehive Game. The proposed algorithm will utilize an artificial neural network to solve the problem. The neural network will use a simple partial differential (motion) equation expressed in terms of its natural constraints. Each constraint within the equation represents a simple connection to an artificial neuron. Each connection strength (or synaptic strength) is weighted by multiplicative constants and summed together. The result is an input that is adjusted in the direction that decreases the error or conflict. Using this information, the system derives a simple binary state output in an attempt to solve the puzzle. Given an overall time slot in which to resolve all conflicts, the system iteratively strives to arrive at the state of the global minimum. The proposed algorithm will be able to solve a variety of real-world problems, including: facility layouts for maximizing productivity and safety, classroom assignment for minimizing pupil conflict, crop and plant placement for maximizing yields, and chemical placement within shipping boxes to reduce the possibility of chemical interactions.
Let C = {c1,...,c(m)} be a family of subsets of a finite set S = {1,..., n}, a subset S' of S is a co-hitting set if S' contains no element of C as a subset. By using an O ( (log n) 2) time EREW PRAM algorithm...
详细信息
Let C = {c1,...,c(m)} be a family of subsets of a finite set S = {1,..., n}, a subset S' of S is a co-hitting set if S' contains no element of C as a subset. By using an O ( (log n) 2) time EREW PRAM algorithm for a maximal independent set problem (MIS), we show that a maximal co-hitting set for S can be computed on an EREW PRAM in time O (alphabeta (log (n + m))2) using 0 (n2m) processors, where alpha = max{\c(i)\\i = 1,...,n} and beta =max{\d(j)\\ j = 1,...n} with d(j)={c(i)\j is-an-element-of c(i)}. This implies that if alphabeta = O((log(n+m))k) then the problem is solvable in NC.
A new parallel algorithm for finding the maximum value of a data set is proposed. Execution times are investigated by taking into account the effect of the overhead time of communication for four kinds of interconnect...
详细信息
A new parallel algorithm for finding the maximum value of a data set is proposed. Execution times are investigated by taking into account the effect of the overhead time of communication for four kinds of interconnection networks; cube connection array, linear array, mesh array, and three-dimensional mesh array. The optimal numbers of processors are derived in the case where the number of processors is less than the number of data. Those are O (N 1 2 ), O (N 2 3 ), O (N 3 4 ), and O (N) , respectively, for linear array, mesh array, three-dimensional mesh array, and cube-connected arrays.
This paper describes an O(log(3) n) time O(n/log n) processors parallel algorithm for determining the congruence (exact matching) of two point sets in three-dimensions on a CREW PRAM, where n is the maximum size of th...
详细信息
This paper describes an O(log(3) n) time O(n/log n) processors parallel algorithm for determining the congruence (exact matching) of two point sets in three-dimensions on a CREW PRAM, where n is the maximum size of the input point sets. Although optimal O(n log n) time sequential algorithms were developed for this problem, no efficient parallel algorithm was known previously. In the algorithm, the original problem is reduced to the two-dimensional congruence problem by computing a three-dimensional point set cps(S) for each input point set S, where cps(S) satisfies the following conditions: 0 < \cps(S)\ less than or equal to 12;cps(T(S)) = T(cps(S)) for all isometric transformations T. The two-dimensional problem can be solved efficiently in parallel using a parallel version of a previously-known sequential algorithm. cps(S) is computed recursively in the following way: the size of a point set is reduced by a constant factor in each recursive step. To reduce the size of a point set, a convex hull is constructed and then it is regarded as a planar graph, so that combinatorial properties of a planar graph are used effectively. A sequential version of the algorithm works in O(n log n) time, so that this paper gives another optimal sequential algorithm. The presented algorithm can be applied for graphs such that each vertex corresponds to a point and each edge corresponds to a line segment connecting its endpoints. Moreover, the algorithm can be modified for computing the canonical form of a point set or a graph.
In this work, the method based on the work of Huang and McColl on analytical inversion of general tridiagonal matrices is parallelized with MPI. The proposed method is not only capable of finding inverses of full pent...
详细信息
In this work, the method based on the work of Huang and McColl on analytical inversion of general tridiagonal matrices is parallelized with MPI. The proposed method is not only capable of finding inverses of full pentadiagonal matrices, but also of those with pentadiagonal envelope, such as tridiagonal matrices. The method is modified to generate an MPI algorithm. The speed-up performance of the parallelized algorithm is also analyzed on different cases.
作者：
SHYU, CHAdvanced Technology Center
Electronics Research and Service Organization Industrial Technology Research Institute Taiwan Republic of China
In this paper we study the problem of finding a maximum weight clique of an interval graph. Let n be the number of vertices in the graph. We show that a maximum weight clique of an interval graph can be found in time ...
详细信息
In this paper we study the problem of finding a maximum weight clique of an interval graph. Let n be the number of vertices in the graph. We show that a maximum weight clique of an interval graph can be found in time O(log n ) using n processors on an exclusive-read exclusive-write parallel random access machine.
Reducing work-in-process (WIP) inventory is continuing to be an important business need because of several factors including the need to reduce working capital. Numerous techniques have been suggested for WIP reductio...
详细信息
Reducing work-in-process (WIP) inventory is continuing to be an important business need because of several factors including the need to reduce working capital. Numerous techniques have been suggested for WIP reduction, and CONWIP is a competitive algorithm for WIP reduction. Prior CONWIP algorithms have been primarily sequential algorithms and can be potentially incur significant computing time, especially when dealing with inventories for multiple products. The paper proposes a card-setting algorithm for multiple product types subject to routing and throughput requirements. The proposed algorithm searches the WIP space iteratively and the step-size is adaptively selected based on the known properties of multi-chain, multi-class, closed queuing networks. Furthermore, parallelization of this search algorithm across multiple processors is proposed where each processor searches a different segment of the WIP space while adaptively adjusting its step size for all product types to ensure fast convergence. The proposed parallel algorithm can take advantage of distributed computing architectures to speed-up the overall computation. An experimental implementation of the parallel algorithm using Message Passing Interface (MPI) over a high-speed network is described. Computational results demonstrate that the proposed parallel algorithm can be parallelized over eight to ten processors to obtain a speed-up of three to five.
This study provides a parallel algorithm for meshfree analysis based on the radial point interpolation method. This algorithm is designed to suit graphics hardware that support compute unified device architecture, NVI...
详细信息
This study provides a parallel algorithm for meshfree analysis based on the radial point interpolation method. This algorithm is designed to suit graphics hardware that support compute unified device architecture, NVIDIA's software development environment on graphics processing units (GPUs). The radial point interpolation method is a meshfree method that enables strict imposition of Dirichlet boundary conditions, and it mainly consists of two steps: the process for assembly of the discrete linear system and the process for solving the linear system. This paper shows that both the processes can be performed effectively on the GPU by applying our parallel algorithm and at the same time, the costs for data transfer to and from the GPU can be reduced, because the processes related to the discrete linear system are performed independently on the GPU. Our numerical tests confirm that the algorithm performed on the GPU accelerates the computations by a factor of maximum 15.
In this paper, we propose a parallel algorithm for solving the graph isomorphism problem. Our goal is to construct a suitable vertex substitution or to prove the absence of such. The problem is solved for undirected g...
详细信息
In this paper, we propose a parallel algorithm for solving the graph isomorphism problem. Our goal is to construct a suitable vertex substitution or to prove the absence of such. The problem is solved for undirected graphs without loops and multiple edges;it is assumed that the graphs can be disconnected. The question of the existence or absence of an algorithm with a polynomial complexity is currently open. Therefore, as for any time-consuming task, the question arises about speeding up its solution by parallelizing the algorithm. The RPM_ParLib library developed by the author allows developing effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework. Supporting a recursive-parallel programming style, such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. The library can be used for applications written in any programming language supported by the .NET Framework. To solve our problem and conduct a numerical experiment, several applications in the C# language were developed. The purpose of the experiment was to study the acceleration achieved due to the recursive-parallel organization of calculations. Specially generated random regular graphs with various degrees of vertices were used as the initial data. A detailed description of the algorithm and experiment, as well as the results obtained, are also given.
Extraction of two-dimensional object locations using current techniques is a computationally intensive process. In this paper a parallel algorithm is presented that can specify the location of objects from edge streak...
详细信息
Extraction of two-dimensional object locations using current techniques is a computationally intensive process. In this paper a parallel algorithm is presented that can specify the location of objects from edge streaks produced by an edge operator. Best-first searches are carried out in a number of non-interacting and localized edge streak spaces. The outcome of each search is a hypothesis. Each edge streak votes for a single hypothesis; it may also take part in the formation of other hypotheses. A poll of the votes determined the stronger hypotheses. The algorithm can be used as a ❉ end to a visual pattern recognition system where features are extracted from the hypothesized object boundary or from the area localized by the hypothesized boundary. Experimental results from a biomedical domain are presented.
暂无评论