关于一类N车探险问题的有效算法  

Efficient algorithm for kind of exploration problem with N vehicles

作　　者：李晓亚[1] 崔晋川[1] 

机构地区：[1]中国科学院数学与系统科学研究院应用数学研究所,北京100190

出　　处：《系统工程学报》2008年第4期444-448,共5页Journal of Systems Engineering

基　　金：国家973计划资助项目(2006CB701306)

摘　　要：研究一类具有 N 车形式的探险问题.该问题要给出 N 辆车的行驶顺序,使得在该顺序下,N 辆车中至少有一辆车的行驶距离最远.通过建立模型,将原 N 车探险问题转化为一个关于 N 辆车的行车顺序的排序问题,该排序问题对应指数时间的复杂度.从两车情况入手,给出了两车探险问题的行驶距离最远的判定条件,并推广得到 N 车情况下探险问题的一个特例,给出该问题在特例情况下的有效算法,并证明了该算法可以求得特例的精确最优解.最后给出了计算实例.This paper studies a kind of exploration problem with N vehicles. That is ： how to arrange the travel order properly to make one of the vehicles go the farthest. By modeling, the authors trans- form the original exploration problem to a scheduling problem with an exponential computational time complexity. This paper firstly analyzes the 2-vehicles case for simplicity, and gives the determinative condition for obtaining the optimal solution. Then the authors extend the 2-vehicles to N -vehicles case, and obtain a special case for which the problem is proved to be efficiently solvable. An efficient algorithm is proposed which can get the optimal solution for the special case. Numerical exam- ples are stated at last.

关 键 词：N车 探险问题 特例 有效算法 

分 类 号：O157[理学—数学]