旅行商问题简化版
摘要:欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解,但
欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解,但是有办法在多项式时间内求出一个较优解。
为了简化问题,而且保证能在多项式时间内求出最优解,J.L.Bentley提出了一种叫做bitonic tour的哈密尔顿环游。它的要求是任意两点(a,b)之间的相互到达的代价dist(a,b)=dist(b,a)且任意两点之间可以相互到达,并且环游的路线只能是从最西端单向到最东端,再单项返回最西端,并且是一个哈密尔顿回路。
现在笛卡尔平面上有n(n=1000)个点,每个点的坐标为(x,y)(-2^31x,y2^31,且为整数),任意两点之间相互到达的代价为这两点的欧几里德距离,现要你编程求出最短bitonic tour。
4、循环中会出现f[i,i]的状态,这种状态是无意义的,它不会影响最优解.
从西向东再从东向西可以看成从西边的起点有2个人走到东边,且2人所经过的点不重复。
可以定义状态为f[i,j],表示较快的人走到第i个点,较慢的人走到第j个点。
相关推荐: