ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



㷨:㷨ضλһֿɲķ
δܺ
ժҪ㷨ʵ㷨ضλһֿɲķ.¸㷨ضλĶ,ͨѡϲ㷨.Ȼ˶ѡϲһַ.㷨ܵõĳһ㷨ģʽ,Ӹ㷨ģʽͿ㷨.㷨ܺ㷨ģʽԼģ黯㷨֮Ĺϵ.о㷨ضλɲķԶͻѧϰҪ.
ؼʡ㷨,Զ,㷨ضλ.
ͼšTP301
Algorithm Framework: an Operational 
Approach to Algorithm Relocation
LUAN Shang-min1 LI Wei1 MA Shao-han2
1(Department of Computer Science and Engineering Beijing University of Aeronautics and Astronautics Beijing 100083)
2(Department of Computer Science Shandong University Ji'nan 250100)
Abstract Algorithm framework is an operational approach to algorithm relocation. In this paper, the authors present the definition of algorithm relocation and an algorithm framework based on selection operator and combination operator. The authors discuss how to design selection operator and combination operator. The algorithm for a given problem can be obtained from the algorithm schema, which is obtained from the algorithm framework presented in this paper. The relationship between algorithm framework and algorithm schema and the relationship between algorithm framework and modular algorithm are discussed as well. Algorithm relocation and its operational approach are significant for software automation and machine-learning.
Key wordsAlgorithm design, software automation, algorithm relocation.
㷨ԶԶѵ͹ؼ.㷨һ֪ʶ߶ܼĴԻ,Ҫʵ㷨Զ,ѶȺܴ.㷨ԶԶɷȻȡһĽչ14,,Щֻɾضṹ㷨,ѭ㷨͵ݹ㷨,ֻض㷨,Ŀǰûһͨ㷨ķ.
L1ڰԶ㷨ϵͳNDADAS(ND algorithm design automation system)вԼķ,ַɾضṹ㷨,ѭ㷨͵ݹ㷨.Helman2ݸһ͸һ㷨ģʽ,ͨ㷨ģʽõĶ̬滮ͷ֦޽㷨.ǽһƹHelmanķ,һ㷨ģʽ3.ͨ㷨ģʽ,ǲԵõ̬滮ͷ֦޽㷨,ҿԵõ̰ĺͻ㷨.,ǣ4ָһ㷨ģʽõĻ㷨,ַʵ㷨Զֻһ.
Ĵ㷨ضλĽǶʵ㷨Զ.ȸ㷨ضλĶ,㷨ܵ,ԼɲԿƹϵͱ任ϲϲ.㷨ܿԵõĳһ㷨ģʽ,㷨ģʽõ㷨,ԣף24㷨ģʽɱ㷨ܵõ.㷨ܺģ黯㷨5֮Ĺϵ.㷨㷨ضλһֿɲķ,о㷨ضλɲķʵ㷨ƵԶͻѧϰҪ.
ŻΪ.nԪa1,a2,...,an,ÿһaiӦһֵ,Ϊd(ai),1in,Թһ,nԪΪҶڵ,ʹLi*d(ai)С.,LiǴӸڵ㵽ΪaiҶڵ·.
1 㷨ضλĶ㷨ܵ
㷨ضλ㷨֮ǰ,Ľṹʵ,Ҳ˵һ⼰ʵ.Ҫ˵,㷨ܲ,ֻΪ˷.
1.1(Ľṹ). öԪP=A,QĽṹ,,Aԭӵļ.MSʾвмļ,Ƕļ,Ҳһļ,һϵļϵȵ.Qǽļ.
1.2(ʵ). Ԫ顴P,I,,dʵ.,PĽṹ,;Iǳʼ״̬ļ;һQϵƫϵ;dһ,ĳЩ,ɵŻ.ĳЩҲ,,SATӾļ.
,ŻΪ˵ķ.
A={a1,a2,...,an}
Q={t|ta1,a2,...,anΪҶڵĶ}
I={a1,a2,...,an}
da1,a2,...,anֵ.Ϊ˶ƫϵ,ӦMSϵһf:
AA,tAеԪΪҶڵĶ,

t1,t2Q,f(t1)f(t2),t1t2.
1.3(㷨ضλ). ĳһ㷨,ǿԶ޸,Ӷıķ,ʹ޸ĺ㷨Ϊһ㷨,㷨޸ĳΪ㷨ضλ.
㷨ضλĶԿ,ĳһ㷨,ǿԶ޸,ʹķ˸ı,㷨Ȼԭ㷨,޸㷨ضλ.һ㷨,ǿͨ޸,ʹΪһ㷨.ķǷı,޸Ҳ㷨ضλ.
ֱϽ,һ㷨,ֻҪ޸ĳЩ,Ϳʹķı,ʹΪһ㷨.,Ĺ
Step1. MS=I.
Step2. t1ʹR1(t1),ͣ.MSѡһt1,ʹR1(t1).
Step3. SMSһӼ,Sеһt2,R2(t2).
Step4. Sеÿһt2,һt,ʹt1t2ֱtӺҶ,MS=MS+{t}.
Step5. GOTO Step 2.
IĴŻĳʼ״̬ļ.·ʽR1R2:
t1MSκ,t1ĴС,R1(t1);
t2MSκ,t2Ĵ۴С,R2(t2),
͵õŻ̰㷨.
·ʽR1R2:
MSдt,t1tûйԪΪҶڵ,ֱtt1ΪӺҶӵMS,t1Ĵ۱MSκһt3ĴС:t3AеnԪΪҶڵ,R1(t1);
t2MS,t2Ĵ۱MSκһt3ĴС:t3AеnԪΪҶڵ,R2(t2)
͵õŻķ֦-޽㷨.
һַ㷨Щͬĵط,ôҪ޸һ㷨ͳΪһ.Щͬĵط?⽫ļ.
Ĺ,Step 2ǴMSѡһһԪt1,ǳһΪѡ.Step 3ǴMSѡһһԪt2,Step 4ִб任tr(t1,t2);ǰִStep 3Step 4Ĺ̳Ϊϲ.ѡϲ׼ȷ.
Aһ,2AʾAݼ,AӼɵļ.
1.4(ѡ). ƲֺOP:2MSMSһѡ,OP:x2MS,OP(x)x.еѡɵļϼΪSS.,MSвмļ.
1.5(ϲ). ƲֺCOP:MS2MS2MSһϲ,еϲɵļϼΪCS.MSмļ.
Ǹѡϲһ㷨.
alframework()
begin
MS=I;
while (not complete(MS)) do
begin
select1 (SS,);
select2 (CS,);
end
end
end(alframework)
һ,еݾѡϲ.ǽϸ˵ͨ㷨ܵõ㷨.
2 ϲѡһַ
ڵ1ָ,ܶԸ㷨Ĳ֮ͬһ׼ȷ,ͿԺ׵ʵ㷨ضλ.潫.
2.1(ѡƹϵ). #MSϵһԪϵ,t1,t2Q,t1#t2ҽt1t2,#Ϊڡصѡƹϵ.
2.2(Ͽƹϵ). MSϵһԪϵ,t1,t2Q,t1t2,t2#t1һ,#ΪڡصϿƹϵ.
2.3(任). ֺtrMSMSMSһ,ֺtrΪ任.tr±ʽʾ.
2.4(Կƹϵ). #,ֱǹڡصѡƹϵϿƹϵ,ԡ#,ΪԿƹϵ.
ԻɵΪ˵ζһĳⷽĲԿƹϵͱ任.ڻɵϸμף6.Ҫϸɵķ֦-޽緽,趨²Կƹϵͱ任.
ѡƹϵ#:t1MS,t2Q,t2ıȨ֮Сt1ıȨ֮,t2#t1.
Ͽƹϵ:t1MS,t2Q,t2ıȨ֮Сt1ıȨ֮,t2#t1.
任tr(t1,t2):·֮ͺϲΪһ·.
ɵķ֦-޽㷨ѡƹϵϿƹϵͬ,ںܶ,Ҳǲͬ,Ķ̬滮㷨.ﻹҪ˵.(1) ĳЩ㷨,еĲҪѡƹϵϿƹϵ,SATGSAT7㷨,ֻϿƹϵ,Ϊ䵱ǰ,õnά.(2) Ͽƹϵʱڵǰ,ϵڲͬʱ̿ܲͬ.ѡϲ˵òԿƹϵѡϲ.

ݶԺ׵֤.
2.1. OP1OP2ѡ.
2.2. COP1COP2ϲ.
е㷨ͨﶨѡϲõ,ԶһЩµѡϲõҪ㷨.ڶһѡϲʱ,ӦʹѡϲõһЩ,ֻһ.ﶨѡϲԵõ4㷨ģʽ.
3 㷨ضλʵ
һڵ㷨ʵ㷨ضλ,Ҳ˵,ͨ㷨õ㷨.ѡϲ2,㷨еıеΪԿƹϵ.еĲԿƹϵȷѡѡϲ,Ҳȷһ㷨ģʽ,ٶ㷨ģʽеıδĺ壬͵õ㷨.磬Ҫõɵķ֦޽㷨,Ƕķ֦-޽緽ѡƺϿƺ,ҪѡOP1(MS)COP1(MS)Ϊѡϲ,ɵõµ㷨ģʽ.
algorithm HL
begin
MS=I;
while (not complete(MS)) do
begin
t=OP1(MS);
MS=COP1(t,MS);
end
end(algorithm)
ͦзֱ2жĻɵķ֦-޽緽ѡƹϵϿƹϵ,complete(MS)Ķͬף4ݸĶ,ٶ㷨ģʽеıS1(MS,,d);S2(MS,,t,B,d);S3(MS,,TS,T,t);S4(MS,,T,t)͵õɵķ֦-޽㷨..
S1(MS,,d):MSѡһԪ.
S2(MS,,t,B,d):MSͦзֱѡһԪغһѡƹϵ,ֱȡMSͦеԪʱΪnull.
S3(MS,,TS,T,t):MSѡһԪ,ҲһAеԭ,ԭͬʱԪغt,ֱȡMS·ʱΪnull;Ҳѡһ任Ϊֵһ.
S4(MS,,T,t):MSͦзֱѡһԪغһѡƹϵ,ֱȡMSͦеԪʱΪnull.
ֻҪѡȡѡOP2ϲCOP1,ٸԿƹϵʵͿԵõSATGSAT7㷨,ͨ㷨ҲԵõ㷨.ƪ,ϸ.ͨӿԿͨ㷨ʵ㷨ضλ.
4  
ǰ㷨ضλĶ,ѡϲ㷨,Լ㷨ܵõ㷨.˵ķʵ.Ƚһ,Ӧ㷨,Ȼڲͬѡϲ,岻ͬ,͵õ˲ͬ㷨ģʽ.㷨ģʽıʵ,ף3,4ж,ף6ݻC++ʵһϵͳ.ƪ,ﲻٶ,ȤĶμף3,4,6.
ĽǿԿ,ף24㷨ģʽɱ㷨ܵõ.ǻƹף24еĽ.,ѡǶף2,3ĺƹ,Ҳ˵ѡеһ.ͨѡƹϵͱ任Ժ׵ϲĹ,ף24ȴûһ.,ף24㷨ģʽǻһϸ,㷨ܲǻĳһ,ȻҲṹʵһ,ֻΪ۵ķ,ǻԸʽ,ƻڸѡϲͿ.
һ㷨,ĸӦõĲͬǸ㷨ǰ,ûбҪٸдԭ㷨,Ƹ㷨ģ黯㷨5.ķгʱ,Ѿһģ黯㷨˱,õ㷨ʱͿԽһ,㷨̳ʹ,ûбҪٶ½б.㷨,ķгʱ,Ҳͬŵ.,ڸһѡϲı,ٴõѡϲʱ,ûбҪ±,ֱӼ̳ʹþͿ.
оõȻѧ.,1968,ʿ,ʦ,ҪоΪ㷨Զ,ʽ,˹.δ,1943,ʿ,,ʿʦ,йѧԺԺʿ,ҪоΪ,,,˹.ܺ,1938,,ʿʦ,ҪоΪ㷨,㷨,˹.
ͨѶϵ:,100083,պѧѧ빤ϵ
ߵλδ(պѧѧ빤ϵ100083)ܺ(ɽѧѧϵϡ250100)
ο
1L Jian. Framework of algorithm correctness in NDADAS. Science in China (series A), 1991,34(7):875884
2Helman P. An algebra for search problems and their solution.In: Kanal L, Kumar V eds. Search in Artificial Intelligence.Berlin: Springer-Verlag, 1988.2890
3,ܺ.һʽ㷨.ѧ,1995,18(10):755762
(Luan Shang-min, Ma Shao-han. A common model for a class of problems and their algorithms. Chinese Journal of Computers, 1995,18(10):755762)
4,ܺ.Ĵ㷨.о뷢չ,1997,34(11):801806
(Luan Shang-min, Ma Shao-han. An algebraic model for seach problems and their algorithm. Computer Research and Development, 1997,34(11):801806)
5Tello E R. Objected-oriented Programming for Artificial Intellegence. Berlin: Springer-Verlag, 1989
6.ķƣ˶ʿѧλģ.:ɽѧ,1993
(Luan Shang-min. Object-oriented method base design MS. Thesis. Ji'nan: Shandong University, 1993)
7Selman B, Levesque H, Mitchell D. A new method for solving hard satisfiability problem.In: Clancey W ed. Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92). San Jose, CA: MIT Press, 1992. 440446
1998-02-23յԭ 
1998-08-27յ޸ĸ
