| 一种基于稀疏优化的数独求解新方法 |
| |
| 引用本文： | 张煜东 王水花 霍元恺 吴乐南. 一种基于稀疏优化的数独求解新方法[J]. 南京信息工程大学学报, 2011, 3(1): 23-27 |
| |
| 作者姓名： | 张煜东 王水花 霍元恺 吴乐南 |
| |
| 作者单位： | 东南大学,信息科学与工程学院,南京,210044 |
| |
| 基金项目： | 资助项目国家自然科学基金 |
| |
| 摘 要： | 为了更好地求解数独问题,提出一种新的求解方法:采用实数编码去除整数约束,同时采用0范数作为目标函数来保证解的稀疏性.在此基础上,根据RIP(Restricted Isometry Property)与KGG(Kashin Garnaev Gluskin)条件,用1范数近似0范数.最后引入松弛矢量,使1范数转换为一个凸线性规划问题.采用主时偶内点法求解该线性规划问题.实验表明:该方法对简单、中等、困难、恶魔级别的数独,可达到100%成功率;对最小提示数目的17数独,达到86.4%的成功率.另外,该算法耗时短,且与数独的难度无关.因此,该算法在成功率与运行时间上均优于约束规划与Sinkhorn算法.
|
| 关 键 词： | 数独 约束规划 整数规划 线性规划 主对偶内点法 |
| 收稿时间： | 2010-07-20 |
A novel sudoku solving method based on sparse optimization |
| |
| ZHANG Yudong,WANG Shuihua,HUO Yuankai,WU Lenan. A novel sudoku solving method based on sparse optimization[J]. Journal of Nanjing University of Information Science & Technology, 2011, 3(1): 23-27 |
| |
| Authors: | ZHANG Yudong WANG Shuihua HUO Yuankai WU Lenan |
| |
| Affiliation: | Engineering,Southeast University,Nanjing |
| |
| Abstract: | |
| |
| Keywords: | sudoku constraint programming integer programming linear programming primal dual interior point metho |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《南京信息工程大学学报》浏览原始摘要信息 |
|
点击此处可从《南京信息工程大学学报》下载全文 |
|
