首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 171 毫秒
1.
Generation of Efficient Nested Loops from Polyhedra   总被引:1,自引:0,他引:1  
Automatic parallelization in the polyhedral model is based on affine transformations from an original computation domain (iteration space) to a target space-time domain, often with a different transformation for each variable. Code generation is an often ignored step in this process that has a significant impact on the quality of the final code. It involves making a trade-off between code size and control code simplification/optimization. Previous methods of doing code generation are based on loop splitting, however they have nonoptimal behavior when working on parameterized programs. We present a general parameterized method for code generation based on dual representation of polyhedra. Our algorithm uses a simple recursion on the dimensions of the domains, and enables fine control over the tradeoff between code size and control overhead.  相似文献   

2.
Consistency techniques for continuous constraints   总被引:1,自引:0,他引:1  
We consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing one single optimal solution, we address the problem of computing a compact representation of the space of all solutions admitted by the constraints. In particular, we show how globally consistent (also called decomposable) labelings of a constraint satisfaction problem can be computed.Our approach is based on approximating regions of feasible solutions by 2 k -trees, a representation commonly used in computer vision and image processing. We give simple and stable algorithms for computing labelings with arbitrary degrees of consistency. The algorithms can process constraints and solution spaces of arbitrary complexity, but with a fixed maximal resolution.Previous work has shown that when constraints are convex and binary, path-consistency is sufficient to ensure global consistency. We show that for continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of constraint satisfaction problems with continuous variables.  相似文献   

3.
Collision detection (CD) among complex objects in motion is an open question because of its algorithmic complexity. In this paper, we present a CD algorithm between a particle and a complex rigid solid. In order to represent solids, we use a simplicial covering scheme by means of 3‐simplices. With this representation system, complex polyhedra and closed triangle meshes can be represented and used in CD with a particle. A particle can be represented by a point, where the real dimensions of the particle are not important. This CD algorithm has been extended for a particle represented by a sphere which in turn represents an approximation to the particle dimensions. In order to efficiently classify the particles and the simplices of the polyhedra covering, we use a new hierarchical data structure named tetra‐tree that decomposes the space into tetra‐cones. These algorithms also use bounding volumes and temporal and geometric coherence, as well as incremental calculations in order to determine the collision in an efficient and exact way. Because of the use of sign operations with signed volumes and barycentric coordinates, we conclude that operations carried out using this method are more robust and efficient than those used in classic algorithms.  相似文献   

4.

An intuitionistic fuzzy soft set plays a significant role as a mathematical tool for mathematical modeling, system analysis and decision making. This mathematical tool gives more precision, flexibility and compatibility to the system when compared to systems that are designed using fuzzy graphs and fuzzy soft graphs. In this paper, we use intuitionistic fuzzy soft graphs and possibility intuitionistic fuzzy soft graphs for parameterized representation of a system involving some uncertainty. We present novel multiple-attribute decision-making methods based on an intuitionistic fuzzy soft graph and possibility intuitionistic fuzzy soft graph. We also present our methods as algorithms that are used in our applications.

  相似文献   

5.
We consider the problem of assigning transmission powers to the nodes of an ad hoc wireless network, so that the total power consumed is minimized and the resulting network is biconnected, i.e., there are at least two node-disjoint paths between any pair of nodes. Biconnected communication graphs are important to ensure fault tolerance, since ad hoc networks are used in critical application domains where failures are likely to occur. A mixed integer programming formulation of the problem can be exactly solved to optimality by a commercial solver only for moderately sized problems. We recall a mixed integer programming formulation that can be exactly solved to optimality by a commercial solver only for very moderately sized problems. We propose a quick greedy algorithm and a GRASP with path-relinking heuristic for solving real-life sized problems. Computational experiments involving practical issues such as energy consumption and interference have been performed and reported for problems with up to 800 nodes, illustrating the effectiveness and the efficiency of the new algorithms. Both the greedy algorithm and the GRASP heuristic outperformed the best heuristic in the literature for very large problem sizes.  相似文献   

6.
Minkowski sum is an important operation. It is used in many domains such as: computer-aided design, robotics, spatial planning, mathematical morphology, and image processing. We propose a novel algorithm, named the Contributing Vertices-based Minkowski Sum (CVMS) algorithm for the computation of the Minkowski sum of convex polyhedra. The CVMS algorithm allows to easily obtain all the facets of the Minkowski sum polyhedron only by examining the contributing vertices—a concept we introduce in this work, for each input facet. We exploit the concept of contributing vertices to propose the Enhanced and Simplified Slope Diagram-based Minkowski Sum (ESSDMS) algorithm, a slope diagram-based Minkowski sum algorithm sharing some common points with the approach proposed by Wu et al. [Wu Y, Shah J, Davidson J. Improvements to algorithms for computing the Minkowski sum of 3-polytopes. Comput Aided Des. 2003; 35(13): 1181-92]. The ESSDMS algorithm does not embed input polyhedra on the unit sphere and does not need to perform stereographic projections. Moreover, the use of contributing vertices brings up more simplifications and improves the overall performance. The implementations for the mentioned algorithms are straightforward, use exact number types, produce exact results, and are based on CGAL, the Computational Geometry Algorithms Library. More examples and results of the CVMS algorithm for several convex polyhedra can be found at http://liris.cnrs.fr/hichem.barki/mksum/CVMS-convex.  相似文献   

7.
Nowadays, mixed-model assembly line is used increasingly as a result of customers’ demand diversification. An important problem in this field is determining the sequence of products for entering the line. Before determining the best sequence of products, a new procedure is introduced to choose important orders for entering the shop floor. Thus the orders are sorted using an analytical hierarchy process (AHP) approach based on three criteria: critical ratio of each order (CRo), Significance degree of customer and innovation in a product, while the last one is presented for the first time. In this research, six objective functions are presented: minimizing total utility work cost, total setup cost and total production rate variation cost are the objectives which were presented previously, another objective is minimizing total idle cost, meanwhile two other new objectives regarding minimizing total operator error cost and total tardiness cost are presented for the first time. The total tardiness cost tries to choose a sequence of products that minimizes the tardiness cost for customers with high priority. First, to check the feasibility of the model, GAMS software is used. In this case, GAMS software could not search all of the solution space, so it is tried in two stages and because this problem is NP-hard, particle swarm optimization (PSO) and simulated annealing (SA) algorithms are used. For small sized problems, to compare exact method with proposed algorithms, the problem must be solved using meta-heuristic algorithms in two stages as GAMS software, whereas for large sized problems, the problem can be solved in two ways (one stage and two stages) by using proposed algorithms; the computational results and pairwise comparisons (based on sign test) show GAMS is a proper software to solve small sized problems, whereas for a large sized problem the objective function is better when solved in one stage than two stages; therefore it is proposed to solve the problem in one stage for large sized problems. Also PSO algorithm is better than SA algorithm based on objective function and pairwise comparisons.  相似文献   

8.
Genetic algorithms play a significant role, as search techniques forhandling complex spaces, in many fields such as artificial intelligence, engineering, robotic, etc. Genetic algorithms are based on the underlying genetic process in biological organisms and on the naturalevolution principles of populations. These algorithms process apopulation of chromosomes, which represent search space solutions,with three operations: selection, crossover and mutation.Under its initial formulation, the search space solutions are coded using the binary alphabet. However, the good properties related with these algorithms do not stem from the use of this alphabet; other coding types have been considered for the representation issue, such as real coding, which would seem particularly natural when tackling optimization problems of parameters with variables in continuous domains. In this paper we review the features of real-coded genetic algorithms. Different models of genetic operators and some mechanisms available for studying the behaviour of this type of genetic algorithms are revised and compared.  相似文献   

9.
Abstract

The design and implementation of a library of C-code procedures to perform operations on rational polyhedra is described. The library supports intersection, union, difference, simplification in context, convex hull, affine image, affine preimage, and computation of dual forms. Since not all of these functions are closed over polyhedra, the library is extended to operate on finite unions of polyhedra. The major design decisions made during the implementation of the library are discussed. The data structure used for representing finite unions of polyhedra is developed and validity rules for the representation of polyhedra are derived. And finally, the algorithms used to implement the various functions in the library are presented.  相似文献   

10.
This paper presents a general method for exact distance computation between convex objects represented as intersections of implicit surfaces. Exact distance computation algorithms are particularly important for applications involving objects that make intermittent contact, such as in dynamic simulations and in haptic interactions. They can also be used in the narrow phase of hierarchical collision detection. In contrast to geometric approaches developed for polyhedral objects, we formulate the distance computation problem as a convex optimization problem. We use an interior point method to solve the optimization problem and demonstrate that, for general convex objects represented as implicit surfaces, interior point approaches are globally convergent, and fast in practice. Further, they provide polynomial-time guarantees for implicit surface objects when the implicit surfaces have self-concordant barrier functions. We use a primal-dual interior point algorithm that solves the Karush-Kuhn-Tucker (KKT) conditions obtained from the convex programming formulation. For the case of polyhedra and quadrics, we establish a theoretical time complexity of O(n1.5), where n is the number of constraints. We present implementation results for example implicit surface objects, including polyhedra, quadrics, and generalizations of quadrics such as superquadrics and hyperquadrics, as well as intersections of these surfaces. We demonstrate that in practice, the algorithm takes time linear in the number of constraints, and that distance computation rates of about 1 kHz can be achieved. We also extend the approach to proximity queries between deforming convex objects. Finally, we show that continuous collision detection for linearly translating objects can be performed by solving two related convex optimization problems. For polyhedra and quadrics, we establish that the computational complexity of this problem is also O(n1.5).  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号