一类最小覆盖问题

对于任意给定的平行四边形,确定了与其相似的直径为1的三角形集族的最小平行四边形覆盖.     

一类组合恒等式的定义证明

对于组合数的两个性质：Cn^m=Cn^n-m和Cn 1^m=Cn^m Cn^m-1，教材采用了两种方法证明．     

组合学的一个新概念--圆组合

1962年笔者在《数学通报》指出下述结果[1 ] :设n ,k为自然数 ,a ,b为实数或复数时 ,就有等价恒等式(a b) n =∑nk=0nk an-kbk,(二项式定理 )an bn =∑[n2 ]k=0( - 1 ) k nk (a b) n- 2k(ab) k,(等价二项式定理 )其中记号nk =n(n- 1 ) (n- 2 )… (n -k 1 )k!,nk =n(n -k- 1 ) (n -k- 2 )…(n- 2k 1 )k!.同时还发现等价恒等式的数字表、证明、性质以及应用上具有相似之处 .由于 nk 是组合记号 ,推测 nk 可能是另一组合记号 ,于是猜想 nk 中蕴藏着组合学的一个新概念 .40年韶光弹指过 ,近年笔者探讨孪生组合等式的问题[2 ,3,4] ,才能清楚地…     

三角形覆盖问题的推广

在www.gzjzes.com的数学论坛中,讨论着这样的一条题,笔者见后,觉得很有启发,特整理证明讨论如下.题目:平面上有2004个不共线的点,每3个点都构成面积不大于1的三角形.求证:这2004个点可以被一个面积不大于4的三角形覆盖.证明选取构成所有三角形中面积最大的一个,记为△ABC,由条件可知S△ABC<1,依次过A,B,C作BC,AC,AB的平行线,三线交于D,E,F.下证明结论成立.图1如图1,运用反证法,假设2004个点中有一点G在△DEF外,(不妨设在边EF外,在边DE,DF外的情况类同),则有S△BCG>S△ABC,这与条件S△ABC为最大的三角形矛盾,所以假设不成立…     

一类最优组合批处理码

Ishai等人首先提出了批处理码的概念,Peterson等人从纯组合的观点定义了(n,N,k,m)-组合批处理码:即是一个n元集和它的m个子集组成的集合系统,对于整数尼,满足任意k个元素都能从每个子集中至多读取1个元素(可以一般化为t个元素)来取得,此时m个子集中元素的总数为N.对给定的参数n,k,m,确定N的最小值N(n,k,m)是该问题研究的中心内容,它不仅具有理论意义,而且有着重要的使用价值.到目前为止,除了一些极特殊的参数以外,当k≥5,m+3≤n(m k-2)时,N(n,k,m)的值还没有被确定.本文给出了N(m+3,5,m)=m+11(m≥7),N(9,5,6)=18,N(m+3,6,m)=m+13(m≥8),N(10,6,7)=21.得到的结果部分解决了:Peterson等人提出的未解决问题.     

求有限集合覆盖的构造方法

在近似算法领域,集合覆盖问题是研究的比较早和比较透彻的问题之一.文中解决与经典SCP不同的另一问题,针对有限集合覆盖的构造,提出一种构造有限集合上的集合覆盖的算法,并且给出了该算法的完备性证明.该算法简单有效,是一种用于构造集合覆盖的规范方法.     

一个组合问题的解法

问题在某次数学测验中,学号为i(i=1,2,3,4)的四位同学的考试成绩f(i)∈{85,89,90,91,95,99},且满足f(1)≤f(2)≤f(3)≤f(4),则这四位同学的考试成绩的所有可能情况的种数为()A.15种B.112种C.126种D.132种此类问题常见于高三的复习资料中,一般同学解这个问题多用分类讨论法,即讨     

一个组合问题的研究

此文基本上还是“穷举法” ,只是稍加分类 ;五类中只选择了最容易的一个小类详细算出 ,四类复杂的情形只公布了他的计算结果 ,无法验证是否正确 ,这是赵慈庚先生五年多以前提出的问题 ,至今没有解答 .发表此文 ,作为抛砖引玉     

排列和组合问题

排列和组合问题是组合数学的基础，其应用非常广泛，特别是它解题思路的独特性，对于培养能力和开发智力有着不可替代的作用．     

一个组合问题的彻底解决

赵慈庚先生在《数学通报》1996年第8期提出了一个问题：“有24位老人，从76岁到99岁每岁1人，他们分三桌就餐，要每桌8人．且每桌年龄的和相等，问有多种分桌法”?《数学通报》2001年第11期上的《一个组合问题的研究》(刘洪元，孙兴家撰文．并称此文为文[1])用穷举法对这个问题     

Maximally Disjoint Solutions of the Set Covering Problem

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP-complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, extensive computational tests are given demonstrating the nature of these algorithms. These tests are carried out both on randomly generated problems and on problems found in the literature.     

基于改进遗传算法的集合覆盖问题

集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.     

A Meta-heuristic with Orthogonal Experiment for the Set Covering Problem

This paper reports an evolutionary meta-heuristic incorporating fuzzy evaluation for some large-scale set covering problems originating from the public transport industry. First, five factors characterized by fuzzy membership functions are aggregated to evaluate the structure and generally the goodness of a column. This evaluation function is incorporated into a refined greedy algorithm to make column selection in the process of constructing a solution. Secondly, a self-evolving algorithm is designed to guide the constructing heuristic to build an initial solution and then improve it. In each generation an unfit portion of the working solution is removed. Broken solutions are repaired by the constructing heuristic until stopping conditions are reached. Orthogonal experimental design is used to set the system parameters efficiently, by making a small number of trials. Computational results are presented and compared with a mathematical programming method and a GA-based heuristic.     

Two-phase method and Lagrangian relaxation to solve the Bi-Objective Set Covering Problem

This paper deals with the Bi-Objective Set Covering Problem, which is a generalization of the well-known Set Covering Problem. The proposed approach is a two-phase heuristic method which has the particularity to be a constructive method using the primal-dual Lagrangian relaxation to solve single objective Set Covering problems. The results show that this algorithm finds several potentially supported and unsupported solutions. A comparison with an exact method (up to a medium size), shows that many Pareto-optimal solutions are retrieved and that the other solutions are well spread and close to the optimal ones. Moreover, the method developed compares favorably with the Pareto Memetic Algorithm proposed by Jaszkiewicz.     

箱覆盖问题的半定松驰算法

箱覆盖问题是NP困难问题中的经典问题，得到了广泛地研究，九十年代以来，半定松驰策略被用来求解组合优化问题，取得了很好的结果[13]，本文首次给箱覆盖问题的半定松驰算法，算法的理论分析结果表明它适合于求解大规模的箱覆盖问题。     

A Covering Problem for Tori

The problem of covering an n-dimensional torus with n-dimensional grid graphs is studied. This is the dual problem of a packing problem concerning the capacity of a graph, which has been studied in information theory. It is related to several other problems as well, including weighted coverings, Kellers cube-tiling problem, and the recreational problem of how to obtain zero correct predictions in the football pools. Motivated by the last problem, bounds on the minimum size of such coverings are tabulated for q = 3, p = 2, and small n.AMS Subject Classification: 05C70, 94B25.     

Algorithms for the Set Covering Problem

The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.     

Solution techniques for the Large Set Covering Problem

Given a finite set E and a family F={E₁,…,E_m} of subsets of E such that F covers E, the famous unicost set covering problem (USCP) is to determine the smallest possible subset of F that also covers E. We study in this paper a variant, called the Large Set Covering Problem (LSCP), which differs from the USCP in that E and the subsets E_i are not given in extension because they are very large sets that are possibly infinite. We propose three exact algorithms for solving the LSCP. Two of them determine minimal covers, while the third one produces minimum covers. Heuristic versions of these algorithms are also proposed and analysed. We then give several procedures for the computation of a lower bound on the minimum size of a cover. We finally present algorithms for finding the largest possible subset of F that does not cover E. We also show that a particular case of the LSCP is to determine irreducible infeasible sets in inconsistent constraint satisfaction problems. All concepts presented in the paper are illustrated on the k-colouring problem which is formulated as a constraint satisfaction problem.     

Constraint Handling in Genetic Algorithms: The Set Partitioning Problem

In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling.A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems.We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions.     

一族Bloch函数的单叶半径与覆盖半径

研究了Bloch函数族B中的一个子族Bg,给出了Bg中函数的单叶半径.作为应用建立了Bg中函数的覆盖定理,从而刻画了Bg中函数的有关性质.