一路超难的题目

一道超难的题目
编号1,2,3,4,5,6的六个城市的距离矩阵如下图所示,设推销员从城市1出发,经过每个城市一次且仅一次,最后回到1城,选择最短的路线其行程是多少公里?

------解决方案--------------------
TSP问题 NP-Hard的。。

数据规模很小的时候就暴力搜索吧

大数据规模 一般用进化算法求 可行解
------解决方案--------------------
看起来应该就是“一笔画”问题（欧拉回路），参考http://blog.163.com/zhoumhan_0351/blog/static/39954227200982051154725/

引用:

编号1,2,3,4,5,6的六个城市的距离矩阵如下图所示,设推销员从城市1出发,经过每个城市一次且仅一次,最后回到1城,选择最短的路线其行程是多少公里?

------解决方案--------------------

引用:

编号1,2,3,4,5,6的六个城市的距离矩阵如下图所示,设推销员从城市1出发,经过每个城市一次且仅一次,最后回到1城,选择最短的路线其行程是多少公里?

如果你仅这壹个6城市Salesman问题，全部搜索

如果想解决同类多城市问题，要找优化算法

Traveling Salesman Problem 

几十年前的老问题了
------解决方案--------------------

引用:

广度优先搜索？

又现眼...

这是很典型的TSP问题，NP Complete的，没有polynomial time的算法

规模大了的时候，只能用approximation algorithm来解。对于general case，approximation ratio

只能是2
------解决方案--------------------
  先给个最直观的递归解法。没有减枝条件的递归遍历。
  

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;


const int cSize = 6;


unsigned int arr[cSize][cSize] = 

{

	{ 0, 12, 23, 34, 45, 56},

	{10,  0,  9, 32, 27, 22},

	{20, 18,  0,  4, 11, 16},

	{30, 30,  5,  0, 10, 20},

	{40, 25, 10,  8,  0, 12},

	{50, 21, 15, 16, 18,  0},

};


struct PathEdge

{

	int m_nStart;    // 路径段的起点

	int m_nArrived;  // 路径段的终点