应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » MATLAB/Mathematica » 匈牙利算法的matlab编程求助
51/1返回列表
查看: 2452  |  回复: 6
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

liushaojiang

银虫 (小有名气)

[求助] 匈牙利算法的matlab编程求助

一个13*13的矩阵[0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0
23.5 21.2 28.8 35 36.4 52.5 47.2 55 53.5 60 0 0 0
61 57.5 56.5 56 47 36 27 18 14 20 0 0 0
23.6 24.5 19 6 4 18 21 29 37.5 45 0 0 0
10 29 19 8 21 35.5 37 44.5 55 63 0 0 0
29 25 19.5 20 7 22.5 12 27.5 33.5 40 0 0 0
33 27 25 26 14.5 22 12 17.5 25 35 0 0 0
56 50 48 40 36.5 28 22 15.5 26.5 30 0 0 0
65 62 60 55 50 48.5 35 25 27 20 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0]用匈牙利算法求出求5个不同行，不同列的最小的五个数，哪位大神能给个程序可以实现的，网上好多匈牙利的matlab程序运行这个矩阵后都死循环了，感激不尽！
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2013-06-22 13:45:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

somomo91

专家顾问 (职业作家)

【答案】应助回帖

这是我用过的匈牙利算法，代入你的13*13，可以得到正确结果，
Perf  = [   0 0 0 0 0 0 0 0 0 0 0 0 1; ...
        0 0 0 0 0 0 0 0 0 0 0 1 0; ...
        0 0 0 0 0 0 0 0 0 0 1 0 0; ...
        23.5 21.2 28.8 35 36.4 52.5 47.2 55 53.5 60 0 0 0; ...
        61 57.5 56.5 56 47 36 27 18 14 20 0 0 0; ...
        23.6 24.5 19 6 4 18 21 29 37.5 45 0 0 0; ...
        10 29 19 8 21 35.5 37 44.5 55 63 0 0 0; ...
        29 25 19.5 20 7 22.5 12 27.5 33.5 40 0 0 0; ...
        33 27 25 26 14.5 22 12 17.5 25 35 0 0 0; ...
        56 50 48 40 36.5 28 22 15.5 26.5 30 0 0 0; ...
        65 62 60 55 50 48.5 35 25 27 20 0 0 0; ...
        0 0 0 0 0 0 0 0 0 0 0 0 0; ...
        0 0 0 0 0 0 0 0 0 0 0 0 0];
======================================================
function [Matching] = 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
            [P_cond,stepnum] = step1(P_cond);
        case 2
            [r_cov,c_cov,M,stepnum] = step2(P_cond);
        case 3
            [c_cov,stepnum] = step3(M,P_size);
        case 4
            [M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(P_cond,r_cov,c_cov,M);
        case 5
            [M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov);
        case 6
            [P_cond,stepnum] = 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 [P_cond,stepnum] = step1(P_cond)

P_size = length(P_cond);

% Loop throught each row
for ii = 1_size
    rmin = min(P_cond(ii,);
    P_cond(ii, = P_cond(ii,-rmin;
end

stepnum = 2;

function [r_cov,c_cov,M,stepnum] = 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_size
    for jj = 1_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 [c_cov,stepnum] = step3(M,P_size)

c_cov = sum(M,1);
if sum(c_cov) == P_size
    stepnum = 7;
else
    stepnum = 4;
end

function [M,r_cov,c_cov,Z_r,Z_c,stepnum] = 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 [M,r_cov,c_cov,stepnum] = 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 [P_cond,stepnum] = 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)

[r_cov,c_cov,M,stepnum] = step2(Edge);
[c_cov,stepnum] = step3(M,length(Edge));
[M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(Edge,r_cov,c_cov,M);
cnum = length(Edge)-sum(r_cov)-sum(c_cov);
赞一下 回复此楼
3楼2013-06-25 20:22:21
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 7 个回答

ajitai

铁杆木虫 (职业作家)
好新鲜的算法，匈牙利算法。
赞一下 回复此楼
2楼2013-06-23 12:59:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

somomo91

专家顾问 (职业作家)

【答案】应助回帖

小虫的自动真恶心表情

=========================================
function [Matching] = 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
            [P_cond,stepnum] = step1(P_cond);
        case 2
            [r_cov,c_cov,M,stepnum] = step2(P_cond);
        case 3
            [c_cov,stepnum] = step3(M,P_size);
        case 4
            [M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(P_cond,r_cov,c_cov,M);
        case 5
            [M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov);
        case 6
            [P_cond,stepnum] = 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 [P_cond,stepnum] = step1(P_cond)

P_size = length(P_cond);

% Loop throught each row
for ii = 1_size
    rmin = min(P_cond(ii,:  ));
    P_cond(ii,:  ) = P_cond(ii,:  )-rmin;
end

stepnum = 2;

function [r_cov,c_cov,M,stepnum] = 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_size
    for jj = 1_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 [c_cov,stepnum] = step3(M,P_size)

c_cov = sum(M,1);
if sum(c_cov) == P_size
    stepnum = 7;
else
    stepnum = 4;
end

function [M,r_cov,c_cov,Z_r,Z_c,stepnum] = 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 [M,r_cov,c_cov,stepnum] = 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 [P_cond,stepnum] = 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)

[r_cov,c_cov,M,stepnum] = step2(Edge);
[c_cov,stepnum] = step3(M,length(Edge));
[M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(Edge,r_cov,c_cov,M);
cnum = length(Edge)-sum(r_cov)-sum(c_cov);
赞一下 回复此楼
4楼2013-06-25 20:23:59
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

somomo91

专家顾问 (职业作家)

【答案】应助回帖

疯了！
===================================
function [Matching] = 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
            [P_cond,stepnum] = step1(P_cond);
        case 2
            [r_cov,c_cov,M,stepnum] = step2(P_cond);
        case 3
            [c_cov,stepnum] = step3(M,P_size);
        case 4
            [M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(P_cond,r_cov,c_cov,M);
        case 5
            [M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov);
        case 6
            [P_cond,stepnum] = 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 [P_cond,stepnum] = 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 [r_cov,c_cov,M,stepnum] = 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 [c_cov,stepnum] = step3(M,P_size)

c_cov = sum(M,1);
if sum(c_cov) == P_size
    stepnum = 7;
else
    stepnum = 4;
end

function [M,r_cov,c_cov,Z_r,Z_c,stepnum] = 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 [M,r_cov,c_cov,stepnum] = 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 [P_cond,stepnum] = 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)

[r_cov,c_cov,M,stepnum] = step2(Edge);
[c_cov,stepnum] = step3(M,length(Edge));
[M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(Edge,r_cov,c_cov,M);
cnum = length(Edge)-sum(r_cov)-sum(c_cov);
赞一下 回复此楼
5楼2013-06-25 20:25:42
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 7 个回答
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 投票:  有多少人是今天查系统知道结果的？ +15 爱看书的可乐 2026-08-26 17/850 2026-08-27 15:06 by xxniao123
[基金申请] 国自然面上复盘~欢迎讨论 +8 晴天加油 2026-08-26 9/450 2026-08-27 14:14 by gltch
[教师之家] 导师吐槽：我怎么摊上了这么个极品研究生！ +6 苏东坡二世 2026-08-23 6/300 2026-08-27 13:57 by zhangjianl
[基金申请] 基金不中，共勉 +8 eulota 2026-08-26 8/400 2026-08-27 12:34 by lice_1987
[基金申请] 基金未中，这种答复是模板吗？ +4 zhaosm1982 2026-08-27 5/250 2026-08-27 12:17 by zhaosm1982
[基金申请] 面上合作单位盖章 +3 ssyjh 2026-08-27 3/150 2026-08-27 09:59 by 阿拉贡aragon
[基金申请] 为什么 国际(地区)合作与交流项目 没有放榜？ 10+3 majunge000 2026-08-26 11/550 2026-08-27 08:42 by 北京莱茵编辑
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 LIbGuocjEEYw 2026-08-26 4/200 2026-08-27 02:01 by Ie9AyIAvGbvs
[基金申请] 能否退出参与的面上项目解除限项 +23 koalala 2026-08-24 26/1300 2026-08-26 14:29 by 宝贝虫子
[基金申请] 系统进不去 +4 yanglien 2026-08-26 5/250 2026-08-26 11:10 by wenfengw83
[基金申请] 国合可查了 +3 paperzjh 2026-08-26 3/150 2026-08-26 10:41 by LemmonTr
[职场人生] 学生撞见辅导员送外卖，第二天全班都沉默了 +3 鲸鱼融金_浙江_� 2026-08-22 3/150 2026-08-26 09:01 by zzuzxg
[基金申请] 国合现在查不到了吗？ +10 chengyan1220 2026-08-24 20/1000 2026-08-26 08:57 by peasantsprig
[基金申请] 牛来！米来！面来！ +8 beefly 2026-08-26 8/400 2026-08-26 08:37 by xuzhipiao
[基金申请] 在坚冰还盖着北海的时候，我看到了怒放的梅花。 (金币+10) +6 ziyangfang 2026-08-25 9/450 2026-08-25 20:26 by huagongfeihu
[基金申请] 某些机构，以效率低为荣，以效率低作为存在感 +9 yuleib84 2026-08-25 10/500 2026-08-25 17:14 by alexon
[基金申请] 我面上完蛋了 +13 且听虎啸 2026-08-20 14/700 2026-08-25 09:10 by mrkang
[基金申请] 建议基金发布提前给出明确的时间点 +13 kulium 2026-08-21 16/800 2026-08-24 16:27 by superceng
[基金申请] 时间戳今天，20号变了 +5 archvillain 2026-08-20 5/250 2026-08-22 06:12 by hui_daxiao
[基金申请] 应该是下周三26日公布了吧？ +4 哈哈蛤？ 2026-08-21 4/200 2026-08-21 10:58 by Vivilian
信息提示
关闭
请填处理意见
关闭