注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mr.Right

不顾一切的去想,于是我们有了梦想。脚踏实地的去做,于是梦想成了现实。

 
 
 

日志

 
 
关于我

人生一年又一年,只要每年都有所积累,有所成长,都有那么一次自己认为满意的花开时刻就好。即使一时不顺,也要敞开胸怀。生命的荣枯并不是简单的重复,一时的得失不是成败的尺度。花开不是荣耀,而是一个美丽的结束,花谢也不是耻辱,而是一个低调的开始。

网易考拉推荐

【转载】利用CVX求解数独(Sudoku)问题  

2014-10-23 00:40:30|  分类: 学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自yechao1009@126《利用CVX求解数独(Sudoku)问题》

这是凸优化课程的一道习题,要求使用CVX(一个凸优化的Matlab包)求解数独(Sudoku)问题。若不限定CVX,可以使用分枝定界以及整数规划等方法求解,还有提出使用最大流方法的,这里使用范数逼近的方法求解,即在“足够稀疏”的情况下,0范数(非零元个数)可用1范数(取绝对值相加)逼近。思路是将9*9的矩阵扩展为9*9*9的三维矩阵,限制其元素为0,1(使用整数规划,但是用1范数来逼近),若第i行第j列等于k,则三维矩阵第k层的第i行第j列数值为1。安装了CVX,求解数独的Matlab代码如下:

X = [5 3 0 0 7 0 0 0 0
     6 0 0 1 9 5 0 0 0
     0 9 8 0 0 0 0 6 0
     8 0 0 0 6 0 0 0 3
     4 0 0 8 0 3 0 0 1
     7 0 0 0 2 0 0 0 6
     0 6 0 0 0 0 2 8 0
     0 0 0 4 1 9 0 0 5
     0 0 0 0 8 0 0 7 9];
dim = size(X);
dim = dim(1);
d = sqrt(dim);


cvx_begin
variable c(dim,dim,dim);
%   objective function is to fill 3-dimensional matrix
minimize(sum(sum(sum(abs(c)))));
subject to
%   initial state: X(i, j) == k, c(i, j, k) == 1
    for i = 1:dim
        for j = 1:dim
            if (X(i,j) ~= 0)
                c(i,j,X(i,j)) == 1;
            end
        end
    end
%   1 - 9 appears only one time in each row
    sum(c, 1) == 1;

%   1 - 9 appears only one time in each column
    sum(c, 2) == 2;

%   1 - 9 appears only one time in each cell
    sum(c, 3) == 3;

%   1 - 9 appears only one time in each 3*3 square  
    for i = 1:d
        for j = 1:d
            for k = 1:dim
                sum(sum(c((i-1)*d+(1:d), (j-1)*d+(1:d), k))) == 1;
            end
        end
    end
cvx_end

Xout = zeros(dim);
for i = 1:dim
    Xout = Xout  + i*c(:,:,i);
end

此方法经简单修改,在安装YALMIP工具包后可使用整数规划求解。

另外还有一种方法可见于:P. Babu, K. Pelckmans, P. Stoica, J, Li. Linear Systems, Sparse Solutions, and Sudoku. IEEE SIGNAL PRO-CESSING LETTERS, Vol. 17, NO. 1, Jan, 2010. 也是使用范数逼近方法的。

  评论这张
 
阅读(230)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016