一道超难的题目
编号1,2,3,4,5,6的六个城市的距离矩阵如下图所示,设推销员从城市1出发,经过每个城市一次且仅一次,最后回到1城,选择最短的路线其行程是多少公里?
[解决办法]
#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");
}
