求BE算法解TSP问题.

hitb

小弟有个project得写出个解决
Bitonic euclidean traveling-salesman problem
的程序,小弟写了一点搞不定啊,请大家帮忙看看啊!中文的是小弟上课时候听的理解的 可以参考一下
思想：
TSP问题
对于8个点 F1-F8  在坐标轴上随机产生8个点（在第一象限，坐标为正即可）
将8个点保存到一个数组中假设  P（1）-P（8）


以  F1 和F8 为始末点   F2为参考点   判断从F3-F7  在F2的同侧还是异侧（判断方法假设F1-F8之间有一条联线，若点和F2在线的同一侧即为同侧，反之异侧）




然后求最短路径（即从F1和F2或者和F2同侧的点联线，求距离，比如F3 F4和F2同侧   则有这么几种路径F1-F2-F3-F4-F8,F1-F3-F2-F4-F8,F1-F4-F2-F3-F8,F1-F2-F4-F3-F8,F1-F3-F2-F4-F8等等求出其中最短的，再求出另外一边的路径F1,F5,F6,F8这几个点的最短路径）  然后比较求出最小路径






然后扩展到N个点   既可以求任意点的最短路径  此为BE算法



要求C++  VC++

The euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane. The general problem is NP-complete, and its solution is therefore believed to require more than polynomial time.


J. L. Bentley has suggested taht we simplify the problem by restricting our attention to bitnoic tours, that is, tours that start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right to left back to the starting point. In this case, a polynomial-time algorithm is possible.

Desrcibe an O(n^2)-time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same x-coordinate. (Hint: Scan left to right, maintaining optimal possibilities for the two parts of the tour.)

JUST

这个问题并不是传统意义上的TSP
它规定了顺序：从左到右，再从右到左
所以可以用DP（动态规划）或者网络流，复杂度为多项式级