某运输公司为10个客户配送货物,假定提货点就在客户1所在的位置,从第i个客户到第j个客户的路线距离用下面矩阵中的 位置上的数表示(其中 表示两个客户之间无直接的路线到达)。
3 f. {) j# M) [! c9 [2 E" E4 r0 x% m% D. z# E( |
1、运送员在给第二个客户卸货完成的时候,临时接到新的调度通知,让他先给客户10送货,已知送给客户10的货已在运送员的车上,请帮运送员设计一个到客户10的尽可能短的行使路线(假定上述矩阵中给出了所有可能的路线选择)。, T* c7 d" M3 O1 i
- }+ D9 k0 K: k; q4 o3 f e' U! t2、现运输公司派了一辆大的货车为这10个客户配送货物,假定这辆货车一次能装满10个客户所需要的全部货物,请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线?对所设计的算法进行分析。
% r; k! L7 z( L& W$ a; }8 ~8 Y$ H5 S# H
|