%?Auction?algorithm?for?solving?2-D?Assignment?problem
%?by?Yanhua?Ruan
%?June.121999?modified?in?Dec.201999?a?Gauss-Seidel?version


function?[qomigaassign]=auc2（befi）

AUCTION_2D_SCALE=0.25;
AUCTION_2D_MAXC=1000.0;
AUCTION_2D_FACTOR=8;
AUCTION_2D_DECRFACTOR=4;??%?4<=.?.?<=10
AUCTION_2D_ENDEPS=1;
AUCTION_2D_MAXTHRESH=100;
AUCTION_2D_SMALL=realmin;

%?scaling?make?1.?all?elements?be?positive;?2.?the?smallest?element?be?1.
s1=min（min（befi））;
if?s1<0
???befi=befi-s1;
end

[nu1nu2v]=find（befi）;
s2=min（v）;?%?spz?befi>0?already.?
befi=befi./s2;

[n_personn_object]=size（befi）;
price=zeros（1n_object）;?%??init.?price?for?each?object

assign=zeros（n_object1）;
curlst=linspace（1n_personn_person）;
numnew?=?n_person;

epsilon?=?1;?
thresh?=?min（n_person/5AUCTION_2D_MAXTHRESH）;
C?=?max（max（befi））;?%?spz?befi>0?already.?
%startdecr?=?C/3;??%?C/5<=..<=C/2
%decr=max（startdecrepsilon）;?%?decide?the?resolution?of?the?algorithm.
decr=epsilon;

while?（numnew>thresh）|（（numnew>0））
???nolist=numnew;??%?the?number?of?unsigned?person
???numnew=0;

???for?i=1:nolist
??????row?=?curlst（i）;
??????bstcol=0;
??????
		tmax=befi（row1:n_object）-price（1:n_object）;
		[max1?bstcol]=max（tmax）;
		tmax（bstcol）=-realmax;
		max2=max（tmax）;
??????
??????if?bstcol?~=?0
?????????price（bstcol）?=?price（bstcol）+max1-max2+decr;?
?????????oldrow?=?assign（bstcol）;
?????????assign（bstcol）?=?row;
?????????if?oldrow?>?0
????????????numnew?=?numnew?+?1;????????????
????????????curlst（numnew）?=?oldrow;
?????????end
??????end???
???end?
???%decr=max（decr/AUCTION_2D_DECRFACTORepsilon）;
???%decr=max（decr/1.414?.0001）;
end??%?while

omiga=zeros（n_personn_object）;

q=0;
for?i=1:n_object
???if?assign（i）~=0
??????omiga（assign（i）i）=1;
	??q=q+befi（assign（i）i）;??????
???end???
end???
%?scaling?back
q?=?q*s2+s1*n_person*（s1<0）;

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????1894??2002-03-20?20:34??auc.m
?????文件?????????517??2001-11-01?08:55??auction.m
?????文件?????????902??2001-11-01?08:51??auction_2D.m
?????文件?????????919??2002-03-02?12:33??CalcMeasCov2.m
?????文件?????????106??2002-02-26?17:39??close_demo.m
?????文件???????10104??2002-03-05?08:46??dis_cen_demo.m
?????文件?????????594??2001-11-01?10:08??find_assi_index.m
?????文件?????????570??1999-05-18?13:00??GAUSSPDF.M
?????文件????????5320??2002-03-01?09:11??gene_2d_2sen.m
?????文件?????????937??2002-02-27?12:09??gene_2d_scn.m
?????文件????????4678??2002-03-01?11:38??gene_2d_sen1.m
?????文件????????4773??2002-03-01?11:38??gene_2d_sen2.m
?????文件????????1011??2000-02-02?12:04??get_approx_cov.m
?????文件????????1049??2000-05-27?09:45??get_approx_cov1.m
?????文件?????????724??2001-09-07?05:03??get_ellipsoid_gate.m
?????文件?????????117??2001-03-11?14:34??get_meas_number.m
?????文件?????????295??2002-02-26?17:58??info_demo.m
?????文件?????????221??2001-03-04?12:57??LLR_deduct_meas.m
?????文件?????????512??2001-03-15?09:58??LLR_Gau_PDA2.m
?????文件????????2644??2002-03-20?21:33??lr_3d_kalman.m
?????文件????????2053??2002-03-03?10:36??lr_kalman.m
?????文件????????4169??2002-03-05?08:52??MDL_demo.m
?????文件????????6107??2002-03-05?08:50??MDL_demo2.m
?????文件????????2550??2002-03-05?09:07??MDL_demo3.m
?????文件????????1768??2001-11-04?13:52??myLinProg.m
?????文件????????6594??2001-11-01?10:03??mySD.m
?????文件????????2509??2001-11-04?15:42??PDAKALMAN.M
?????文件????????5234??2002-03-20?17:26??plot_2d_KF1.m
?????文件????????5150??2002-03-21?09:35??plot_2d_pda1.m
?????文件???????16947??2002-03-21?13:18??plot_3d_KF1.m
?????文件???????14236??2002-03-21?13:18??plot_3d_PDA1.m
............此處省略20個文件信息