消防车辆出动的最短路线优化算法

(,065000):,,,。:;;:TU998:B:1009-0029(2005)05-0629-021,GIS。GIS,、。119。1s～3s,,。,Dijkstra,Dijkstra。22.1Dijkstra,。。O(n2),,n。2.2Bellman-Ford-MooreO(nm),,m/。,。Dijkstra。2.3Floyd,O(n3)。Dijkstra,。2.4--A*A*。:,,,,。3,。,。,。AB,AB。,A→BB→A。A→BB→A。,V={0,1,…,n-1},、。3.1Dijkstra,,。Dijkstra,,。,,,。,,,。,,,,Dijkstra,。Dijkstra,,O(n2)。,。(,),。50%,,O(bd/2),b,d92620059245。3.2,。,,,,、。,。,,。。,、、。(),,。,00:00-07:00,07:00-08:30,08:30-11:00,11:00-15:00,15:00-17:00;17:00-20:00,20:00-24:00。,。,。。,,,。,V0,V3。1,V23V435020,V0-V2-V3。2,V4340,V23,,V0-V4-V3。12,,。4,,,。12:[1]RKAhuja,KMehlhorn,JBOrlin,RETarjan.Fasteralgorithmsfortheshortestpathproblem[J].JournaloftheAssociationforComputingMachinery,1990,37(2):213-223.[2],.[M].:,1997.[3],,.[M].:,2004.OptimizingtheshortpathalgorithmonsteeringvehicleoffirefightingRENShao-yun(TheChinesePeople'sArmedPoliceForcesAcademy,Langfang065000,China)Abstract:Discussthedescriptionofroute-netandhowtogetasuitablecalibrationofroad-impedanceformakingthevehiclegoquicklytotheterminal,givethecorrespondingsolutionsintheory.Keywords:firevehicles;shortestpath;optimizationalgorithm:(1978-),,,,,,065000。:2005-03-22036FireScienceandTechnology,September2005,Vol24,No.5