论文检索
论文发表
当前位置：主页 > 论文百科 > 论文创新 >

匈牙利算法相关的例题_匈牙利算法的matlab编程求助

发布时间：2016-11-20 11:04

  本文关键词：匈牙利算法，由笔耕文化传播整理发布。


好新鲜的算法，匈牙利算法。

这是我用过的匈牙利算法，，代入你的13*13，可以得到正确结果，
Perf  = ;
======================================================
function  = xiongyali(Perf)
Matching = zeros(size(Perf));
num_y = sum(~isinf(Perf),1);
num_x = sum(~isinf(Perf),2);
x_con = find(num_x~=0);
y_con = find(num_y~=0);
P_size = max(length(x_con),length(y_con));
P_cond = zeros(P_size);
P_cond(1:length(x_con),1:length(y_con)) = Perf(x_con,y_con);
if isempty(P_cond)
    Cost = 0;
    return
end
Edge = P_cond;
Edge(P_cond~=Inf) = 0;
cnum = min_line_cover(Edge);
Pmax = max(max(P_cond(P_cond~=Inf)));
P_size = length(P_cond)+cnum;
P_cond = ones(P_size)*Pmax;
P_cond(1:length(x_con),1:length(y_con)) = Perf(x_con,y_con);
%*************************************************
exit_flag = 1;
stepnum = 1;
while exit_flag
    switch stepnum
        case 1
             = step1(P_cond);
        case 2
             = step2(P_cond);
        case 3
             = step3(M,P_size);
        case 4
             = step4(P_cond,r_cov,c_cov,M);
        case 5
             = step5(M,Z_r,Z_c,r_cov,c_cov);
        case 6
             = step6(P_cond,r_cov,c_cov);
        case 7
            exit_flag = 0;
    end
end
Matching(x_con,y_con) = M(1:length(x_con),1:length(y_con));
Cost = sum(sum(Perf(Matching==1)));
function  = step1(P_cond)
P_size = length(P_cond);
% Loop throught each row
for ii = 1:P_size
    rmin = min(P_cond(ii,:));
    P_cond(ii,:) = P_cond(ii,:)-rmin;
end
stepnum = 2;
function  = step2(P_cond)
P_size = length(P_cond);
r_cov = zeros(P_size,1);
c_cov = zeros(P_size,1);
M = zeros(P_size);
for ii = 1:P_size
    for jj = 1:P_size
        if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0
            M(ii,jj) = 1;
            r_cov(ii) = 1;
            c_cov(jj) = 1;
        end
    end
end
r_cov = zeros(P_size,1);
c_cov = zeros(P_size,1);
stepnum = 3;
function  = step3(M,P_size)
c_cov = sum(M,1);
if sum(c_cov) == P_size
    stepnum = 7;
else
    stepnum = 4;
end
function  = step4(P_cond,r_cov,c_cov,M)
P_size = length(P_cond);
zflag = 1;
while zflag
    row = 0; col = 0; exit_flag = 1;
    ii = 1; jj = 1;
    while exit_flag
        if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0
            row = ii;
            col = jj;
            exit_flag = 0;
        end
        jj = jj + 1;
        if jj > P_size; jj = 1; ii = ii+1; end
        if ii > P_size; exit_flag = 0; end
    end
   
    if row == 0
        stepnum = 6;
        zflag = 0;
        Z_r = 0;
        Z_c = 0;
    else
        M(row,col) = 2;
        if sum(find(M(row,:)==1)) ~= 0
            r_cov(row) = 1;
            zcol = find(M(row,:)==1);
            c_cov(zcol) = 0;
        else
            stepnum = 5;
            zflag = 0;
            Z_r = row;
            Z_c = col;
        end
    end
end
function  = step5(M,Z_r,Z_c,r_cov,c_cov)
zflag = 1;
ii = 1;
while zflag
    rindex = find(M(:,Z_c(ii))==1);
    if rindex > 0
        ii = ii+1;
        Z_r(ii,1) = rindex;
        Z_c(ii,1) = Z_c(ii-1);
    else
        zflag = 0;
    end
   
    if zflag == 1;
        cindex = find(M(Z_r(ii),:)==2);
        ii = ii+1;
        Z_r(ii,1) = Z_r(ii-1);
        Z_c(ii,1) = cindex;
    end
end
for ii = 1:length(Z_r)
    if M(Z_r(ii),Z_c(ii)) == 1
        M(Z_r(ii),Z_c(ii)) = 0;
    else
        M(Z_r(ii),Z_c(ii)) = 1;
    end
end
r_cov = r_cov.*0;
c_cov = c_cov.*0;
M(M==2) = 0;
stepnum = 3;
function  = step6(P_cond,r_cov,c_cov)
a = find(r_cov == 0);
b = find(c_cov == 0);
minval = min(min(P_cond(a,b)));
P_cond(find(r_cov == 1),:) = P_cond(find(r_cov == 1),:) + minval;
P_cond(:,find(c_cov == 0)) = P_cond(:,find(c_cov == 0)) - minval;
stepnum = 4;
function cnum = min_line_cover(Edge)
= step2(Edge);
= step3(M,length(Edge));
= step4(Edge,r_cov,c_cov,M);
cnum = length(Edge)-sum(r_cov)-sum(c_cov);

小虫的自动真恶心表情
=========================================
function  = xiongyali(Perf)
Matching = zeros(size(Perf));
num_y = sum(~isinf(Perf),1);
num_x = sum(~isinf(Perf),2);
x_con = find(num_x~=0);
y_con = find(num_y~=0);
P_size = max(length(x_con),length(y_con));
P_cond = zeros(P_size);
P_cond(1:length(x_con),1:length(y_con)) = Perf(x_con,y_con);
if isempty(P_cond)
    Cost = 0;
    return
end
Edge = P_cond;
Edge(P_cond~=Inf) = 0;
cnum = min_line_cover(Edge);
Pmax = max(max(P_cond(P_cond~=Inf)));
P_size = length(P_cond)+cnum;
P_cond = ones(P_size)*Pmax;
P_cond(1:length(x_con),1:length(y_con)) = Perf(x_con,y_con);
%*************************************************
exit_flag = 1;
stepnum = 1;
while exit_flag
    switch stepnum
        case 1
             = step1(P_cond);
        case 2
             = step2(P_cond);
        case 3
             = step3(M,P_size);
        case 4
             = step4(P_cond,r_cov,c_cov,M);
        case 5
             = step5(M,Z_r,Z_c,r_cov,c_cov);
        case 6
             = step6(P_cond,r_cov,c_cov);
        case 7
            exit_flag = 0;
    end
end
Matching(x_con,y_con) = M(1:length(x_con),1:length(y_con));
Cost = sum(sum(Perf(Matching==1)));
function  = step1(P_cond)
P_size = length(P_cond);
% Loop throught each row
for ii = 1:P_size
    rmin = min(P_cond(ii,:  ));
    P_cond(ii,:  ) = P_cond(ii,:  )-rmin;
end
stepnum = 2;
function  = step2(P_cond)
P_size = length(P_cond);
r_cov = zeros(P_size,1);
c_cov = zeros(P_size,1);
M = zeros(P_size);
for ii = 1:P_size
    for jj = 1:P_size
        if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0
            M(ii,jj) = 1;
            r_cov(ii) = 1;
            c_cov(jj) = 1;
        end
    end
end
r_cov = zeros(P_size,1);
c_cov = zeros(P_size,1);
stepnum = 3;
function  = step3(M,P_size)
c_cov = sum(M,1);
if sum(c_cov) == P_size
    stepnum = 7;
else
    stepnum = 4;
end
function  = step4(P_cond,r_cov,c_cov,M)
P_size = length(P_cond);
zflag = 1;
while zflag
    row = 0; col = 0; exit_flag = 1;
    ii = 1; jj = 1;
    while exit_flag
        if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0
            row = ii;
            col = jj;
            exit_flag = 0;
        end
        jj = jj + 1;
        if jj > P_size; jj = 1; ii = ii+1; end
        if ii > P_size; exit_flag = 0; end
    end
   
    if row == 0
        stepnum = 6;
        zflag = 0;
        Z_r = 0;
        Z_c = 0;
    else
        M(row,col) = 2;
        if sum(find(M(row,:  )==1)) ~= 0
            r_cov(row) = 1;
            zcol = find(M(row,:  )==1);
            c_cov(zcol) = 0;
        else
            stepnum = 5;
            zflag = 0;
            Z_r = row;
            Z_c = col;
        end
    end
end
function  = step5(M,Z_r,Z_c,r_cov,c_cov)
zflag = 1;
ii = 1;
while zflag
    rindex = find(M(:,Z_c(ii))==1);
    if rindex > 0
        ii = ii+1;
        Z_r(ii,1) = rindex;
        Z_c(ii,1) = Z_c(ii-1);
    else
        zflag = 0;
    end
   
    if zflag == 1;
        cindex = find(M(Z_r(ii),:  )==2);
        ii = ii+1;
        Z_r(ii,1) = Z_r(ii-1);
        Z_c(ii,1) = cindex;
    end
end
for ii = 1:length(Z_r)
    if M(Z_r(ii),Z_c(ii)) == 1
        M(Z_r(ii),Z_c(ii)) = 0;
    else
        M(Z_r(ii),Z_c(ii)) = 1;
    end
end
r_cov = r_cov.*0;
c_cov = c_cov.*0;
M(M==2) = 0;
stepnum = 3;
function  = step6(P_cond,r_cov,c_cov)
a = find(r_cov == 0);
b = find(c_cov == 0);
minval = min(min(P_cond(a,b)));
P_cond(find(r_cov == 1),:  ) = P_cond(find(r_cov == 1),:  ) + minval;
P_cond(:,find(c_cov == 0)) = P_cond(:,find(c_cov == 0)) - minval;
stepnum = 4;
function cnum = min_line_cover(Edge)
= step2(Edge);
= step3(M,length(Edge));
= step4(Edge,r_cov,c_cov,M);
cnum = length(Edge)-sum(r_cov)-sum(c_cov);

疯了！
===================================
function  = xiongyali(Perf)
Matching = zeros(size(Perf));
num_y = sum(~isinf(Perf),1);
num_x = sum(~isinf(Perf),2);
x_con = find(num_x~=0);
y_con = find(num_y~=0);
P_size = max(length(x_con),length(y_con));
P_cond = zeros(P_size);
P_cond(1:length(x_con),1:length(y_con)) = Perf(x_con,y_con);
if isempty(P_cond)
    Cost = 0;
    return
end
Edge = P_cond;
Edge(P_cond~=Inf) = 0;
cnum = min_line_cover(Edge);
Pmax = max(max(P_cond(P_cond~=Inf)));
P_size = length(P_cond)+cnum;
P_cond = ones(P_size)*Pmax;
P_cond(1:length(x_con),1:length(y_con)) = Perf(x_con,y_con);
%*************************************************
exit_flag = 1;
stepnum = 1;
while exit_flag
    switch stepnum
        case 1
             = step1(P_cond);
        case 2
             = step2(P_cond);
        case 3
             = step3(M,P_size);
        case 4
             = step4(P_cond,r_cov,c_cov,M);
        case 5
             = step5(M,Z_r,Z_c,r_cov,c_cov);
        case 6
             = step6(P_cond,r_cov,c_cov);
        case 7
            exit_flag = 0;
    end
end
Matching(x_con,y_con) = M(1:length(x_con),1:length(y_con));
Cost = sum(sum(Perf(Matching==1)));
function  = step1(P_cond)
P_size = length(P_cond);
% Loop throught each row
for ii = 1 : P_size
    rmin = min(P_cond(ii,:  ));
    P_cond(ii,:  ) = P_cond(ii,:  )-rmin;
end
stepnum = 2;
function  = step2(P_cond)
P_size = length(P_cond);
r_cov = zeros(P_size,1);
c_cov = zeros(P_size,1);
M = zeros(P_size);
for ii = 1 : P_size
    for jj = 1 : P_size
        if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0
            M(ii,jj) = 1;
            r_cov(ii) = 1;
            c_cov(jj) = 1;
        end
    end
end
r_cov = zeros(P_size,1);
c_cov = zeros(P_size,1);
stepnum = 3;
function  = step3(M,P_size)
c_cov = sum(M,1);
if sum(c_cov) == P_size
    stepnum = 7;
else
    stepnum = 4;
end
function  = step4(P_cond,r_cov,c_cov,M)
P_size = length(P_cond);
zflag = 1;
while zflag
    row = 0; col = 0; exit_flag = 1;
    ii = 1; jj = 1;
    while exit_flag
        if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0
            row = ii;
            col = jj;
            exit_flag = 0;
        end
        jj = jj + 1;
        if jj > P_size; jj = 1; ii = ii+1; end
        if ii > P_size; exit_flag = 0; end
    end
   
    if row == 0
        stepnum = 6;
        zflag = 0;
        Z_r = 0;
        Z_c = 0;
    else
        M(row,col) = 2;
        if sum(find(M(row,:  )==1)) ~= 0
            r_cov(row) = 1;
            zcol = find(M(row,:  )==1);
            c_cov(zcol) = 0;
        else
            stepnum = 5;
            zflag = 0;
            Z_r = row;
            Z_c = col;
        end
    end
end
function  = step5(M,Z_r,Z_c,r_cov,c_cov)
zflag = 1;
ii = 1;
while zflag
    rindex = find(M(:,Z_c(ii))==1);
    if rindex > 0
        ii = ii+1;
        Z_r(ii,1) = rindex;
        Z_c(ii,1) = Z_c(ii-1);
    else
        zflag = 0;
    end
   
    if zflag == 1;
        cindex = find(M(Z_r(ii),:  )==2);
        ii = ii+1;
        Z_r(ii,1) = Z_r(ii-1);
        Z_c(ii,1) = cindex;
    end
end
for ii = 1:length(Z_r)
    if M(Z_r(ii),Z_c(ii)) == 1
        M(Z_r(ii),Z_c(ii)) = 0;
    else
        M(Z_r(ii),Z_c(ii)) = 1;
    end
end
r_cov = r_cov.*0;
c_cov = c_cov.*0;
M(M==2) = 0;
stepnum = 3;
function  = step6(P_cond,r_cov,c_cov)
a = find(r_cov == 0);
b = find(c_cov == 0);
minval = min(min(P_cond(a,b)));
P_cond(find(r_cov == 1),:  ) = P_cond(find(r_cov == 1),:  ) + minval;
P_cond(:,find(c_cov == 0)) = P_cond(:,find(c_cov == 0)) - minval;
stepnum = 4;
function cnum = min_line_cover(Edge)
= step2(Edge);
= step3(M,length(Edge));
= step4(Edge,r_cov,c_cov,M);
cnum = length(Edge)-sum(r_cov)-sum(c_cov);

看那个没有表情的回复吧，

还是在这里下载吧


  本文关键词：匈牙利算法，由笔耕文化传播整理发布。



本文编号：183372

资料下载
论文发表

本文链接：https://www.wllwen.com/wenshubaike/shangbiaozhuanli/183372.html

上一篇：匈牙利算法相关的例题_hdu1150 匈牙利算法  
下一篇：tianwaifeimao的专栏
论文发表
最近更新
教材专著
热点文章

Copyright(c)文论论文网All Rights Reserved | 网站地图 |

版权申明：资料由用户8d181***提供，本站仅收录摘要或目录，作者需要删除请E-mail邮箱bigeng88@qq.com