著名的货郎担架问题大家都明白,现在要求解它。有两种办法方法一,暴力枚举法,举出所有的路径,这方法最简单,但是,需要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;
unsigned int iNodeCount;//结点的个数
unsigned int** lpDpArray;//动态规划时的数组
unsigned int** lpGraph;//存储图的数据
bool ** bHasCaculate;//存储一条路径是否访问过
unsigned int** lpPath;//存储最短的路径
bool FreeResource();//free memory
bool InitData();//init graph data
void Search();//搜索最短的路径
unsigned int GetMinPath(unsigned int iNode, unsigned int iNodeSet);
void ShowPath();//显示其中一个路径
int main(){
InitData();
Search();
cout<<lpDpArray[1][(1<<iNodeCount)-2]<<endl;
ShowPath();
FreeResource();
system("PAUSE");
}
bool FreeResource(){//free memory
for(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;
return true;
}
bool InitData(){//allocate memory and init data
cout<<"请输入结点个数:"<<endl;
cin>>iNodeCount;
lpDpArray = new unsigned int*[iNodeCount+ 1];
lpDpArray[0] = NULL;
bHasCaculate = new bool*[iNodeCount+ 1];
bHasCaculate[0]= NULL;
lpGraph = new unsigned int*[iNodeCount+ 1];
lpGraph[0] = NULL;
lpPath = new unsigned int*[iNodeCount+ 1];
lpPath[0] = NULL;
for(int iIndex= 1; iIndex<= iNodeCount; ++iIndex){
lpDpArray[iIndex] = new unsigned int[1<<iNodeCount];
bHasCaculate[iIndex] = new bool[1<<iNodeCount];
lpGraph[iIndex] = new unsigned int[iNodeCount+1];
lpPath[iIndex] = new unsigned 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;
}
}
return true;
}
//=========================================================================
//lpDpArray[iNode][iNodeSet]表示从Node(1)到Node(iNode)经过iNodeSet集合中的点的
//最小值
//=========================================================================
void Search(){
//显然当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);
}
unsigned int GetMinPath(unsigned int iNode, unsigned int iNodeSet){
if(bHasCaculate[iNode][iNodeSet]){
return lpDpArray[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 iNodeSet
unsigned int iPreValue = GetMinPath(iPreNode, iNodeSet&(~(1<<(iPreNode-1))));
if((iPreValue!= -1) && iPreValue+ lpGraph[iPreNode][iNode]< iMinValue){//update value
lpPath[iNode][iNodeSet] = iPreNode;
iMinValue = iPreValue+ lpGraph[iPreNode][iNode];
}
}
}
lpDpArray[iNode][iNodeSet] = iMinValue;
bHasCaculate[iNode][iNodeSet] = true;
return lpDpArray[iNode][iNodeSet];
}
void ShowPath(){
int * path= new int[iNodeCount+ 1];
int ivalue= (1<<iNodeCount)-1;
int iPreNode = 1;
int iNodeIndex = 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
以上的是边的权值(有向图)
分享到:
相关推荐
用佳点集实现遗传算法,解决货郎担问题,也就是Tsp问题,整个程序用Java实现,为便于学习,程序添加了详尽的注释,以及Javadoc帮助文档。整个程序只注重算法本身,没有添加任何包括图形界面在内的影响阅读的代码。...
货郎担问题的解决,很好用的哦,可以直接运行
TSP货郎担应用动态归划法求解 求从某个节点出发, 遍历余下n-1各节点后再回到出发点的最小成本周游路线.
用的是遗传算法.实现了货郎担的模拟,图形界面
旅行商问题,即TSP问题(Travelling Salesman Problem)是指对给定一组n个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次而且总的旅行距离最短。 此问题是典型NPC组合优化问题(NPC=...
TSP问题(又名:旅行商问题,货郎担问题)遗传算法通用matlab程序
里面是货郎担问题的各种接方法,包括动态规划,穷举搜索, 解决方案: 1.穷举法? 2.最短路标号法? 3.指派问题? 4.整数规划? 5.动态规划?
货郎担问题和野人过河问题,解压后有word文档,里面有详细说明
是一个模拟退火程序,解决的是货郎担问题,所用的语言是matlab
货郎担问题是运筹学中的一个著名命题,目前使用分值定界法及动态规划法比较多,本文介绍使用元素判别值进行求解及其算法设计和程序实现。它比现行方法简单有效。
利用动态规划思想,求货郎担问题,采用C++,显示各结点的路径并求出最短距离
旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。——旅行商问题百科
分支界限法解绝旅行商货郎担问题。 分支界限法解绝旅行商货郎担问题。 分支界限法解绝旅行商货郎担问题。
TSP问题是一个典型的组合优化问题、容易描述但是难以处理的NP完全问题,同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式,其可能的路径总数与城市数目n是成指数型增长的,所以一般很难精确的求出...
TSP问题(Traveling Salesman Problem)即旅行商问题,又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次...
采用蚁群算法计算货郎担通过 34 个城市一次回到原点的最短距离 可短时间解决这个 NP 难的 TSP 问题 内含运行文件生成的两张图 注释较详细
使用动态规划实现货郎担问题,计算出代价矩阵的最优解,即最短路径
TSP问题(又名:旅行商问题,货郎担问题)遗传算法通用matlab程序
离散数学的货郎担问题的课设 自己做的
matlab 实现货郎担问题的源代码,其使用的而算法是模拟退火算法。