3.实例推导

4.时间复杂度

O(n)

三.贪心（最优装载问题）

问题描述

1.数学模型

2.算法框架

void Loading(int x[],  Type w[], Type c, int n)
{int *t = new int [n+1];   //动态数组t用来存放排序后的货物Sort(w, t, n);    //将集装箱按重量把数组w非减排序存放到数组t中for ( int i = 1; i <= n; i++ ) x[i] = 0;  //决策变量初始化for ( int i = 1; i <= n  && w[t[i]] <= c; i++ ) {x[t[i]] = 1;   //决策变量的对应位置置为1c -= w[t[i]]; //更新当前的荷载量} //在剩余集装箱中选择最轻的装船，直至超重
}

3.时间复杂度

O(nlogn) 主要来自把货物按重量排序的算法sort()

4.正确性分析

四.回溯和分支限界(旅行商问题）

1.解空间是子集树还是排列树在？

答：排列树，因为每个城市都要访问。

2.回溯法求解的过程

//旅行商问题回溯算法的实现
//形参t是回溯的深度，从2开始
void Backtrack(int t)
{//到达叶子结点的父结点if(t==n){if(a[x[n-1]][x[n]]!= NoEdge && a[x[n]][1]!= NoEdge && (cc + a[x[n-1]][x[n]]+a[x[n]][1]for(int i=1; i<=n; i++)bestx[i] = x[i];bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];}return;}
else {for(int i=t; i<=n; i++){if(a[x[t-1]][x[i]]!= NoEdge &&(cc + a[x[t-1]][x[i]]< bestc||bestc == NoEdge)){swap(x[t],x[i]);cc += a[x[t-1]][x[t]];Backtrack(t+1);cc -= a[x[t-1]][x[t]];swap(x[t],x[i]);}}}
}

3.分支限界法求解的过程

//旅行商问题分支限界法的实现
template 
Type Traveling::BBTSP(int *v, Type **G, int tn, Type tNoEdge)
{priority_queue > pq;MinHeapNode E, N;Type bestc, cc, rcost, MinSum, *MinOut, b;int i, j;a = G;n = tn;NoEdge = tNoEdge;MinSum = 0;                                             //最小出边费用和MinOut = new Type[n+1];                                 //计算MinOut[i]=顶点i的最小出边费用for(i = 1; i <= n; i++){MinOut[i] = NoEdge;for(j = 1; j <= n; j++)if(a[i][j] != NoEdge && (a[i][j] < MinOut[i] || MinOut[i] == NoEdge))MinOut[i] = a[i][j];if(MinOut[i] == NoEdge)                             //无回路return NoEdge;MinSum += MinOut[i];}//初始化E.s = 0;E.cc = 0;E.rcost = MinSum;E.x = new int[n];for(i = 0; i < n; i++)E.x[i] = i+1;bestc = NoEdge;//搜索排列空间树while(E.s < n-1)                                        //非叶结点{if(E.s == n-2)                                      //当前扩展结点是叶结点的父结点 再加2条边构成回路{                                                   //所构成回路是否优于当前最优解if(a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge &&(E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1] < bestc || bestc==NoEdge)){//费用更小的路bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1];E.cc = bestc;E.lcost = bestc;E.s++;pq.push(E);}elsedelete []E.x;                               //舍弃扩展结点}else                                                //产生当前扩展结点儿子结点{for(i = E.s+1; i < n; i++)if(a[E.x[E.s]][E.x[i]] != NoEdge){//可行儿子结点cc = E.cc + a[E.x[E.s]][E.x[i]];        //当前费用rcost = E.rcost - MinOut[E.x[E.s]];     //更新最小出边费用和b = cc + rcost;                         //下界if(b < bestc || bestc == NoEdge)        //子树可能含最优解 结点插入最小堆{N.s = E.s + 1;N.cc = cc;N.lcost = b;N.rcost = rcost;N.x = new int[n];for(j = 0; j < n; j++)N.x[j] = E.x[j];N.x[E.s+1] = E.x[i];                //获得新的路径N.x[i] = E.x[E.s+1];pq.push(N);                         //加入优先队列}}delete []E.x;                                   //完成结点扩展}if(pq.empty())                                      //堆已空break;E = pq.top();                                       //取下一扩展结点pq.pop();}if(bestc == NoEdge)                                     //无回路return NoEdge;for(i = 0; i < n; i++)                                  //将最优解复制到v[1:n]v[i+1] = E.x[i];while(pq.size())                                        //释放最小堆中所有结点{E = pq.top();pq.pop();delete []E.x;}return bestc;
}