灾情巡视路线

19 组 袁光辉 唐少君 代悦灾情巡视路线摘要本文解决的是设计最佳灾情巡视路线的问题，是经典的货郎但问题，为解决此问题，本文利用了算法prim和函数Floyd、router，对所给的公路网示意图进行

19 组袁光辉唐少君代悦 灾情巡视路线 摘要 本文解决的是设计最佳灾情巡视路线的问题，是经典的货郎但问题，为解决此问 primFloydrouter 题，本文利用了算法和函数、，对所给的公路网示意图进行分 析，做出最小生成树和最短路径图，根据图论知识和图形分析。最后建立了一个 —— 最小路径的模型最小边权模型。 对于问题一，我们确定的最佳巡视路线为 第一 O-1-B-A-34-35-33-31-32-30-Q-28-27-24-23-N-26-P-29-R- 组 O 第二 O-M-25-21-K-22-17-16-I-15-14-13-J-18-J-19-20-L-6-5-2-O 组 O-C-3-D-4-8-E-9-F-10-F-12-H-12-G-11-D-3-2-O 第三 组 24 对于问题二，我们得到，要在小时内完成巡视，至少应分四组；在该分组下 的最佳巡视路线为 第一 O-C-B-34-35-32-31-32-30-Q-29-R-A-1-O 组 第二 O-P-28-27-24-23-22-(17)-K-21-20-25-N-26-(P)-O 组 第三 O-2-5-6-L-19-J-13-14-H-14-15-I-18-(K)-(21)-(25)-M- 组 O 第四 O-(2)- (5) –(6)-7-E-11-G-12-F-10-E-8-4-D-3-2-O 组 对于问题三，如果巡视人员足够多，在巡视唯一一个乡镇或村的情况下最短时间 6.436.43 为，所以在以下分组过程中那个时间不超过的原则进行分组；分组为： 1 O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-O H 6.43 2 O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O 13\14 6.16 1