|
楼主 |
发表于 2011-1-19 16:10
|
显示全部楼层
今天用0-1规划写了一个
前段时间写过剔除法求解八皇后问题,可以求出所有解,今天用0-1规划写了一个程序,每次只能求出一个解-
- clear;clc;close all
- N=8;
- c=ones(N);
- % 行求和
- blkele=num2cell(c,2);
- A1=blkdiag(blkele{:});
- % 列求和
- A2=repmat(eye(N),1,N);
- Aeq=[A1;A2];
- beq=ones(2*N,1);
- % 斜线情况判断
- M=N-2;
- A=zeros(4*M+2,N*N);
- d{1}=arrayfun(@(i)find(diag(diag(c,i),i)),-M:M,'UniformOutput',0);
- d{2}=arrayfun(@(i)find(fliplr(diag(diag(c,i),i))),-M:M,'UniformOutput',0);
- d0=cat(1,d{:});
- linearIndex=arrayfun(@(x)sub2ind(size(A),x+zeros(1,length(d0{x})),...
- d0{x}'),1:numel(d0),'UniformOutput',0);
- A(cell2mat(linearIndex))=1;
- b=ones(4*M+2,1);
- x=bintprog([],A,b,Aeq,beq);
- Res=reshape(x,[],N);
复制代码 下面是我用lingo写的一个版本,还有待改进-
- model:
- sets:
- Node/1..8/:N;
- link(Node,Node):x;
- plus1/1..15/:;
- minus1/1..6/:;
- endsets
- @for(Node(i):@sum(Node(j):x(i,j))=1);
- @for(Node(j):@sum(Node(i):x(i,j))=1);
- @for(plus1(k)|k#ge#3:@sum(link(i,j)|i+j#eq#k:x(i,j))<1);
- @for(minus1(k):@sum(link(i,j)|i-j#eq#k:x(i,j))<1);
- @for(minus1(k):@sum(link(i,j)|j-i#eq#k:x(i,j))<1);
- @sum(Node(i):x(i,i))<1;
- @for(link(i,j):@bin(x(i,j)));
复制代码 |
评分
-
1
查看全部评分
-
|