匈牙利算法的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=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

1 1 1

2 2 2 2 0

2 4 4

3 3 1 1 0

7 2 2 4 4 7 7 0

3 5 5 7 7 5 5 0

4 3 3 9 9 6 6 0

8 8 8 1 1 4 4 0

6 6 6 12 12 11 11 0

5 9 9 13 13 12 12 0

蚁群算法TSP问题matlab源代码

function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta ,Rho,Q) %%===================================================== ==================== %% ACATSP.m %% Ant Colony Algorithm for Traveling Salesman Problem %% ChengAihua,PLA Information Engineering University,ZhengZhou,China %% Email:aihuacheng@https://www.sodocs.net/doc/dc12250003.html, %% All rights reserved %%------------------------------------------------------------------------- %% 主要符号说明 %% C n个城市的坐标，n×4的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%===================================================== ==================== %%第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=max( ((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5,min(abs(C(i,3)-C(j,3)),144- abs(C(i,3)-C(j,3))) );%计算城市间距离 else D(i,j)=eps; end D(j,i)=D(i,j); end end Eta=1./D;%Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n);%Tau为信息素矩阵 Tabu=zeros(m,n);%存储并记录路径的生成 NC=1;%迭代计数器 R_best=zeros(NC_max,n);%各代最佳路线

用改进的匈牙利算法求解运输问题

用改进的匈牙利算法求解运输问题 李雪娇，于洪珍 中国矿业大学信电学院，江苏徐州 (221008) Email ：liaohuchushan@https://www.sodocs.net/doc/dc12250003.html, 摘 要：本文提出用改进的匈牙利算法求解运输问题。此算法不但可以直接求取最优解，而且在运量受限制的运输问题中有很好的应用。 关键词：改进，匈牙利算法，运输问题，最优解 0. 引言 在现实生活中，我们常常会遇到许多运输问题。运输问题的求解多采用表上作业法。在此方法中，我们需要先利用最小元素法或西北角法求出一组基本可行解，再对此解检验其最优性。若此解非最优解，则又要进行解的改进。这一过程比较麻烦，尤其对一些结构不太大的模型，编程时往往过于繁琐。 同时，经典运输问题在实际应用中有很大的局限性, 对一些运输量受限制或运输能力受限制的运输问题，我们无法用表上作业法直接求取。在此，我们采用改进的匈牙利算法处理这类运输问题。为了便于描述，设物资供应量12[...]m A a a a =，物资需求量12[...]n B b b b =，从到i A j B 的单物的物资运价，最小运输量 (假设m )。 i j C i j L n >1. 匈牙利算法[1][4] 匈牙利算法的基本思想是修改效益矩阵的行和列，使得每行和每列中至少有一个零元素。经过一定的变换，得到不同行、不同列只有一个零元素。从而得到一个与这些零元素相匹配的完全分配方案。这种方法总是在有限步内收敛于一个最优解。该方法的理论基础是：在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最优解的分配。求解步骤如下： 第一步：使指派问题的系数矩阵经变换后，在各行各列中都出现零元素，即从系数矩阵的每行（或列）元素中减去该行（或列）的最小元素。 第二步：寻求找n 个独立的零元素，以得到最优解：（1）从只有一个0元素的行（或列）开始，对这个0元素加圈，记为θ。然后划去此元素所在列（或行）的其他0元素，记作?。反复进行，直到所有的0元素被划完。（2）若仍有没有划圈的0元素，则从剩有0元素最少的行开始，比较这行0元素所在各列中0元素的数目，选择0元素少的那列的0元素加圈θ，然后划掉同行同列的其他0元素，反复进行直到所有的0元素被划掉或圈出。 （3）若元素的数目m 等于矩阵的阶数，那么指派问题的最优解已得到。若m ，则转入下一步。 n n <第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数：若l ，必须再变换当前的系数矩阵，才能找到个独立的0元素，为此转第四步；若l ，而，应回到第二步（2），另行试探。 n

二分图的最大匹配经典之匈牙利算法

Doctor的图论计划之——二分图最大匹配 第一讲二分图的最大匹配经典之匈牙利算法 二分图，顾名思义就是分成了两个部分的图……很白痴的解释（自己吐槽了先），但吐槽的同时我们也要发现一些二分图的基本性质！ 性质1 二分图之所以分成了两个部分，那是因为单独的一个部分中的任意两点不连通！ 性质2 二分图匹配——匈牙利算法中我们只需记录集合1到集合2的单向边就可以了（注意看上边的图，箭头是单向的）思考这是为什么！ 但是！二分图确实是无向图！！！只不过匈牙利算法只是从一个集合另一个集合走一遍罢了！！！！ 性质3 树是一种特殊的二分图！ 紫色的结点构成集合1，绿色的结点构成集合2，换句话说，儿子和爸爸打仗时爷爷和

孙子站在同一战线！（也可以认为是儿子和爸妈吵架时总是爷爷奶奶护着，小时候有这样的记忆没有？反正我没有！） PS：树就是无回路懂不？ 性质3 对于任意二分图，其包含的环一定全部是偶环！（充要可证） 可以证明，含有奇数条边的环一定有两个在相同集合内的点有边相连！ 也就是说——二分图的bfs子树一定不含奇环！ 接下来说一下二分图求最大匹配的算法——匈牙利算法 【例1】传说中的多米诺骨牌覆盖问题 在一个n*m的棋盘上，摆放一些1*2大小的多米诺骨牌，但棋盘某些地方是坏 掉的，即不能将骨牌置于这些坏掉的格子上，求最多能摆上的骨牌数量 【例2】传说中的猎人打鸟问题 猎人要在n*n的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟都被 打掉，也可以在某一列中打,这样此列中的所有鸟都打掉.问至少打几枪,才能打光 所有的鸟？ 【例3】传说中的搞对象问题 一保守教师想带学生郊游, 却怕他们途中谈恋爱,他认为满足下面条件之一的两 人谈恋爱几率很小: (1)身高差>40 (2) 性别相同(3) 爱好不同类型的音乐(4) 爱好同类型的运动 告诉你每个同学的信息，问老师最多能带多少学生？ 这样的问题如何解决？搜索？怎么搜？会不会超时？答案很简单，三道题中的元素都可以用很简单的方式分成两个互不相干的部分，因此可以用二分图匹配来解决这个问题：形象的说，我们规定搞基和百合都是不允许的，已知一群男人和女人，他们可以看做图中的顶点，男人构成了集合A,女人构成了集合B，边表示这名男人和这名女人互相有好感（可以配成一对）不考虑个人因素，现在希望为这些饥渴的男男女女找到最多的配对数（脚踏两只船也是不允许的！）为了解决这样的问题我们才引入了二分图的匹配算法——匈牙利算法！ 匈牙利算法是一种用增广路求二分图最大匹配的算法。它由匈牙利数学家Edmonds于1965年提出，因而得名。 如果暴搜的话那么无疑时间复杂度将成为O（2^E）！无法快速实现，于是我们就提出了更为高效的算法，这种算法是从网络流演变而来，但这里我们抛开所有网络流的知识，但从这一算法的角度来进行阐释！ 解释一些常用的名词 交错轨：所谓交错轨，还有一种更为文雅的说法叫增广轨，这种说法让人不禁联想到蛋疼的网络流算法，所以我更喜欢用一种与网络流无关的说法来称呼它，下面我们来举几个交错轨的例子：

蚁群算法matlab程序代码

先新建一个主程序M文件ACATSP.m 代码如下: function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q) %%================================================== ======================= %% 主要符号说明 %% C n个城市的坐标，n×2的矩阵 %% NC_max 蚁群算法MATLAB程序最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 表示蚁群算法MATLAB程序信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%================================================== =======================

%% 蚁群算法MATLAB程序第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5; else D(i,j)=eps; % i = j 时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示 end D(j,i)=D(i,j); %对称矩阵 end end Eta=1./D; %Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n); %Tau为信息素矩阵 Tabu=zeros(m,n); %存储并记录路径的生成

蚁群算法matlab

蚁群算法的matlab源码，同时请指出为何不能优化到已知的最好解 % % % the procedure of ant colony algorithm for VRP % % % % % % % % % % % % %initialize the parameters of ant colony algorithms load data.txt; d=data(:,2:3); g=data(:,4); m=31; % 蚂蚁数 alpha=1; belta=4;% 决定tao和miu重要性的参数 lmda=0; rou=0.9; %衰减系数 q0=0.95; % 概率 tao0=1/(31*841.04);%初始信息素 Q=1;% 蚂蚁循环一周所释放的信息素 defined_phrm=15.0; % initial pheromone level value QV=100; % 车辆容量 vehicle_best=round(sum(g)/QV)+1; %所完成任务所需的最少车数V=40; % 计算两点的距离 for i=1:32; for j=1:32;

dist(i,j)=sqrt((d(i,1)-d(j,1))^2+(d(i,2)-d(j,2))^2); end; end; %给tao miu赋初值 for i=1:32; for j=1:32; if i~=j; %s(i,j)=dist(i,1)+dist(1,j)-dist(i,j); tao(i,j)=defined_phrm; miu(i,j)=1/dist(i,j); end; end; end; for k=1:32; for k=1:32; deltao(i,j)=0; end; end; best_cost=10000; for n_gen=1:50; print_head(n_gen); for i=1:m; %best_solution=[]; print_head2(i);

可以直接用的匈牙利算法

将xyl程序存入M文件，在matlab中先写入邻接矩阵marix，而后再写function [z,ans]=xyl(marix) 回车得出结果 程序文件 xyl.m function [z,ans]=xyl(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;

蚁群算法MATLAB代码

function [y,val]=QACStic load att48 att48; MAXIT=300; % 最大循环次数 NC=48; % 城市个数 tao=ones(48,48);% 初始时刻各边上的信息最为1 rho=0.2; % 挥发系数 alpha=1; beta=2; Q=100; mant=20; % 蚂蚁数量 iter=0; % 记录迭代次数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2); end end bestroute=zeros(1,48); % 用来记录最优路径 routelength=inf; % 用来记录当前找到的最优路径长度 % for i=1:mant % 确定各蚂蚁初始的位置 % end for ite=1:MAXIT for ka=1:mant %考查第K只蚂蚁 deltatao=zeros(48,48); % 第K只蚂蚁移动前各边上的信息增量为零 [routek,lengthk]=travel(distance,tao,alpha,beta); if lengthk

matlab蚁群算法精讲及仿真图

蚁群算法matlab精讲及仿真 4.1基本蚁群算法 4.1.1基本蚁群算法的原理 蚁群算法是上世纪90年代意大利学者M.Dorigo,v.Maneizz。等人提出来的,在越来越多的领域里得到广泛应用。蚁群算法，是一种模拟生物活动的智能算法，蚁群算法的运作机理来源于现实世界中蚂蚁的真实行为，该算法是由Marco Dorigo 首先提出并进行相关研究的，蚂蚁这种小生物，个体能力非常有限，但实际的活动中却可以搬动自己大几十倍的物体，其有序的合作能力可以与人类的集体完成浩大的工程非常相似，它们之前可以进行信息的交流，各自负责自己的任务，整个运作过程统一有序，在一只蚂蚁找食物的过程中，在自己走过的足迹上洒下某种物质，以传达信息给伙伴，吸引同伴向自己走过的路径上靠拢，当有一只蚂蚁找到食物后，它还可以沿着自己走过的路径返回，这样一来找到食物的蚂蚁走过的路径上信息传递物质的量就比较大，更多的蚂蚁就可能以更大的机率来选择这条路径，越来越多的蚂蚁都集中在这条路径上，蚂蚁就会成群结队在蚁窝与食物间的路径上工作。当然，信息传递物质会随着时间的推移而消失掉一部分，留下一部分，其含量是处于动态变化之中，起初，在没有蚂蚁找到食物的时候，其实所有从蚁窝出发的蚂蚁是保持一种随机的运动状态而进行食物搜索的，因此，这时，各蚂蚁间信息传递物质的参考其实是没有价值的，当有一只蚂蚁找到食物后，该蚂蚁一般就会向着出发地返回，这样，该蚂蚁来回一趟在自己的路径上留下的信息传递物质就相对较多，蚂蚁向着信息传递物质比较高的路径上运动，更多的蚂蚁就会选择找到食物的路径，而蚂蚁有时不一定向着信

息传递物质量高的路径走，可能搜索其它的路径。这样如果搜索到更短的路径后，蚂蚁又会往更短的路径上靠拢，最终多数蚂蚁在最短路径上工作。【基于蚁群算法和遗传算法的机器人路径规划研究】 该算法的特点： (1)自我组织能力，蚂蚁不需要知道整体环境信息，只需要得到自己周围的信息，并且通过信息传递物质来作用于周围的环境，根据其他蚂蚁的信息素来判断自己的路径。 (2)正反馈机制，蚂蚁在运动的过程中，收到其他蚂蚁的信息素影响，对于某路径上信息素越强的路径，其转向该路径的概率就越大，从而更容易使得蚁群寻找到最短的避障路径。 (3)易于与其他算法结合，现实中蚂蚁的工作过程简单，单位蚂蚁的任务也比较单一，因而蚁群算法的规则也比较简单，稳定性好，易于和其他算法结合使得避障路径规划效果更好。 (4)具有并行搜索能力探索过程彼此独立又相互影响，具备并行搜索能力，这样既可以保持解的多样性，又能够加速最优解的发现。 4.1.2 基本蚁群算法的生物仿真模型 a为蚂蚁所在洞穴,food为食物所在区,假设abde为一条路径,eadf为另外一条路径,蚂蚁走过后会留下信息素,5分钟后蚂蚁在两条路径上留下的信息素的量都为3,概率可以认为相同,而30分钟后baed路径上的信息素的量为60,明显大于eadf路径上的信息素的量。最终蚂蚁会完全选择abed这条最短路径,由此可见,

基于蚁群算法的MATLAB实现

基于蚁群算法的机器人路径规划MATLAB源代码 基本思路是，使用离散化网格对带有障碍物的地图环境建模，将地图环境转化为邻接矩阵，最后使用蚁群算法寻找最短路径。 function [ROUTES,PL,Tau]=ACASPS(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 基于蚁群算法的机器人路径规划 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→https://www.sodocs.net/doc/dc12250003.html,/greensim %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N

(完整版)蚁群算法matlab程序实例整理

function [y,val]=QACS tic load att48 att48; MAXIT=300; % 最大循环次数 NC=48; % 城市个数 tao=ones(48,48);% 初始时刻各边上的信息最为1 rho=0.2; % 挥发系数 alpha=1; beta=2; Q=100; mant=20; % 蚂蚁数量 iter=0; % 记录迭代次数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2); end end bestroute=zeros(1,48); % 用来记录最优路径 routelength=inf; % 用来记录当前找到的最优路径长度 % for i=1:mant % 确定各蚂蚁初始的位置 % end for ite=1:MAXIT for ka=1:mant %考查第K只蚂蚁 deltatao=zeros(48,48); % 第K只蚂蚁移动前各边上的信息增量为零 [routek,lengthk]=travel(distance,tao,alpha,beta); if lengthk

蚁群算法最短路径通用Matlab程序(附图)

蚁群算法最短路径通用Matlab程序（附图） function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.sodocs.net/doc/dc12250003.html, % All rights reserved %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N if ix==-0.5

图的匹配——匈牙利算法与KM算法

图的匹配 一、什么是图的匹配 1.图的定义 无向图：无向图G 是指非空有限集合V G ，和V G 中某些元素的无序对的集合E G ，构成的二元组(V G ，E G )。V G 称为G 的顶点集，其中的元素称为G 的顶点。E G 称为G 的边集，其中的元素称为G 的边。在不混淆的情况下，有时记V ＝V G ，E ＝E G 。如果V ＝{v 1,…,v n }，那么E 中的元素e 与V 中某两个元素构成的无序对(v i ，v j )相对应，记e ＝v i v j ，或e ＝v j v i 。在分析问题时，我们通常可以用小圆圈表示顶点，用小圆圈之的连线表示边。 二分图：设G 是一个图。如果存在V G 的一个划分X ，Y ，使得G 的任何一条边的一个端点在X 中，另一个端点在Y 中，则称G 为二分图，记作G ＝(X ，Y ，E)。如果G 中X 的每个顶点都与Y 的每个顶点相邻，则称G 为完全二分图。 2.匹配的相关概念 设G ＝(V ，E)是一个图，E M ?，如果M 不含环且任意两边都不相邻，则称M 为G 的一个匹配。G 中边数最多的匹配称为G 的最大匹配。 对于图G ＝(V ，E)，在每条边e 上赋一个实数权w(e)。设M 是G 的一个匹配。定义∑∈=m e e w M w )()(，并称之为匹配M 的权。G 中权最大的匹配称为G 的最大权匹配。如果 对一切，e ∈E ，w(e)=1,则G 的最大权匹配就是G 的最大匹配。 设M 是图G=(V ,E)的一个匹配，v i ∈V 。若v i 与M 中的边相关联，则称v i 是M 饱和点，否则称v i 为M 非饱和点。 如果G 中每个顶点都是M 饱和点，则称M 为G 的完美匹配。 设M 是G 的一个匹配，P 是G 的一条链。如果P 的边交替地一条是M 中的边，一条不是M 中的边，则称P 为M 交错链。类似地，我们可以定义G 的交错圈。易知，G 的交错圈一定是偶圈。 一条连接两个不同的M 非饱和点的M 交错链称为M 增广链。 两个集合S 1与S 2的“异或”操作S 1⊕S 2是指集合S 1⊕S 2＝（S 1∩S 2）\（S 1∪S 2） 容易看出，设M 是G 的匹配，P 是G 中的M 增广链、则M ⊕P 也是G 的匹配，而且1+=⊕M P M 。 图表 1 “异或”操作 可以证明，G 中匹配M 是最大匹配当且仅当G 中没有M 增广链。

匈牙利算法

匈牙利算法(Edmonds算法)步聚： (1)首先用（*）标记X中所有的非M顶点，然后交替进行步骤（2），（3）。 (2)选取一个刚标记（用（*）或在步骤（3）中用（y i）标记）过的X中顶点，例如顶点x ，如果x i与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过,则用（x i）i 去标记Y中顶点y。重复步骤(2)，直至对刚标记过的X中顶点全部完成一遍上述过程。 (3)选取一个刚标记（在步骤(2)中用(x i)标记）过的Y中结点，例如y i，如果y i与x为 同一匹配边的两端点，且在本步骤中x尚未被标记过，则用(y i)去标记X中结点x。 重复步骤(3)，直至对刚标记过的Y中结点全部完成一遍上述过程。 (2),(3)交替执行，直到下述情况之一出现为止： (I)标记到一个Y中顶点y，它不是M顶点。这时从y出发循标记回溯，直到（*）标 记的X中顶点x，我们求得一条交替链。设其长度为2k+1，显然其中k条是匹配 边，k+1条是非匹配边。 (II)步骤(2)或(3)找不到可标记结点，而又不是情况(I)。 (4)当(2),(3)步骤中断于情况(I)，则将交替链中非匹配边改为匹配边，原匹配边改为非 匹配边(从而得到一个比原匹配多一条边的新匹配)，回到步骤(1)，同时消除一切现有 标记。 (5)对一切可能,(2)和(3)步骤均中断于情况(II),或步骤(1)无可标记结点,算法终止 (算法找不到交替链). 以上算法说穿了，就是从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过交替出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。 下面给出此算法的一个例子：

蚁群算法最短路径matlab程序

蚁群算法最短路径通用Matlab程序 下面的程序是蚁群算法在最短路中的应用，稍加扩展即可应用于机器人路径规划 function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% ---------------------------------------------------------------% ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.sodocs.net/doc/dc12250003.html, % All rights reserved %% ---------------------------------------------------------------% 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N if ix==-0.5 ix=MM-0.5;

匈牙利算法的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)

蚁群算法解决TSP问题的MATLAB程序

蚁群算法TSP(旅行商问题)通用matlab程序 function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha, Beta,Rho,Q) %%=================================================================== %% ACA TSP.m %% Ant Colony Algorithm for Traveling Salesman Problem %% ChengAihua,PLA Information Engineering University,ZhengZhou,China %% Email:aihuacheng@https://www.sodocs.net/doc/dc12250003.html, %% All rights reserved %%------------------------------------------------------------------------- %% 主要符号说明 %% C n个城市的坐标，n×2的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%=================================================================== %%第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5; else D(i,j)=eps; end D(j,i)=D(i,j); end end Eta=1./D;%Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n);%Tau为信息素矩阵 Tabu=zeros(m,n);%存储并记录路径的生成 NC=1;%迭代计数器 R_best=zeros(NC_max,n);%各代最佳路线 L_best=inf.*ones(NC_max,1);%各代最佳路线的长度 L_ave=zeros(NC_max,1);%各代路线的平均长度

蚁群算法TSP(旅行商问题)通用matlab程序

蚁群算法TSP(旅行商问题)通用matlab程序！！ function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,B eta,Rho,Q) %%================================================================ ========= %% ACATSP.m %% Ant Colony Algorithm for Traveling Salesman Problem %% ChengAihua,PLA Information Engineering University,ZhengZhou,China %% Email:aihuacheng@https://www.sodocs.net/doc/dc12250003.html, %% All rights reserved %%------------------------------------------------------------------------- %% 主要符号说明 %% C n个城市的坐标，n×2的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%================================================================ ========= %%第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5; else D(i,j)=eps; end D(j,i)=D(i,j); end end Eta=1./D;%Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n);%Tau为信息素矩阵 Tabu=zeros(m,n);%存储并记录路径的生成 NC=1;%迭代计数器 R_best=zeros(NC_max,n);%各代最佳路线 L_best=inf.*ones(NC_max,1);%各代最佳路线的长度

匈牙利算法

匈牙利算法： 匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家DénesK?nig和Jen?Egerváry 的工作之上创建起来的。 设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集V1，V2，选择这样的子集中边数最大的子集称为图的最大匹配问题（maximalmatchingproblem)。 果一个匹配中，|V1|≤|V2|且匹配数|M|=|V1|，则称此匹配为完全匹配，也称作完备匹配。特别的当|V1|=|V2|称为完美匹配。 作用： 解决指派问题。所谓的指派问题就比如：甲乙丙三个人去做ABC 三件事情。每个人做每件事情所花的时间可能不一样。每个人只能安排一件事情，问怎样安排才能使三个人所工作的时间之和最小？ 扩展成n个人n件事也可以，但要求是： 事情数和人数一样多 每人只能做一件事 这样的问题就称作指派问题 匈牙利算法就是解决这样的问题的。 步骤概括： 每行减去此行最小数

判断是否达到算法目标，如未达到算法目标，继续下一步。否则结束。 横纵交替，从行开始。找出所有还没有选中0的行（具体见步骤实例），在此行后面打钩；把此行中有0的列全打钩。在打钩的列中，如果有零，又在有0的行打钩，如此交替，直到不能再打钩。 在没有打钩的行和打钩的列上划线，会得到发现所有的0已经被划去，如果没有划去，请检查前面的步骤。此时剩下的所有元素中，找到最小值，就记为min吧。 在第4步画线的行减去min（此时原来的0变成-min)，再在画线的列加上min(此时矩阵中没有了负数）。回到第2步。

蚁群算法求解TSP问题MATLAB程序

%% 蚁群算法¨ clear close clc n = 10; % 城市数量 m = 100; % 蚂蚁数量 alfa = 1.5; beta = 2.5; rho = 0.1; Q = 1000; maxgen = 50; x = [2 14 9 6 3 2 4 8 12 5]'; y = [8 9 12 4 1 2 5 8 1 15]'; % x = [37,49,52,20,40,21,17,31,52,51,42,31,5,12,36,52,27,17,13,57,62,42,16,8,7,27,30, 43,58,58,37,38,46,61,62,63,32,45,59,5,10,21,5,30,39,32,25,25,48,56,30]'; % y = [52,49,64,26,30,47,63,62,33,21,41,32,25,42,16,41,23,33,13,58,42,57,57,52,38,68, 48,67,48,27,69,46,10,33,63,69,22,35,15,6,17,10,64,15,10,39,32,55,28,37,40]'; City = [x,y]; % 城市坐标 %% 城市之间的距离 for i = 1:n D(i,:) = ((City(i,1) - City(:,1)).^2 + (City(i,2) - City(:,2)).^2).^0.5 + eps; end eta = 1./D; % 启发因子 tau = ones(n); % 信息素矩阵 path = zeros(m,n); % 记录路径 for iter = 1: maxgen %% 放置蚂蚁 path(:,1) = randi([1 n],m,1); for i = 2 : n for j = 1 : m visited = path(j,1:i-1); leftcity = setdiff(1:n,visited); %% 计算剩下城市的概率 P = zeros(1,length(leftcity)); for k = 1:length(leftcity) P(k) = tau(visited(end),leftcity(k))^alfa*eta(visited(end),leftcity(k))^beta;%判断是否有重复城市 end P1 = sum(P); Pk = P / P1; P = cumsum(Pk); r = rand; index = find(P >= r); nextcity = leftcity(index(1)); path(j,i) = nextcity; end end for flag = 1:m if length(unique(path(flag,:))) ~= n % keyboard; end end if iter >= 2 path(1,:) = Pathbest(iter-1,:); end for i = 1 : m