贪心、分支限界、动态规划解决最短路径问题.docx

贪心、分支限界、动态规划解决最短路径问题
算法综合实验报告
学 号： 100407
姓 名：
黄琼莹
一、实验内容：
分别用动态规划、贪心及分支限界法实现对TSP问题（无向图）的求解，并
至少用两个测试用例对所完成的代码进行正
pinnode->cc = ;
pinnode->lcost = ;
pinnode->pNe_t = ;
pinnode->rcost = ;
pinnode->s = ;
pinnode->pNe_t = NULL;
for(int k=0;k_[k] = [k];
}
pre = pMiniHeap->pHead;
ne_t = pMiniHeap->pHead->pNe_t;
if(ne_t == NULL){
pMiniHeap->pHead->pNe_t = pinnode;
}
else{
while(ne_t != NULL){
if((ne_t->lcost) > (pinnode->lcost)){ // 发现一个优先级大的，则置于
其前面
pinnode->pNe_t = pre->pNe_t;
pre->pNe_t = pinnode;
break; // 跳出
}
pre = ne_t;
ne_t = ne_t->pNe_t;
}
pre->pNe_t = pinnode; // 放在末尾
}
}
// 出堆
Node_
RemoveMiniHeap(MiniHeap_
pMiniHeap){
Node_
pnode = NULL;
if(pMiniHeap->pHead->pNe_t != NULL){
pnode = pMiniHeap->pHead->pNe_t;
pMiniHeap->pHead->pNe_t = pMiniHeap->pHead->pNe_t->pNe_t;
}
return pnode;
}
// 分支限界法找最优解
void Traveler(){
int i,j;
int temp__[MA__CITY_NUMBER];
Node_
pNode = NULL;
int miniSum; // 所有结点最小出边的费用和
int miniOut[MA__CITY_NUMBER];
// 保存每个结点的最小出边的索引
MiniHeap_
heap = new MiniHeap; // 分配堆
InitMiniHeap(heap); // 初始化堆
miniSum = 0;
for (i=0;i0 City_Graph[i][j]lcost = 0;// 当前结点的优先权为 0
也就是最优
pNode->cc = 0;// 当前费用为0(还没有开始旅行)
pNode->rcost = miniSum; // 剩余所有结点的最小出边费用和就是初始
化的 miniSum
pNode->s = 0;// 层次为 0
pNode->pNe_t = NULL;
for(int k=0;k_[k] = Best_Cost_Path[k]; // 第一个结点所保存