优化搜索原则创建数独模型

针对目前流行的数独游戏,建立数学模型,给出了创建不同难度的数独游戏的算法.首先,模型创造性地利用了数独游戏的解题算法的逆过程来创建一个完整的终盘.在此基础上,进一步优化创建终盘的搜索法则,保证了所采用的算法复杂度最小.最后,移去已有终盘上的一些格子以得到一道数独题的初盘,并在此过程中始终保证该问题有且只有唯一解.同时,基于人性化的原则,我们通过玩家使用的解题技巧和频率来划分难度.根据划分的难度等级,依次创建不同难度的数独游戏.     

数海星空——神奇的9阶数独幻方

数独幻方是集数独和幻方为一体,是数独的升华和发展。其性质奥妙无穷:两图分别是一个大九宫图,各有9×9=81个小方格,用粗实线把大九宫图划成9个"九宫格",再把1～9九个数字分别填入9个小方格内,从而会出现以下七种独特数字关系:1.每一行都是"1～9",9个数字不重复;2.每一列都是"1～9",9个数字不重复;3.每条对角线都是"1～9",9个数字不重复;4.每个粗实线内的九宫格,都是"1～9",9个数字不重复;     

一种无人机侦察航迹分层规划方法

给出了一个通用可行的无人机侦察航迹分层规划方法,并应用到第十三届"华为杯"全国研究生数学建模竞赛A题第一问中.将无人机侦察航迹规划问题划分为四个层次,从上至下分别是目标群间侦察顺序优化,目标群内各目标侦察顺序优化,侦察点位优化,转弯设计,依次求解获得侦察航迹.通过分层解算方法既有效控制了算法复杂度,又能在确保满足复杂约束的同时优化无人机在敌方雷达探测区域内的暴露时间.     

求解集束型装备调度问题的改进遗传算法

针对半导体制造中的有滞留时间约束集束型装备调度问题,以最小化生产周期为目标,建立问题的数学模型,提出基于机械手搬运作业顺序编码的改进遗传算法.设计基于禁止区间法的启发式构造算法以生成初始种群,避免了不可行染色体的产生;通过互换染色体中处于机械手全等待的基因位置,以及基于图论的不可行解修复技术改进局部搜索效率,避免冗余迭代和陷入局部最优等现象.与遗传算法、混合量子进化算法的仿真实验比较,验证了提出算法的有效性和鲁棒性.     

找回了漏的解

原题:已知直线l_1:x+3y-6=0,l_2:y=kx+b,若l_1、l_2与x轴、y轴正半轴围成的四边形有外接圆,则k=____.这是解析几何教学中,教师经常使用到的例(习)题.此题难度不大,主要考查直线的斜率、四点共圆等知识点和数形结合的思想.在执教过程中,笔者发现:在参考资料上提供的和网上搜索的答案均为3,解     

数海星空——神奇的25阶数独幻方

<正>数独幻方是数独和幻方的有效结合,利用珠心算功能,来研究和探索数字科学领域中的神奇奥秘,使此幻方品位和境界得到了进一步提升,正所谓:数字世界、奥妙无穷。此幻方好似天上的星星布满天空,相互依存,相互依赖,令人赏心悦目,变幻莫测。特性如下:1.每行1至25个数字不重复,和都等于325;2.每列1至25个数字不重复,和都等于325;     

线性分式多乘积问题的?-近似算法

本文针对线性分式多乘积问题提出一个近似算法;该算法主要通过非均匀搜索网格结点,将等价问题转化为多项式个与结点参量相关的线性子问题,通过求解这些子问题获得原问题的全局近似最优解.本文不仅从理论上证明了算法的收敛性,且通过算例验证算法的可行性与有效性,最终给出算法的计算复杂度.     

基于免疫原理的蚁群系统及其应用

针对蚁群算法在寻优过程中容易出现停滞现象,同意在该算法中引入免疫机制,将待求解问题看成抗原,而问题的解看成抗体,通过基于浓度的选择机制和多样性保持策略来提高蚁群算法的全局搜索能力和避免停滞现象.对TSP问题的仿真实验结果表明,该算法极大地提高了搜索能力和避免了停滞现象.     

此类问题亦可用余弦定理来解

新编教材数学第一册 (下 ) (Ｐ1 2 8) ,在总结正弦定理的应用时指出 :已知三角形两边和其中一边的对角 ,求解三角形其余元素时 ,可利用正弦定理 .而在 (Ｐ1 30 )总结余弦定理的应用时指出 ,利用余弦定理 ,可以解决以下两类有关三角形的问题 :(1)已知三边 ,求三个角 ;(2 )已知两边和它们的夹角 ,求第三边和其它两个角 .在这里给学生造成了一种错觉 ,似乎已知三角形两边和其中一边的对角 ,求解三角形其余元素这类问题 ,只能用正弦定理来解 ,从而忽视了此类问题亦可用余弦定理来解 ,甚至可能用余弦定理来解反而比用正弦定理来解更方便、更简单 …     

用好中点巧解几何题

近几年的中考,几何题难度有所增大,错综复杂的已知条件和图形变换,让学生望而生畏.其实,分析题目的核心条件,用好关键条件,可以起到事半功倍的效果.现就日照市的一道中考几何题来看,紧紧抓住条件中的"中点"进行联想,挖掘中点的意义和功用,巧解此题.     

Solving jigsaw puzzles by computer

An algorithm to assemble large jigsaw puzzles using curve matching and combinatorial optimization techniques is presented. The pieces are photographed one by one and then the assembly algorithm, which uses only the puzzle piece shape information, is applied. The algorithm was experimented successfully in the assembly of 104-piece puzzles with many almost similar pieces. It was also extended to solve an intermixed puzzle assembly problem and has successfully solved a 208-piece puzzle consisting of two intermixed 104-piece puzzles. Previous results solved puzzles with about 10 pieces, which were substantially different in shape.Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

A comparison of several enumerative algorithms for Sudoku

Sudoku is a puzzle played of an n × n grid Open image in new window where n is the square of a positive integer m. The most common size is n=9. The grid is partitioned into n subgrids of size m × m. The player must place exactly one number from the set N={1, …, n} in each row and each column of Open image in new window as well as in each subgrid. A grid is provided with some numbers already in place, called givens. In this paper, some relationships between Sudoku and several operations research problems are presented. We model the problem by means of two mathematical programming formulations. The first one consists of an integer linear programming model, while the second one is a tighter non-linear integer programming formulation. We then describe several enumerative algorithms to solve the puzzle and compare their relative efficiencies. Two basic backtracking algorithms are first described for the general Sudoku. We then solve both formulations by means of constraint programming. Computational experiments are performed to compare the efficiency and effectiveness of the proposed algorithms. Our implementation of a backtracking algorithm can solve most benchmark instances of size 9 within 0.02?s, while no such instance was solved within that time by any other method. Our implementation is also much faster than an existing alternative algorithm.     

Cryptographic puzzles and DoS resilience,revisited

Cryptographic puzzles (or client puzzles) are moderately difficult problems that can be solved by investing non-trivial amounts of computation and/or storage. Devising models for cryptographic puzzles has only recently started to receive attention from the cryptographic community as a first step toward rigorous models and proofs of security of applications that employ them (e.g. Denial-of-Service (DoS) resistance). Unfortunately, the subtle interaction between the complex scenarios for which cryptographic puzzles are intended and typical difficulties associated with defining concrete security easily leads to flaws in definitions and proofs. Indeed, as a first contribution we exhibit shortcomings of the state-of-the-art definition of security of cryptographic puzzles and point out some flaws in existing security proofs. The main contribution of this paper are new security definitions for puzzle difficulty. We distinguish and formalize two distinct flavors of puzzle security which we call optimality and fairness and in addition, properly define the relation between solving one puzzle versus solving multiple ones. We demonstrate the applicability of our notions by analyzing the security of two popular puzzle constructions. We briefly investigate existing definitions for the related notion of security against DoS attacks. We demonstrate that the only rigorous security notion proposed to date is not sufficiently demanding (as it allows to prove secure protocols that are clearly not DoS resistant) and suggest an alternative definition. Our results are not only of theoretical interest: the better characterization of hardness for puzzles and DoS resilience allows establishing formal bounds on the effectiveness of client puzzles which confirm previous empirical observations. We also underline clear practical limitations for the effectiveness of puzzles against DoS attacks by providing simple rules of thumb that can be easily used to discard puzzles as a valid countermeasure for certain scenarios.     

A novel hybrid genetic algorithm for solving Sudoku puzzles

In this article, a novel hybrid genetic algorithm is proposed. The selection operator, crossover operator and mutation operator of the genetic algorithm have effectively been improved according to features of Sudoku puzzles. The improved selection operator has impaired the similarity of the selected chromosome and optimal chromosome in the current population such that the chromosome with more abundant genes is more likely to participate in crossover; such a designed crossover operator has possessed dual effects of self-experience and population experience based on the concept of tactfully combining PSO, thereby making the whole iterative process highly directional; crossover probability is a random number and mutation probability changes along with the fitness value of the optimal solution in the current population such that more possibilities of crossover and mutation could then be considered during the algorithm iteration. The simulation results show that the convergence rate and stability of the novel algorithm has significantly been improved.     

Construction of meaning: urban elementary students’ interpretation of geometric puzzles

Mathematical puzzles have long been employed by parents and teachers to augment the standard mathematics curriculum. This paper reports on a study of urban elementary students engaged in the solution of mathematical puzzles. The work confirms that, given the opportunity, these students will construct their own, logically consistent, interpretations of the puzzle clues. In particular, these students used self-generated rules about alignment and orientation to construct meaning in ambiguous clues. Such exercises in logic bring to light the value of student approaches to problem solving, and the possibility of using these approaches as building blocks from which students might construct knowledge in the standard curriculum.     

Sliding puzzles and rotating puzzles on graphs

Sliding puzzles on graphs are generalizations of the Fifteen Puzzle. Wilson has shown that the sliding puzzle on a 2-connected graph always generates all even permutations of the tiles on the vertices of the graph, unless the graph is isomorphic to a cycle or the graph θ₀ [R.M. Wilson, Graph puzzles, homotopy, and the alternating group, J. Combin. Theory Ser. B 16 (1974) 86–96]. In a rotating puzzle on a graph, tiles are allowed to be rotated on some of the cycles of the graph. It was shown by Scherphuis that all even permutations of the tiles are also obtainable for the rotating puzzle on a 2-edge-connected graph, except for a few cases. In this paper, Scherphuis’ Theorem is generalized to every connected graph, and Wilson’s Theorem is derived from the generalized Scherphuis’ Theorem, which will give a uniform treatise for these two families of puzzles and reveal the structural relation of the graphs of the two puzzles.     

Implementing pure adaptive search for global optimization using Markov chain sampling

The Pure Adaptive Search (PAS) algorithm for global optimization yields a sequence of points, each of which is uniformly distributed in the level set corresponding to its predecessor. This algorithm has the highly desirable property of solving a large class of global optimization problems using a number of iterations that increases at most linearly in the dimension of the problem. Unfortunately, PAS has remained of mostly theoretical interest due to the difficulty of generating, in each iteration, a point uniformly distributed in the improving feasible region. In this article, we derive a coupling equivalence between generating an approximately uniformly distributed point using Markov chain sampling, and generating an exactly uniformly distributed point with a certain probability. This result is used to characterize the complexity of a PAS-implementation as a function of (a) the number of iterations required by PAS to achieve a certain solution quality guarantee, and (b) the complexity of the sampling algorithm used. As an application, we use this equivalence to show that PAS, using the so-called Random ball walk Markov chain sampling method for generating nearly uniform points in a convex region, can be used to solve most convex programming problems in polynomial time.     

Properties, isomorphisms and enumeration of 2-Quasi-Magic Sudoku grids

A Sudoku grid is a 9×9 Latin square further constrained to have nine non-overlapping 3×3 mini-grids each of which contains the values 1–9. In Δ-Quasi-Magic Sudoku a further constraint is imposed such that every row, column and diagonal in each mini-grid sums to an integer in the interval [15−Δ,15+Δ]. The problem of proving certain (computationally known) results for Δ=2 concerning mini-grids and bands (rows of mini-grids) was posed at the British Combinatorial Conference in 2007. These proofs are presented and extensions of these provide a full combinatorial enumeration for the total number of completed 2-Quasi-Magic Sudoku grids. It is also shown that there are 40 isomorphism classes of completed 2-Quasi-Magic Sudoku grids.     

一种基于数独的新试验设计

通过研究数独方的构成与设计,建立了一种基于数独的新试验设计,给出了这种设计的数学模型与统计分析。该设计能安排单因素的n个水平,并能在行、列、块3个方向控制变异性。