Bitonic旅行路线问题
   
　　问题描述

　　欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的游历路线问题。图1(a)给出了七个点问题的解。Bitonic旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。图1（b）给出了七个点问题的解。

　　　　　　　
　　　　　　　　　　　　　　　　　　　　图1

　　请设计一种多项式时间的算法，解决Bitonic旅行路线问题。

　　输入格式（input.txt）
　　
　　输入文件的第一行为平面中给定的点的个数n（n≤100），接下来n行分别为这n个顶点的坐标xi和yi，每行描述一个顶点，横纵坐标之间有一个空格。

　　输出格式(Output.txt)
　
　　输出文件仅有一个实数，为所求的最短路径长度，结果保留到小数后两位。

    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有