按:   检索词:   从
   最新录用    过刊检索
一种基于稀疏优化的数独求解新方法
投稿时间:2010-07-20    点此下载全文
引用本文:张煜东 王水花 霍元恺 吴乐南.一种基于稀疏优化的数独求解新方法[J].南京信息工程大学学报,2011,(1):23~27
摘要点击次数: 2131
全文下载次数: 1349
作者单位E-mail
张煜东 王水花 霍元恺 吴乐南 东南大学信息科学与工程学院$南京$ zhangyudongnuaa@gmail.com 
基金项目:国家自然科学基金(60872075)"
中文摘要:为了更好地求解数独问题,提出一种新的求解方法:采用实数编码去除整数约束,同时采用0范数作为目标函数来保证解的稀疏性.在此基础上,根据RIP(Restricted Isometry Property)与KGG(Kashin Garnaev Gluskin)条件,用1范数近似0范数.最后引入松弛矢量,使1范数转换为一个凸线性规划问题.采用主对偶内点法求解该线性规划问题.实验表明:该方法对简单、中等、困难、恶魔级别的数独,可达到100%成功率;对最小提示数目的17数独,达到864%的成功率.另外,该算法耗时短,且与数独的难度无关.因此,该算法在成功率与运行时间上均优于约束规划与Sinkhorn算法
中文关键词:数独  约束规划  整数规划  线性规划  主对偶内点法
 
A novel sudoku solving method based on sparse optimization
Abstract:In order to solve the sudoku more efficiently,a novel approach was proposed.We employed the real number coding to get rid of the integer constraint,meanwhile used the L0 norm to guarantee the sparsity of the solution.Moreover,the L1 norm was used to approximate the L0 norm on the basis of RIP and KGG condition.Finally,the slack vectors were introduced to transfer the L1 norm into a convex linear programming problem,which was solved by the primal dual interior point method.Experiments demonstrate that this algorithm reach 100% success rate on easy,medium,difficult,and evil levels,and reach 864% success rate on only 17 clue sudokus.Besides,the average computation time is quite short,and has nothing to do with the difficulty of sudoku itself.In all,this algorithm is superior to both constraint programming and Sinkhorn algorithm in terms of success rate and computation time.
keywords:sudoku  constraint programming  integer programming  linear programming  primal dual interior point metho
查看全文  查看/发表评论  下载PDF阅读器

您是本站第 660079 位访问者
版权所有:南京信息工程大学期刊社《南京信息工程大学学报》编辑部     
地址:江苏南京,宁六路219号,南京信息工程大学