迷题：走遍全国各省会的最短路线问题 ？？？

前几天，看了丁涛100天挑战骑车，要经过所有中国大陆省会城市，想设计个最短的路线。

2个城市之间的距离使用经度和纬度来计算。

1.刚开始使用了遍历+回调，所有路线都要考虑。14个城市以内还可以，几十的城市全部算下来所花的时间非常庞大，估计1个月都算不完。

后来加了一些简单的淘汰算法，不过也是九牛一毛。

2.第二个思路：逐渐添加城市，保证路线最短的方式是将剩余的城市一个一个地插进去，遍历要插入的位置。

比如：当前城市路线：上海 - 武汉 - 杭州 - 上海； 下一个城市：长沙。  将长沙循环添加到各个线中间，找出最佳插入点。 （最后是失败）

后来发现算出来的路线并非最短距离。

哪位同学有更好的思路？？

大陆城市的经纬度（排除了东北三省，因为直线跨海了）
Point 构造函数 (double 经度, double 纬度, String 名称)

Point sh = new Point(121.29, 31.14, "上海");
Point wh = new Point(114.21, 30.37, "武汉");
Point bj = new Point(116.28, 39.54, "北京");
Point tj = new Point(117.11, 39.09, "天津");
Point cq = new Point(106.32, 29.32, "重庆");
Point hhht = new Point(111.48, 40.49, "呼和浩特");
Point sjz = new Point(114.28, 38.02, "石家庄");
Point ty = new Point(112.34, 37.52, "太原");
Point jn = new Point(117, 36.38, "济南");
Point zz = new Point(113.42, 34.48, "郑州");
Point xa = new Point(108.54, 34.16, "西安");
Point lz = new Point(103.49, 36.03, "兰州");
Point yc = new Point(106.16, 38.20, "银川");
Point xn = new Point(101.45, 36.38, "西宁");
Point wlmq = new Point(87.36, 43.48, "乌鲁木齐");
Point hf = new Point(117.18, 31.51, "合肥");
Point nj = new Point(118.50, 32.02, "南京");
Point hz = new Point(120.09, 30.14, "杭州");
Point cs = new Point(113, 28.11, "长沙");
Point nc = new Point(115.52, 28.41, "南昌");
Point cd = new Point(104.05, 30.39, "成都");
Point gy = new Point(106.42, 26.35, "贵阳");
Point fz = new Point(119.18, 26.05, "福州");
Point gz = new Point(113.15, 23.08, "广州");
Point nn = new Point(108.20, 22.48, "南宁");
Point km = new Point(102.41, 25, "昆明");
Point ls = new Point(91.10, 29.40, "拉萨");

获取距离代码

public long getDistance(Point another) {
		double x, y, out;
		double PI = Math.PI;
		double R = 6.371229 * 1e6;
		x = (another.getJ() - this.getJ()) * PI * R * Math.cos(((another.getW() + this.getW()) / 2) * PI / 180) / 180;
		y = (another.getW() - this.getW()) * PI * R / 180;
		out = Math.sqrt(x * x + y * y);
		return (long)(out / 1000);
	}

我的方法直接把你机器烧了
1，全排列
2，计算每次排列结果的总距离
3，保留最小值
其实计算量一点也不大，

http://en.wikipedia.org/wiki/Shortest_path_problem

计算量不大，估计你是拍脑袋得出的结论。

可采用欧拉回路算法，google下吧

 

“欧拉回路算法”在这里不适用。

“欧拉回路算法”是将奇数点变偶数点；这里所有的点有且只有2个点，一出一入。

“欧拉回路算法”出入在那里是条件；这里是解。

你烧我的机器，我就拍你的脑袋。

这个不就是标准的图的多个节点的最短路径问题吗？你回头翻翻大学时的数据结构，好好看看迪杰斯特拉算法。

LS的， 迪杰斯特拉算法 也不行的。

27个点，你用迪杰斯特拉算法 做出来， 而且结果在三天之内可以运行出来， 我请你吃饭。

数据结构-图