学位论文 > 优秀研究生学位论文题录展示

数独的难度衡量、生成及微粒群算法

作　者: 张艳宗
导　师: 杨启帆
学　校: 浙江大学
专　业: 运筹学与控制论
关键词: 数独难度生成微粒群算法相变
分类号: O157.1
类　型: 硕士论文
年　份: 2009年
下　载: 310次
引　用: 0次
阅　读: 论文下载

内容摘要

数独是近五年来国际上最热门的组合问题之一,国内研究才刚开始。本文从三个方面,即数独的难度衡量、生成,以及数独的微粒群算法研究数独。全文共分为五章。第一章是绪论部分,主要介绍数独的定义、来源、相关概念和数独已有的一些研究成果。第二章给出影响数独难度的几种因素,分析候选数为主要因素,再根据其构造加权规范函数WNF(P),计算数值衡量数独难度。为生成数独,第三章首先考虑数独终盘的生成算法,根据终盘给出生成难度在所给区间内数独的基于数独终盘和逻辑推理的数字删除模型,分析比较此方法和其他方法的复杂性。第四章简单介绍了几种求解数独的已知方法,回溯法、逻辑推理法、基于图着色问题的数独解法、基于SAT问题的数独解法、遗传算法等,分析各算法复杂性或应用范围。综合分析已有启发式算法后,第五章提出了数独的微粒群算法,首先仔细介绍微粒群算法的原理,再构造粒子的速度、位置以使此算法可应用于解数独这一离散问题,并进行相关算法实验,将此算法实验结果与蚁群算法、和声算法进行比较。另外,我们利用微粒群算法求解某类按随机生成的数独,分析比较其与模拟退火算法在相变中的情况。

全文目录

摘要  4-5
Abstract  5-6
目录  6-8
第一章绪论  8-13
  1.1 数独概述  8
  1.2 数独历史  8-9
  1.3 定义术语  9-10
  1.4 数独的逻辑推理方法  10
  1.5 数独的变形  10-11
  1.6 关于数独以前的工作  11-12
  1.7 论文结构  12-13
第二章数独难度衡量  13-18
  2.1 影响数独难度的几大因素  13-15
  2.2 WNF(P)的计算  15-18
第三章数独的生成  18-27
  3.1 生成数独终盘  18-22
  3.2 基于数独终盘的任意插入数字模型  22-23
  3.3 基于数独终盘的任意删除数字模型  23-24
  3.4 基于数独终盘和逻辑推理的数字删除模型  24-26
  3.5 数独变换增加数独组合个数  26-27
第四章求解数独的已知方法  27-30
  4.1 回溯法  27
  4.2 逻辑推理法  27-28
  4.3 基于图着色问题的数独解法  28
  4.4 基于SAT问题的数独解法  28
  4.5 遗传算法  28-30
第五章求解数独的微粒群算法  30-40
  5.1 粒子群算法介绍  30
  5.2 微粒群算法基本原理  30-31
  5.3 数独求解的微粒群算法表示  31-36
  5.4 算法实验  36-38
  5.5 算法展望  38-40
参考文献  40-43
致谢  43

数独的难度衡量、生成及微粒群算法

内容摘要

全文目录

相似论文