
COMPUTER ENGINEERING
1999 25 8 Vol.25 No.8 1999



ͼA*㷨SQLⷨ
ԥۣ¥
ժҪͼA*㷨SQL㷨ݿ洢ͼԭʼݣSQLA*㷨ҪȡĽ⣬˱̡
ؼʣͼA*㷨SQL
Use SQL Soluting A* Algorithm in Graph Searching
Jia Nayu,Li Hui,Lou Rongsheng
(Dept. of Computer Science,Fudan University,Shanghai 200433)
AbstractThes paper researchs two graph searching algorithms:A* Algorithm and SQI.Algorithm.It uses database to store initiative data in a graph and uses SQL to get A* Algorithm's solution,it can simplify the programming in this area.
Key wordsGraph search;A* Algorithm;SQL language
1  
ͼѰ·̵㷨 GraphSearch :
(1) һֻгʼ s ͼ G=(N,E),N={s},E=   s  һ OPEN δչС 
(2) һ CLOSED չʼΪձ 
(3) LOOP:  OPEN Ϊգʧ˳ 
(4) ѡ OPEN ϵĵһ㣬 OPEN ƳŽ CLOSED Сƴ˽Ϊ n  
(5)  n ΪһĿ㣬нⲢɹ˳˽׷ͼ G űߴ n  s ·õ 
(6) չ n ɲ n ȵЩ̽ļ M  
(7)  N=N  M,E=E  {(n,m)|m  M},  M ЩԱӽ OPEN Ѿ OPEN  CLOSED ϵÿһ M Ա m ɾȥͨ s Ĵ۽ϴıߣ OPEN еӦ㡣뱻ɾıĽ㣬 CLOSED УҪĺ m. 
(8) ĳһʽ OPEN  
(9) GO LOOP 

ͼ 1 Ʒʾͼ 
㷨 GraphSearch ĵ 8  ,OPEN ϵĽԱܹѡһ '  ' ΪĲչá 
 1 ͨͼС·ߣͼ 1 㣬ߵͼϵǴۡ 
 A Ϊ㣬 E Ϊյ㡣㷨Ϊ 
 1  2  
 G={N,E},N={A},E=   OPEN={A},CLOSED={} 
 3  9  
 5  N=E ΪĿᣬɹ˳׷ϱһ֪ʼ A յ E · A  B  D  E, Ϊ 11
1  Open
ʼչNM·С
1OPEN={}
CLOSED={A}N=AB,C,DM={B,C,D}
OPEN={B,C,D}(A B)(A C)
(A D)
2OPEN={C,D}
CLOSED={A,B}N=BC,DM={C,D}
OPEN={C,D}(A B)(A C)
(B C)(B D)
3OPEN={D}
CLOSED={A,B,C}N=CD,EM={D,E}
OPEN={D,E}(A B)(A C)(B C)
(B D)(C E)
4OPEN={E}
CLOSED={A,B,C,D}N=DEM={E}
OPEN={E}(A B)(A C)(B D)
(D E)
5OPEN={}
CLOSED={A,B,C,D,E}N=E

2 A* 㷨 
A* 㷨УһرĹƺ f ֵ f(n) ʾʼ S  n С·ӽ n ĿС·Ĵ֮ͣ f(n)=g(n)+h(n)  f(n) Ǵ n յһС·Ĵۡ OPEN ϾС f ֵǸΪе N ²չ 
ͼУ n 庯 h*(n) ʾӽ n ĿС ( ȷ )  g*(n) ʾʼ S  n Сۣ㷨 g*(n)=g(n)  f*(n)=g*(n)+h*(n) ʾʼ S ͨ n ĿСۡ n Ŀͨ·ʱ h*(n) ޶塣 
 h*(n) йصϢԳ h* Ϊ 
 A* 㷨гʹ OPEN  CLOSED ⣬Ҫһ (x,y) С۵ĺ h(x,y)  
㷨 GraphSearch ĵ 4 Ϊ 
(4)  OPEN ȡ g(n)+h(n,b) СĶ n Ƴ CLOSED  
/*g(n) Ϊʼ s  n Ĵۣ h(n,b) Ϊ n  b Ĵ*/ 
ͬʱȡ (8)  A* 㷨 
 2  1 У A չ 3  B  C  D ͼɵã 
g*(B)=2, g*(C)=3, g*(D)=7 
ѡȡ g* Сĵ B һչ C,D,  g*(D)=2+4=6,g*(C)=2+3=5, ϴεչ g*(C)=3(  A-C),  g*(C)=5(  A-B-C) ȥ g*(D)=6(  A-B-D) չ A ʱ g*(D)=7(  A-D) ֵչ D ֵ E  C  g*(E)=2+4+5=11(  A->B->D->E),g*(C)=2+4+4=10(  A->B->D->C) ֵҲȥ 
ݿ֧֣ɰѺ h ľȷֵȴݿУ㷨Чʡ 
3 ݿֵ֧ͼ㷨 
ݿ SQL ʵʼ㵽Ŀ·ͼ⡣ SQL ǻڼϸϵķǹԣû A* 㷨չĸǸ WHERE   һλ  ģȫһµ˼·һ£ 
 3  1 ĽͨͼĶ㡢߼Ȩһͨͼԭʼݿ⣬ṹ 
Citytraf(n1 CHAR(1),n2 CHAR(1)  d NUMBER(2)) ͼ 2 ʾԴΪĴ۱ 
Cityttaf 
n1 A,A,A,B,B,C,C,D
n2 B,C,D,C,D,D,E,E
d 2,3,7,3,4,4,10,5

ͼ 2 ۱ 
 Citytraf ԵõκСۣһ⣬ʼֵ 
Citytray 
Create Table Oper(n1,n2,d) as select n1,n2,d 
From Citytraf 
ӱ Citytraf  Oper иѡһ n1, n2 ǿܵ·Ĵۣ Oper У 
Insert into Oper 
Select Citytraf.n1,Oper.n2,Citytraf.d+Oper.d 
From Citytraf,Oper 
Where Citytraf.n2=Oper.n1 
ȨСߣ 
Create Table End(n1,n2,d) /* С */ 
Insert into End 
Select n1,n2,min(d) /* ȡ d С */ 
From Oper 
Group by n1,n2 /* ȥ n1,n2 ظļ¼ */ 
 SQL ޵ݹ鴦ܣγƷִɴΣֱµС End еļ¼ͨ·ĵԵСۡ 
Ϊҳ㣬 A  E С۵· PATH ½ 
Create Table PATH(n1,n2,d) /* һ· */ 
Insert into PATH 
/* ·д㿪ʼĵһ */ 
Select C1.n1,C1.n2,C1.d From Citytraf C1,End E1 
Where C1.n1='A' and E1.n1=C1.n2 
and C1.d+E1.d=(Select d from End where n1='A' and n2='E') 
UNION /* ·гһмθ */ 
Select E1.n1,E1.n2,E1.d from End E1,End E2,Citytraf C  End E2 
Where C.n1='A' and E1.n1=C.n2 and E1.n2=E2.n1 and E2.n2='E' 
and E1.d+C.d+E2.d=(Select d From End Where n1='A' and n2='E') 
UNION /* ·յı */ 
Select C1.n1,C1.n2,C1.d From Citytraf C1,End E1 
Where C1.n2='E' and E1.n1=C1.n2 
and C1.d+E1.d=(Select d from End where n1='A' and n2='E') 
UNION /* ·ͼһ */ 
Select n1,n2,d from Citytraf 
Where n1='A' and n2='E' 
ʾ Path еļ¼·ĸ㡣 
4 
A* 㷨˼ʼ A  S( һ ) Ĵ⣬ͬʱҪ S  B( Ŀ ) Ĵۡ A  S  B Ȼ·Ӷÿѡ ' ȷ ' Ľչ A* 㷨ĸڼ S  B СϡݲͬҵӦ A* 㷨ĺġ 
ʹݿⷽʱԭʼݶһУ㷨 Graph-search ĸԾת˶ԭʼݿĲѯĸԡ· A  S  B У A  S  S  B(S Ϊ A  B ·һ ) Ĵۺ SQL ݿвѯпɱȽϳСĴۡʱֻҪܰ A  B( С ) ֽʼ㡢м㡢ĿΪ⡣ 
SQL ⷨصǱ˷ӵı⣬ SQL ǷǹԣֻҪȷд·Զҵһ·еıߣݿ⻷ºʵ֣ν̾ҪݿƺǡôдǱ׼ SQL Իܴ 3GL ܴȫ⣬ѿݹ鹦 SQL ޷һЩȻܽ⵫Чʵ£Щ SQL   мһЩʩչĹܣ DB2 е WITH 䣬 Oracle е PL/SQL ȣЩǷǱ׼ʩӰ˳ĿֲԣĲۣձǰ SQL Ƕ뵽һ 3GL Уʹڵ DBMS Ҫ 3GL Եһ SQL 㷨Ͳ 3GL  SQL 㷨оǺġ
ߵλѧϵϺ 200433
ο 
1 Ӿ , ʩ . ݽṹ . Ϻѧ ,1994 
2  . ͼ . ʳ ,1985 
3 ˷ . ͳƷ . ѧϵ ,1991 
4 ʩ ,  , ¥ . ݿϵͳ . ߵȽ  ,1994 
