① 求二分圖最大匹配的Matlab程序
[numh]=maxnum(g);%g是二分圖鄰接矩陣
%調用了一個自己寫maxnum函數，返回num就是最大值，h是hij(不唯一）
以下是maxnum.m的內容，用的是匈牙利演算法
其中還用了一個遞歸的incpath函數，尋找增廣路徑
function[numh]=maxnum(g)
s=size(g);
globalG_h;%矩陣hij記錄選中
globalG_g;%矩陣gij記錄匹配
globalG_v;%記錄當前一次路徑訪問過的節點
G_h=false(s);%矩陣hij初始為空
G_g=g;%矩陣gij就是傳遞進來的參數g
fori=1:s(1)
G_v=false(1,s(2));%每次初始化徑訪問過的節點為空
incpath(i);%從Ai開始尋找增廣路徑
end
h=G_h;num=sum(h(:));%輸出最大匹配數，和匹配矩陣h
clearglobal'G_h';clearglobal'G_g';
end
functionOK=incpath(i)%從Ai開始
globalG_h;globalG_g;globalG_v;OK=false;
j=find(~G_h(i,:)&G_g(i,:)&~G_v,1);%尋找合條件的Bj
ifisempty(j),return;end%找不到返回false
G_v(j)=true;%找到了，標記Bj為以訪問節點
ii=find(G_h(:,j));%尋找Bj在原來匹配中
ifisempty(ii)%如果不在原匹配中
G_h(i,j)=true;OK=true;return;end%找到增廣路徑末端，返回true
ok=incpath(ii);%如果在原來的匹配中，根據匹配對應的Aii遞歸調用incpath尋找
ifok%如果遞歸尋找返回成功
G_h(i,j)=~G_h(i,j);G_h(ii,j)=~G_h(ii,j);OK=true;return;end%路徑反色返回true
end
② 求下列所示的有效矩陣的指派問題最優解3 8 2 10 128 7 2 9 76 ...
為了解你這道題,我又重新把運籌學又看了一遍,然後去matlab論壇找解決方案.最終得出指派矩陣如下：1
0
0
0
00
0
1
0
00
1
0
0
00
0
0
1
00
0
0
0
1最優值為22ps：如果手動解的話,可以採用匈牙利演算法,但是不提倡使用手動求解.將相應的演算法變成程序,用的時候直接調用程序比較方便(如參加數學建模的時候,這類程序最好提前准備).另外,像這種比較專業的問題,我建議你去專業論壇去問或查看一些帖子對你一定非常有幫助.matlab程序如下（非原創）：>>
c=[3
8
2
10
12;8
7
2
9
7;6
4
2
7
5
8
4
2
3
5;9
10
6
9
10];
c=c(:);
a=zeros(10,25);
for
i=1:5
a(i,(i-1)*5+1:5*i)=1;
a(5+i,i:5:25)=1;
end
b=ones(10,1);
[x,y]=bintprog(c,[],[],a,b);
x=reshape(x,[5,5]),y
③ 二分圖最大匹配Matlab程序（在線等，感激不盡！）
第一個問題比較簡單，這里懶得對著你的圖片敲數據，用隨機數代替
long=100;
A=0.1*rand(long,1);
B=0.15*rand(long,1);
[AA BB]=meshgrid(A,B);
gg=0.5017*AA-0.65*BB;
g=gg>=-0.03&gg<=0.03; %這就是gij矩陣，相當於二分圖的連接矩陣
[num h] = maxnum(g);%第二個問題就是求二分圖的最大匹配問題，這里
%調用了一個自己寫maxnum函數，返回num就是最大值，h是hij(不唯一）
以下是maxnum.m的內容，用的是匈牙利演算法
其中還用了一個遞歸的incpath函數，尋找增廣路徑
function[numh]=maxnum(g)
s=size(g);
globalG_h;%矩陣hij記錄選中
globalG_g;%矩陣gij記錄匹配
globalG_v;%記錄當前一次路徑訪問過的節點
G_h=false(s);%矩陣hij初始為空
G_g=g;%矩陣gij就是傳遞進來的參數g
fori=1:s(1)
G_v=false(1,s(2));%每次初始化徑訪問過的節點為空
incpath(i);%從Ai開始尋找增廣路徑
end
h=G_h;num=sum(h(:));%輸出最大匹配數，和匹配矩陣h
clearglobal'G_h';clearglobal'G_g';
end
functionOK=incpath(i)%從Ai開始
globalG_h;globalG_g;globalG_v;OK=false;
j=find(~G_h(i,:)&G_g(i,:)&~G_v,1);%尋找合條件的Bj
ifisempty(j),return;end%找不到返回false
G_v(j)=true;%找到了，標記Bj為以訪問節點
ii=find(G_h(:,j));%尋找Bj在原來匹配中
ifisempty(ii)%如果不在原匹配中
G_h(i,j)=true;OK=true;return;end%找到增廣路徑末端，返回true
ok=incpath(ii);%如果在原來的匹配中，根據匹配對應的Aii遞歸調用incpath尋找
ifok%如果遞歸尋找返回成功
G_h(i,j)=~G_h(i,j);G_h(ii,j)=~G_h(ii,j);OK=true;return;end%路徑反色返回true
end
④ 匈牙利演算法網上下載的MATLAB程序（fenpei.m)為什麼會出現死循環跪求答案！！
那估計是因為輸入的新的數據不符合程序允許,或者超過極限值之類的吧
⑤ 急急急！！！尋匈牙利演算法、KM演算法的代碼！
尋匈牙利演算法:
function [result,msum]=sbppp(cost,m)
if nargin==1
dd=cost;
else
dd=max(max(cost))-cost;
end
[nop,nop]=size(cost);msum=0;
for i=1:nop
dd(i,:)=dd(i,:)-min(dd(i,:));
end
for j=1:nop
dd(:,j)=dd(:,j)-min(dd(:,j));
end
backup=dd;
for z=1:nop
bh=nop;bl=nop;result=[];
for k=1:nop
for i=1:nop
h=find(dd(i,:)==0);
if length(h)~=0&length(h)<bh
bh=length(h);
ch=i;
end
end
L=find(dd(ch,:)==0);
for j=1:length(L)
l=find(dd(:,L(j))==0);
if length(l)<bl
bl=length(l);
cl=L(j);
end
end
result(1,k)=ch;result(2,k)=cl;
dd(ch,:)=1;dd(:,cl)=1;
bl=nop;bh=nop;
if length(find(dd==0))==0
break
end
end
if length(result(1,:))==nop
break
end
dd=backup;DD=dd;d=zeros(nop);
for i=1:length(result(1,:))
d(result(1,i),result(2,i))=1;
end
D=~(d+dd);
p=[];q=[];k=1;zx=inf;
for i=1:nop
if sum(d(i,:))==0
p(k)=i;
k=k+1;
end
end
for j=1:length(p)
q=find(D(p(j),:)==1);
for e=1:length(q)
pp=find(d(:,q(e))==1);
if pp~=0
p(k)=pp;
k=k+1;
end
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
DD(:,q(u))=inf;
end
end
for l=1:length(p)
if min(DD(p(l),:))<zx
zx=min(DD(p(l),:));
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
dd(:,q(u))=dd(:,q(u))+zx;
end
end
for l=1:length(p)
dd(p(l),:)=dd(p(l),:)-zx;
end
backup=dd;
end
for i=1:length(result(1,:))
msum=msum+cost(result(1,i),result(2,i));
end
匈牙利演算法的MatLab實現 收藏
程序文件 fenpei.m
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
function [z,ans]=fenpei(marix)
%//////////////////////////////////////////////////
%輸入效率矩陣 marix 為方陣;
%若效率矩陣中有 M,則用一充分大的數代替;
%輸出z為最優解，ans為 最優分配矩陣；
%//////////////////////////////////////////////////
a=marix;
b=a;
%確定矩陣維數
s=length(a);
%確定矩陣行最小值，進行行減
ml=min(a');
for i=1:s
a(i,:)=a(i,:)-ml(i);
end
%確定矩陣列最小值，進行列減
mr=min(a);
for j=1:s
a(:,j)=a(:,j)-mr(j);
end
% start working
num=0;
while(num~=s) %終止條件是「（0）」的個數與矩陣的維數相同
%index用以標記矩陣中的零元素，若a(i,j)=0，則index(i,j)=1,否則index(i,j)=0
index=ones(s);
index=a&index;
index=~index;
%flag用以標記劃線位，flag=0 表示未被劃線，
%flag=1 表示有劃線過，flag=2 表示為兩直線交點
%ans用以記錄 a 中「（0）」的位置
%循環後重新初始化flag,ans
flag = zeros(s);
ans = zeros(s);
%一次循環劃線全過程，終止條件是所有的零元素均被直線覆蓋，
%即在flag>0位,index=0
while(sum(sum(index)))
%按行找出「（0）」所在位置，並對「（0）」所在列劃線，
%即設置flag,同時修改index,將結果填入ans
for i=1:s
t=0;
l=0;
for j=1:s
if(flag(i,j)==0&&index(i,j)==1)
l=l+1;
t=j;
end
end
if(l==1)
flag(:,t)=flag(:,t)+1;
index(:,t)=0;
ans(i,t)=1;
end
end
%按列找出「（0）」所在位置，並對「（0）」所在行劃線，
%即設置flag,同時修改index,將結果填入ans
for j=1:s
t=0;
r=0;
for i=1:s
if(flag(i,j)==0&&index(i,j)==1)
r=r+1;
t=i;
end
end
if(r==1)
flag(t,:)=flag(t,:)+1;
index(t,:)=0;
ans(t,j)=1;
end
end
end %對 while(sum(sum(index)))
%處理過程
%計數器：計算ans中1的個數，用num表示
num=sum(sum(ans));
% 判斷是否可以終止，若可以則跳出循環
if(s==num)
break;
end
%否則，進行下一步處理
%確定未被劃線的最小元素，用m表示
m=max(max(a));
for i=1:s
for j=1:s
if(flag(i,j)==0)
if(a(i,j)<m)
m=a(i,j);
end
end
end
end
%未被劃線，即flag=0處減去m；線交點，即flag=2處加上m
for i=1:s
for j=1:s
if(flag(i,j)==0)
a(i,j)=a(i,j)-m;
end
if(flag(i,j)==2)
a(i,j)=a(i,j)+m;
end
end
end
end %對while(num~=s)
%計算最優（min）值
zm=ans.*b;
z=0;
z=sum(sum(zm));
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
運行實例：
>> a=[37.7 32.9 38.8 37 35.4
43.4 33.1 42.2 34.7 41.8
33.3 28.5 38.9 30.4 33.6
29.2 26.4 29.6 28.5 31.1
0 0 0 0 0];
>> [z,ans]=fenpei(a)
z =
127.8000
ans =
0 0 0 0 1
0 0 0 1 0
0 1 0 0 0
1 0 0 0 0
0 0 1 0 0
⑥ 匈牙利演算法 matlab程序出現問題 運行時出現 Undefined function or variable 'a'.
調用 Edmonds 時，忘了個 實際參數 a（有值得）或數值了。
也可以 用默認參數值。
function [Matching,Cost] = Edmonds(a)
if nargin==0
a=.......;
end
Matching = zeros(size(a));
.........
⑦ 求kM演算法和匈牙利演算法的程序代碼
我學pascal的。本來我是有程序的。既然你要c的那我只好查給你了。問演算法過程的話可以追問匈牙利演算法1 #include<stdio.h>
2 #include<string.h>
3 bool g[201][201];
4 int n, m, ans;
5 bool b[201];
6 int link[201];
7 bool init()
8 {
9 int _x, _y;
10 memset(g, 0, sizeof(g));
11 memset(link, 0, sizeof(link));
12 ans = 0;
13 if (scanf("%d%d", &n, &m) == EOF)
14 return false;
15 for (int i = 1; i <= n; i++) {
16 scanf("%d", &_x);
17 for (int j = 0; j < _x; j++) {
18 scanf("%d", &_y);
19 g[i][_y] = true;
20 }
21 }
22 return true;
23 }
24
25 bool find(int a)
26 {
27 for (int i = 1; i <= m; i++) {
28 if (g[a][i] == 1 && !b[i]) {
29 b[i] = true;
30 if (link[i] == 0 || find(link[i])) {
31 link[i] = a;
32 return true;
33 }
34 }
35 }
36 return false;
37 }
38
39 int main()
40 {
41 while (init()) {
42 for (int i = 1; i <= n; i++) {
43 memset(b, 0, sizeof(b));
44 if (find(i))
45 ans++;
46 }
47 printf("%d\n", ans);
48 }
49 }KM演算法#include <cstdio>
#include <memory.h>
#include <algorithm> // 使用其中的 min 函數
using namespace std;
const int MAX = 1024;
int n; // X 的大小
int weight [MAX] [MAX]; // X 到 Y 的映射（權重）
int lx [MAX], ly [MAX]; // 標號
bool sx [MAX], sy [MAX]; // 是否被搜索過
int match [MAX]; // Y(i) 與 X(match [i]) 匹配
// 初始化權重
void init (int size);
// 從 X(u) 尋找增廣道路，找到則返回 true
bool path (int u);
// 參數 maxsum 為 true ，返回最大權匹配，否則最小權匹配
int bestmatch (bool maxsum = true);
void init (int size)
{
// 根據實際情況，添加代碼以初始化
n = size;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
scanf ("%d", &weight [i] [j]);
}
bool path (int u)
{
sx [u] = true;
for (int v = 0; v < n; v ++)
if (!sy [v] && lx[u] + ly [v] == weight [u] [v])
{
sy [v] = true;
if (match [v] == -1 || path (match [v]))
{
match [v] = u;
return true;
}
}
return false;
}
int bestmatch (bool maxsum)
{
int i, j;
if (!maxsum)
{
for (i = 0; i < n; i ++)
for (j = 0; j < n; j ++)
weight [i] [j] = -weight [i] [j];
}
// 初始化標號
for (i = 0; i < n; i ++)
{
lx [i] = -0x1FFFFFFF;
ly [i] = 0;
for (j = 0; j < n; j ++)
if (lx [i] < weight [i] [j])
lx [i] = weight [i] [j];
}
memset (match, -1, sizeof (match));
for (int u = 0; u < n; u ++)
while (1)
{
memset (sx, 0, sizeof (sx));
memset (sy, 0, sizeof (sy));
if (path (u))
break;
// 修改標號
int dx = 0x7FFFFFFF;
for (i = 0; i < n; i ++)
if (sx [i])
for (j = 0; j < n; j ++)
if(!sy [j])
dx = min (lx[i] + ly [j] - weight [i] [j], dx);
for (i = 0; i < n; i ++)
{
if (sx [i])
lx [i] -= dx;
if (sy [i])
ly [i] += dx;
}
}
int sum = 0;
for (i = 0; i < n; i ++)
sum += weight [match [i]] [i];
if (!maxsum)
{
sum = -sum;
for (i = 0; i < n; i ++)
for (j = 0; j < n; j ++)
weight [i] [j] = -weight [i] [j]; // 如果需要保持 weight [ ] [ ] 原來的值，這里需要將其還原
}
return sum;
}
int main()
{
int n;
scanf ("%d", &n);
init (n);
int cost = bestmatch (true);
printf ("%d ", cost);
for (int i = 0; i < n; i ++)
{
printf ("Y %d -> X %d ", i, match [i]);
}
return 0;
}
⑧ MATLAB 匈牙利演算法運行busy
是不是你的程序掉進死循環了
你檢查下
輸入的新的數據不符合程序允許,或者超過極限值
尋匈牙利演算法:
function [result,msum]=sbppp(cost,m)
if nargin==1
dd=cost;
else
dd=max(max(cost))-cost;
end
[nop,nop]=size(cost);msum=0;
for i=1:nop
dd(i,:)=dd(i,:)-min(dd(i,:));
end
for j=1:nop
dd(:,j)=dd(:,j)-min(dd(:,j));
end
backup=dd;
for z=1:nop
bh=nop;bl=nop;result=[];
for k=1:nop
for i=1:nop
h=find(dd(i,:)==0);
if length(h)~=0&length(h)<bh
bh=length(h);
ch=i;
end
end
L=find(dd(ch,:)==0);
for j=1:length(L)
l=find(dd(:,L(j))==0);
if length(l)<bl
bl=length(l);
cl=L(j);
end
end
result(1,k)=ch;result(2,k)=cl;
dd(ch,:)=1;dd(:,cl)=1;
bl=nop;bh=nop;
if length(find(dd==0))==0
break
end
end
if length(result(1,:))==nop
break
end
dd=backup;DD=dd;d=zeros(nop);
for i=1:length(result(1,:))
d(result(1,i),result(2,i))=1;
end
D=~(d+dd);
p=[];q=[];k=1;zx=inf;
for i=1:nop
if sum(d(i,:))==0
p(k)=i;
k=k+1;
end
end
for j=1:length(p)
q=find(D(p(j),:)==1);
for e=1:length(q)
pp=find(d(:,q(e))==1);
if pp~=0
p(k)=pp;
k=k+1;
end
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
DD(:,q(u))=inf;
end
end
for l=1:length(p)
if min(DD(p(l),:))<zx
zx=min(DD(p(l),:));
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
dd(:,q(u))=dd(:,q(u))+zx;
end
end
for l=1:length(p)
dd(p(l),:)=dd(p(l),:)-zx;
end
backup=dd;
end
for i=1:length(result(1,:))
msum=msum+cost(result(1,i),result(2,i));
end
匈牙利演算法的MatLab實現 收藏
程序文件 fenpei.m
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
function [z,ans]=fenpei(marix)
%//////////////////////////////////////////////////
%輸入效率矩陣 marix 為方陣;
%若效率矩陣中有 M,則用一充分大的數代替;
%輸出z為最優解，ans為 最優分配矩陣；
%//////////////////////////////////////////////////
a=marix;
b=a;
%確定矩陣維數
s=length(a);
%確定矩陣行最小值，進行行減
ml=min(a');
for i=1:s
a(i,:)=a(i,:)-ml(i);
end
%確定矩陣列最小值，進行列減
mr=min(a);
for j=1:s
a(:,j)=a(:,j)-mr(j);
end
% start working
num=0;
while(num~=s) %終止條件是「（0）」的個數與矩陣的維數相同
%index用以標記矩陣中的零元素，若a(i,j)=0，則index(i,j)=1,否則index(i,j)=0
index=ones(s);
index=a&index;
index=~index;
%flag用以標記劃線位，flag=0 表示未被劃線，
%flag=1 表示有劃線過，flag=2 表示為兩直線交點
%ans用以記錄 a 中「（0）」的位置
%循環後重新初始化flag,ans
flag = zeros(s);
ans = zeros(s);
%一次循環劃線全過程，終止條件是所有的零元素均被直線覆蓋，
%即在flag>0位,index=0
while(sum(sum(index)))
%按行找出「（0）」所在位置，並對「（0）」所在列劃線，
%即設置flag,同時修改index,將結果填入ans
for i=1:s
t=0;
l=0;
for j=1:s
if(flag(i,j)==0&&index(i,j)==1)
l=l+1;
t=j;
end
end
if(l==1)
flag(:,t)=flag(:,t)+1;
index(:,t)=0;
ans(i,t)=1;
end
end
%按列找出「（0）」所在位置，並對「（0）」所在行劃線，
%即設置flag,同時修改index,將結果填入ans
for j=1:s
t=0;
r=0;
for i=1:s
if(flag(i,j)==0&&index(i,j)==1)
r=r+1;
t=i;
end
end
if(r==1)
flag(t,:)=flag(t,:)+1;
index(t,:)=0;
ans(t,j)=1;
end
end
end %對 while(sum(sum(index)))
%處理過程
%計數器：計算ans中1的個數，用num表示
num=sum(sum(ans));
% 判斷是否可以終止，若可以則跳出循環
if(s==num)
break;
end
%否則，進行下一步處理
%確定未被劃線的最小元素，用m表示
m=max(max(a));
for i=1:s
for j=1:s
if(flag(i,j)==0)
if(a(i,j)<m)
m=a(i,j);
end
end
end
end
%未被劃線，即flag=0處減去m；線交點，即flag=2處加上m
for i=1:s
for j=1:s
if(flag(i,j)==0)
a(i,j)=a(i,j)-m;
end
if(flag(i,j)==2)
a(i,j)=a(i,j)+m;
end
end
end
end %對while(num~=s)
%計算最優（min）值
zm=ans.*b;
z=0;
z=sum(sum(zm));
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
運行實例：
>> a=[37.7 32.9 38.8 37 35.4
43.4 33.1 42.2 34.7 41.8
33.3 28.5 38.9 30.4 33.6
29.2 26.4 29.6 28.5 31.1
0 0 0 0 0];
>> [z,ans]=fenpei(a)
z =
127.8000
ans =
0 0 0 0 1
0 0 0 1 0
0 1 0 0 0
1 0 0 0 0
0 0 1 0 0
⑨ matlab 向量排序。
排序不等式是：倒序<=亂序<=順序；所以最好是A和B都排序成順序才會得到最大值。但如果A保持不動，讓B排序使得得到的乘積最大，這其實是一個整數二元線性規劃問題。你可以設一個矩陣C，這個矩陣是7x7的，行元素表示對應A中1到7的位置，列元素的含義是對應B元素不排序的值。在7x7矩陣中aij表示：A中從頭開始第i個元素與B中從頭開始第j個元素相對應，則在此處取值為1，否則取值為零。而7x7矩陣每一行求和為1，每一列求和為1。這樣只有求解max（CA）就ok。解決這樣的二元整數規劃，你可以嘗試使用匈牙利演算法，或者直接使用Lingo或者Matlab求解。這屬於運籌學問題。