检索结果-内蒙古大学图书馆

SOLVING combinatorial SEARCH problems BY INTELLIGENT BACKTRACKING

INFORMATION PROCESSING LETTERS 1981年第1期12卷 36-39页

作者： BRUYNOOGHE, M Katholieke Universiteit Leuven Afdeling Toegepaste Wiskunde en Programmatie B-3030 Heverlee Belgium

Many combinatorial search problems consist of finding values for a set of variables which have a known set of possible values and where the solution has to satisfy a set of constraints. Traditional backtracking can solve these problems by enumerating all tuples in some order and looking to see if they satisfy the constraints. A new method is proposed, which improves backtracking behavior at the cost of an increase in space. The method analyzes the occurring conflicts and takes the appropriate actions to delay their reappearance. The method attempts to execute all generators and constraints, and diverges from traditional backtracking methods when a conflict arises. The derivation of minimal conflictsets provides more accurate backtracking behavior.

关键词： Artificial intelligence combinatorial problems

来源：评论

学校读者我要写书评

暂无评论

Computational Complexity Analysis and Algorithm Design for combinatorial Optimization problems

Computational Complexity Analysis and Algorithm Design for C...

引用

3rd International Conference on Networking and Computing (ICNC)

作者： Watanabe, Toshimasa Hiroshima Univ Grad Sch Engn Higashihiroshima 724 Japan

The paper shows summary of the author's research subjects from 1973 through 2012. Additional explanation on these subjects and related references are omitted because of space limitation. They will be given at pres... 详细信息

ISBN: (纸本)9780769548937

关键词： combinatorial problems Computational Complexity Analysis Algorithm Design Graph Connectivity Petri Nets

来源：评论

学校读者我要写书评

暂无评论

Maximizing Expected Utility for Stochastic combinatorial Optimization problems

Maximizing Expected Utility for Stochastic Combinatorial Opt...

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Li, Jian Deshpande, Amol Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China Univ Maryland Dept Comp Sci College Pk MD 20742 USA

ISBN: (纸本)9780769545714

We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings over probabilistic graphs, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk-averse or risk-prone behaviors, and instead we consider a more general objective which is to maximize the expected utility of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). We show that we can obtain a polynomial time approximation algorithm with additive error epsilon for any epsilon > 0, if there is a pseudopolynomial time algorithm for the exact version of the problem (This is true for the problems mentioned above) and the maximum value of the utility function is bounded by a constant. Our result generalizes several prior results on stochastic shortest path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems.

关键词： Approximation algorithms Approximation methods Fourier series Optimization Polynomials Random variables Vectors combinatorial problems knapsack problems optimisation polynomial approximation polynomial time approximation algorithm stochastic combinatorial

来源：评论

学校读者我要写书评

暂无评论

combinatorial flexibility problems and their computational complexity

引用

Electronic Notes in Discrete Mathematics 2008年第C期30卷 303-308页

作者： Aguilera, Néstor E. Leoni, Valeria A. Nasini, Graciela L. CONICET and UNL. IMAL/INTEC 3000 Santa Fe Güemes 3450 Argentina CONICET UNR Depto de Matemática 2000 Rosario Av. Pellegrini 250 Argentina

The concept of flexibility-originated in the context of heat exchanger networks-is associated with a substructure which guarantees the performance of the original structure, in a given range of possible states. We extend this concept to combinatorial optimization problems, and prove several computational complexity results in this new framework. Under some monotonicity conditions, we prove that a combinatorial optimization problem polynomially transforms to its associated flexibility problem, but that the converse need not be true. In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids. We also prove that, when relaxing in different ways the matroid structure, the flexibility problems become NP-complete. This fact is shown by proving the NP-completeness of the flexibility problems associated with the Shortest Path, Minimum Cut and Weighted Matching problems. © 2008 Elsevier B.V. All rights reserved.

关键词： combinatorial problems computational complexity flexibility

来源：评论

学校读者我要写书评

暂无评论

An incremental model for combinatorial maximization problems

引用

5th International Workshop on Experimental Algorithms (WEA 2006)

作者： Hartline, Jeff Sharp, Alexa Cornell Univ Ithaca NY 14853 USA

ISBN: (纸本)3540345973

Many combinatorial optimization problems aim to select a subset of elements of maximum value subject to certain constraints. We consider an incremental version of such problems, in which some of the constraints rise over time. A solution is a sequence of feasible solutions, one for each time step, such that later solutions build on earlier solutions incrementally. We introduce a general model for such problems, and define incremental versions of maximum flow, bipartite matching, and knapsack. We find that imposing an incremental structure on a problem can drastically change its complexity. With this in mind, we give general yet simple techniques to adapt algorithms for optimization problems to their respective incremental versions, and discuss tightness of these adaptations with respect to the three aforementioned problems.

关键词： analysis of algorithms approximation techniques combinatorial problems network analysis online problems

来源：评论

学校读者我要写书评

暂无评论

SUPER-HEURISTICS AND THEIR APPLICATIONS TO combinatorial problems

引用

Asian Journal of Control 2008年第1期1卷

作者： Tak Wing Edward Lau Yu-Chi Ho Division of Engineering and Applied Sciences Harvard University Cambridge MA02138 U.S.A. Yu-Chi (Larry) Ho received his S.B. and S.M. degrees in Electrical Engineering from M.I.T. and his Ph.D. in Applied Mathematics from Harvard University. Except for three years of full time industrial work he has been on the Harvard Faculty. Since 1969 he has been Gordon McKay Professor of Engineering and Applied Mathematics. In 1988 he was appointed to the T. Jefferson Coolidge Chair in Applied Mathematics and Gordon McKay Yu-Chi (Larry) Ho received his S.B. and S.M. degrees in Electrical Engineering from M.I.T. and his Ph.D. in Applied Mathematics from Harvard University. Except for three years of full time industrial work he has been on the Harvard Faculty. Since 1969 he has been Gordon McKay Professor of Engineering and Applied Mathematics. In 1988 he was appointed to the T. Jefferson Coolidge Chair in Applied Mathematics and Gordon McKay Professor of Engineering at Harvard and as visiting professor to the Cockrell Family Regent's Chair in Engineering at the University of Texas Austin. He has published over 120 articles and three books one of which (co-authored with A.E. Bryson Jr.) has been translated into both Russian and Chinese and made the list of Citation Classics as one of the most referenced works on the subject of optimal control. He is on the editorial boards of several international journals and is the editor-in-chief of the new international Journal on Discrete Event Dynamic Systems. He is the recipient of various fellowships and awards including the Guggenheim (1970) and the IEEE Field Award for Control Engineering and Science (1989) the Chiang Technology Achievement Award (1993). He is a fellow of IEEE a Distinguished Member of the Control Systems Society and a member of the U.S. National Academy of Engineering. In addition to serving on various governmental and industrial panels and professional society administrative bodies he was the President of the IEEE Robotics & Automation Society in 1988

combinatorial problems are known to be difficult because of the shear size of the solution space and the lack of polynomial time algorithms to “solve” them. Heuristics are often devised to produce acceptable solutions in an affordable time. In this paper, we propose a method called super-heuristic that expands the capabilities of heuristics using randomization and sampling techniques. We submit that heuristics are in general strategies that map from available information of a problem instance to decisions in solution constructions/improvement. We show that it is important to utilize the information effectively in the randomization process. More importantly, the possibility of randomization around a heuristic spells out the demarcation between the roles of human and machines in complex optimization problems.

关键词： combinatorial problems heuristics randomization and sampling techniques man-machine interactions

来源：评论

学校读者我要写书评

暂无评论

The design and implementation of a reconfigurable processor for problems of combinatorial computation

引用

JOURNAL OF SYSTEMS ARCHITECTURE 2003年第4-6期49卷 211-226页

作者： Skliarova, I Ferrari, AB Univ Aveiro Dept Elect & Telecommun IEETA P-3810193 Aveiro Portugal

The paper analyses different techniques that might be employed in order to solve various problems of combinatorial optimization and argues that the best results can be achieved by the use of software running on a general-purpose computer together with an FPGA-based reconfigurable co-processor. It suggests an architecture for a combinatorial co-processor that is based on hardware templates and consists of reconfigurable functional and control units. Finally the paper demonstrates how the co-processor can be applied to two practical applications formulated over discrete matrices, the Boolean satisfiability and covering problems. (C) 2003 Elsevier B.V. All rights reserved.

关键词： reconfigurable combinatorial processor hardware template combinatorial problems

来源：评论

学校读者我要写书评

暂无评论

Lower and upper bounds on graph communicabilities

引用

INFORMATION PROCESSING LETTERS 2025年 187卷

作者： Ghodrati, Amir Hossein Hosseinzadeh, Mohammad Ali Shahid Rajaee Teacher Training Univ Fac Sci Dept Math Tehran Iran Amol Univ Special Modern Technol Fac Engn Modern Technol Amol Iran

In this paper, some lower and upper bounds for the subgraph centrality and communicability of a graph are proved. The expected value of the normalized total communicability of a random G(n, p) graph is also considered and asymptotically determined. Moreover, some computational results are presented to compare the bounds obtained in this paper with some other bounds in the literature.

关键词： Matrix exponential Communicability Subgraph centrality Eigenvalues combinatorial problems

来源：评论

学校读者我要写书评

暂无评论

Enhancing Reptile Search Algorithm Performance for the Knapsack Problem with Integration of Chaotic Map 23rd

Enhancing Reptile Search Algorithm Performance for the Knaps...

引用

23rd Mexican International Conference on Artificial Intelligence

作者： Barrera-Garcia, Jose Cisternas-Caneo, Felipe Crawford, Broderick Soto, Ricardo Becerra-Rozas, Marcelo Giachetti, Giovanni Monfroy, Eric Pontificia Univ Catolica Valparaiso Valparaiso Chile Univ Andres Bello Santiago Chile Univ Angers LERIA Angers France

ISBN: (纸本)9783031755422;9783031755439

This study investigates the binarization process of the Reptile Search Algorithm (RSA) using chaotic maps to solve the Knapsack Problem. We evaluate RSA, Particle Swarm Optimization (PSO), and Grey Wolf Optimizer (GWO) using the S4 transfer function with four binarization strategies: standard, standard with chaotic maps, elitist, and elitist with chaotic maps. Experimental results show that standard binarization strategies, particularly RSA with standard binarization rule (STD) and RSA with standard binarization rule with a chaotic map (STD SINE), consistently outperform elitist strategies across various Knapsack problem instances. Including chaotic maps, especially the sine chaotic map, slightly improves performance. Convergence analysis reveals that standard binarization ensures steady and strong convergence, while elitist binarization accelerates convergence but may risk settling on local optima early. This research highlights the importance of selecting appropriate binarization strategies and suggests further exploration of chaotic maps to enhance the performance of metaheuristic algorithms in solving binary combinatorial optimization problems.

关键词： Reptile Search Algorithm combinatorial problems Binarization Schemes Chaotic Maps Metaheuristics

来源：评论

学校读者我要写书评

暂无评论

ON THE RELATIONSHIP BETWEEN THE DIAMETER AND THE SIZE OF A BOUNDARY OF A DIRECTED GRAPH

引用

INFORMATION PROCESSING LETTERS 1994年第5期50卷 277-282页

作者： JIMBO, S MARUOKA, A Department of Information Engineering Faculty of Engineering Tohoku University Sendai 980 Japan

A family of expanding graphs is useful to make many kind of networks efficient, as Ajtai et al. constructed sorting networks of depth 0(log n) with it. On the other hand, Klawe showed that particular families of directed graphs obtained from a finite number of one-dimensional linear functions, which play important roles in constructing some kind of networks or generating random numbers, cannot be families of expanding graphs. Moreover, Klawe gave a conjecture concerning a lower bound of the amount of expanding property of these families. Maass gave a partial answer to the conjecture. In this paper, a theorem that states the relationship between the diameter and the size of a boundary in a directed graph is proved. An answer to Klawe's conjecture is also obtained from this theorem. The answer is more suitable than Maass's one.

关键词： combinatorial problems EXPANDING GRAPHS DIAMETER BOUNDARIES LINEAR FUNCTIONS

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：