广义货郎担架问题(TSP，广义哈密顿环问题)---允许有向图
著名的货郎担架问题大家都明白，现在要求解它。有两种办法
方法一，暴力枚举法，举出所有的路径，这方法最简单，但是，需要N!的复杂度，当n比较大时，完全没有可计算性，当然，生成n!种排列比较简单，不需要什么高端的技巧。在此不解释这种解法
方法二，动态规划，设T(Vi,V)表示从V1经过V中所有结点到Vi的最短路径值，于是我们有以下的转移方程
T(Vi,V)=min{D(k,i)+T(Vk,V\{Vk}}其中Vk是V中元素，其中D(k,i)表示第k个结点到第i个的距离(允许取无穷大)。我们要求解的问题是T(V1,V\{V1}).----即我们从V1出了，遍历V中除V1之外的结点，然后回到V1.根据这个原则，我们用二进制位表示每一个元素的取与不取。则知道代码如下：
//author:sy1206321#include <iostream>using std::endl;using std::cin;using std::cout;unsignedintiNodeCount;//结点的个数unsignedint**lpDpArray;//动态规划时的数组unsignedint**lpGraph;//存储图的数据bool**bHasCaculate;//存储一条路径是否访问过unsignedint**lpPath;//存储最短的路径boolFreeResource();//free memoryboolInitData();//init graph datavoidSearch();//搜索最短的路径unsignedintGetMinPath(unsignedint iNode, unsigned intiNodeSet);voidShowPath();//显示其中一个路径int main(){InitData();Search();cout<<lpDpArray[1][(1<<iNodeCount)-2]<<endl;ShowPath();FreeResource();system("PAUSE");}boolFreeResource(){//free memoryfor(int iIndex= 0; iIndex<= iNodeCount; ++iIndex){delete[]lpDpArray[iIndex];delete[]bHasCaculate[iIndex];delete[]lpGraph[iIndex];delete[]lpPath[iIndex];}delete[]lpDpArray;delete[]bHasCaculate;delete[]lpGraph;delete[]lpPath;returntrue;}boolInitData(){//allocate memory and init datacout<<"请输入结点个数:"<<endl;cin>>iNodeCount;lpDpArray=new unsigned int*[iNodeCount+ 1];lpDpArray[0]=NULL;bHasCaculate=newbool*[iNodeCount+ 1];bHasCaculate[0]=NULL;lpGraph=newunsigned int*[iNodeCount+ 1];lpGraph[0]=NULL;lpPath=newunsigned int*[iNodeCount+ 1];lpPath[0]=NULL;for(int iIndex= 1; iIndex<= iNodeCount; ++iIndex){lpDpArray[iIndex]=newunsigned int[1<<iNodeCount];bHasCaculate[iIndex]=newbool[1<<iNodeCount];lpGraph[iIndex]=newunsigned int[iNodeCount+1];lpPath[iIndex]=newunsigned int[1<<iNodeCount];}cout<<"请输入图的数据，如果不存在就输入0"<<endl;//读入图的数据，不存在则用无穷表示(static_cast<int>(-1))for(unsigned int iRow= 1; iRow<= iNodeCount; ++iRow){for(unsigned int iCol= 1; iCol<= iNodeCount; ++iCol){cin>>lpGraph[iRow][iCol];if(!lpGraph[iRow][iCol]){lpGraph[iRow][iCol]=static_cast<unsigned int>(-1);}}}//把bHasCaculate, lpDpArray, lpPath数组全部清零for(unsigned int iRow=1; iRow<= iNodeCount; ++iRow){for(unsigned int iCol= 1; iCol< (1<<iNodeCount); ++iCol){bHasCaculate[iRow][iCol]=false;lpDpArray[iRow][iCol]=static_cast<unsigned int>(-1);lpPath[iRow][iCol]=0;}}returntrue;}//=========================================================================//lpDpArray[iNode][iNodeSet]表示从Node(1)到Node(iNode)经过iNodeSet集合中的点的//最小值//=========================================================================voidSearch(){//显然当iNodeSet为0是，表示空集for(int iNode= 1; iNode<= iNodeCount; ++iNode){lpDpArray[iNode][0]=lpGraph[1][iNode];lpPath [iNode][0]=1;bHasCaculate[iNode][0]=true;}lpDpArray[1][(1<<iNodeCount)-2]=GetMinPath(1, (1<<iNodeCount)-2);}unsignedintGetMinPath(unsignedint iNode, unsigned intiNodeSet){if(bHasCaculate[iNode][iNodeSet]){returnlpDpArray[iNode][iNodeSet];}unsigned int iMinValue=static_cast<int>(-1);for(int iPreNode= 1; iPreNode<= iNodeCount; ++iPreNode){if(((1<<(iPreNode-1)) & iNodeSet) && (lpGraph[iPreNode][iNode]!= -1)){//iPreNode is a elem of iNodeSetunsigned int iPreValue=GetMinPath(iPreNode, iNodeSet&(~(1<<(iPreNode-1))));if((iPreValue!= -1) && iPreValue+ lpGraph[iPreNode][iNode]< iMinValue){//update valuelpPath[iNode][iNodeSet]=iPreNode;iMinValue=iPreValue+ lpGraph[iPreNode][iNode];}}}lpDpArray[iNode][iNodeSet]=iMinValue;bHasCaculate[iNode][iNodeSet]=true;returnlpDpArray[iNode][iNodeSet];}voidShowPath(){int*path=newint[iNodeCount+ 1];intivalue=(1<<iNodeCount)-1;intiPreNode=1;intiNodeIndex=0;while(ivalue){ivalue-=(1<<(iPreNode-1));path[iNodeCount-iNodeIndex]=iPreNode;++iNodeIndex;iPreNode=lpPath[iPreNode][ivalue];}path[0]=1;for(iNodeIndex= 0; iNodeIndex<= iNodeCount; ++iNodeIndex){cout<<path[iNodeIndex]<<(iNodeIndex== iNodeCount ? "\n":"->");}delete[]path;}在其中我们并没有完全采用动态规划，而是采用它的一个变种---备忘录，我们把已经求得的还会重新利用的小的结果记录起来，下次再求解这个小问题的时候直接查表就可以了，而不是像动态规划那样，在求解一个大问题的时候要求所有的小问题都已经被解决。
易求算法时间复杂度是O(n*2^n)空间也是，显然在时间上比n!要快许多，而对于n!我们由斯特林公式知n!=(n/e)^n*(2*pi*n)^0.5，显然比2^n*n要大许多的
其中我给的一组输入值是:
6(6个顶点）
0 10 20 30 40 50
12 0 18 30 25 21
23 19 0 5 10 15
34 32 4 0 8 16
45 27 11 10 0 18
56 22 16 20 12 0
以上的是边的权值（有向图）