一道超难的题目
编号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;  // 路径段的终点 
 

PathEdge(int nStart, int nArrived)
{
m_nStart = nStart;
m_nArrived = nArrived;
}
};


class Path
{
unsigned int m_path[cSize][cSize];  // 所有的路径信息

int m_nPathEdgeNum;        // 递归过程中选中的路径边数
// 一个完整回路由6条边组成,比如: 
// <0,1> <1,2> <2,3> <3,4> <4,5> <5,0>
vector<PathEdge> m_vPathEdge;           // 递归过程中选中的路径信息

unsigned int m_nShortPathLenth;     // 最短回路的长度
vector<PathEdge> m_vShortPath;          // 最短回路的节点信息

public:
Path(unsigned int (&arr)[cSize][cSize])
{
m_nPathEdgeNum = 0;
m_nShortPathLenth = 0xFFFFFFFF;
memcpy(m_path, arr, sizeof(arr));
}

void find(int nStart)
{
for (int nArrived=0; nArrived<cSize; ++nArrived)
{
if (nStart==nArrived)
{
continue;
}

if (m_nPathEdgeNum==cSize-1) //  递归的出口条件：找到一条回路,一个满足需求的回路由6条边组成.
{
// 添加第6条路径组成回路
m_vPathEdge.push_back(PathEdge(nStart, m_vPathEdge[0].m_nStart));

// 计算回路路径的长度
unsigned int nLenth = 0;
vector<PathEdge>::iterator it = m_vPathEdge.begin();
for (;it!=m_vPathEdge.end(); ++it)
{
nLenth+=m_path[it->m_nStart][it->m_nArrived];
}

if (nLenth<m_nShortPathLenth)
{
// 保存最短路径信息
m_vShortPath.clear();
m_nShortPathLenth = nLenth;
copy(m_vPathEdge.begin(), m_vPathEdge.end(), back_inserter(m_vShortPath));
}

m_vPathEdge.pop_back(); // 移除前面添加的第6条路径
return;
}

if (HasCycle(PathEdge(nStart, nArrived))) // 添加这条边，是否存在回路
{
continue;
}

Move(nStart, nArrived);
find(nArrived);
UndoMove();
}
}

void Output()
{
cout<<"最短的路径是:";
vector<PathEdge>::iterator it = m_vShortPath.begin();
for (; it!=m_vShortPath.end(); ++it)
{
cout<<"<"<<it->m_nStart<<","<<it->m_nArrived<<"> ";
}
cout<<endl;
cout<<"最短路径长度为:"<<m_nShortPathLenth<<endl;
}

protected:
bool HasCycle(PathEdge edge) 
 
{
vector<PathEdge>::iterator it = m_vPathEdge.begin();
for (; it!=m_vPathEdge.end(); ++it)
{
if (edge.m_nArrived == it->m_nStart 
[解决办法]

edge.m_nArrived == it->m_nArrived)
{
return true;
}
}

return false;
}

void Move(int nStart, int nArrived)
{
m_vPathEdge.push_back(PathEdge(nStart, nArrived));
++m_nPathEdgeNum;
}

void UndoMove()
{
m_vPathEdge.pop_back();
--m_nPathEdgeNum;
}
};

void main()
{
Path path(arr);
path.find(0);   // 始发位置为0;
path.Output();

system("pause");
}
  

程序输出如下：
最短路径是：<0,2> <2,3> <3, 4> <4, 5> <5, 1> <1, 0>
最短路径为：80。

楼主可以在这个基础上优化重构。

[解决办法]
可以用状态DP。。或者直接暴力递归搜索就行了。。
[解决办法]
运筹学基本问题,写成方程组，解出来就是了。推荐lingo数学软件来解
不多言，LZ找本运筹学书瞅瞅吧