实验4 回溯法实现
一、实验目标：
1.熟悉回溯法应用场景及实现的基本方法步骤；
2.学会回溯法的实现方法和
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
方法：
二、实验内容
1. 旅行售货员问题：
当结点数为4，权重矩阵为
，求最优路径及开销。
2. 0-1背包问题：
对于n=5，C=10，vi={6,3,5,4,6}，wi={2,2，6,5,4}，计算xi及最优价值V。
分别利用动态规划、回溯法和分支限界法解决此问题，比较并分析这三种算法实现！
三、实验过程
1.源代码
旅行售货员问题（回溯法）：
#include
using namespace std;
class travel //回溯
{
friend int TSP(int **, int[], int, int);
private:
void Backtrack(int i);
int n, //顶点数
*x,
*bestx;
int **a,
cc,
bestc,
NoEdge;
};
void Swap(int a, int b)
{
int temp;
temp = a;
a = b;
b = temp;
return;
}
void travel::Backtrack(int i)
{
if (i == 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]) < bestc || bestc == NoEdge)
{
for (int j = 1; j <= n; j++) bestx[j] = x[j];
bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][1];
}
}
else
{
for (int j = i; j <= n; j++)
{
if (a[x[i - 1]][j] != NoEdge && a[x[n]][1] != NoEdge
&& (cc + a[x[i - 1]][x[j]] < bestc || bestc == NoEdge))
{
swap(x[i], x[j]);
cc += a[x[i - 1]][x[i]];
Backtrack(i + 1);
cc -= a[x[i - 1]][x[i]];
swap(x[i], x[j]);
}
}
}
}
int TSP(int** a,int v[], int n, int NoEdge)
{
travel Y;
Y.x = new int[n + 1];
for (int i = 1; i <= n; i++)
Y.x[i] = i;
Y.a = a;
Y.n = n;
Y.bestc = NoEdge;
Y.bestx = v;
Y.cc = 0;
Y.NoEdge = NoEdge;
Y.Backtrack(2);
delete[] Y.x;
return Y.bestc;
}
int main()
{
int const max = 10000;
cout << "请输入节点数:" << endl;
int n;
cin >> n;
int *v = new int[n];//保存路径
int NoEdge = 0;
int **p = new int*[max];
for (int i = 0; i < n+1; i++)//生成二维数组
p[i] = new int[n+1];
cout << "请依次输入各城市之间的路程：" << endl;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> p[i+1][j+1];
cout << "最短路径长度：" << TSP(p, v, 4, 1000) << endl;
cout << "路径为：";
for (int i = 1; i < 5; i++)
cout << v[i] <<' ';
cout << endl;
return 0;
}
运行截图：
旅行售货员问题（分支限界法）：
#include
using namespace std;
#define MAX_CITY_NUMBER 10 //城市最大数目
#define MAX_COST 1000 //两个城市之间费用的最大值
int City_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];//
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示城市间边权重的数组
int City_Size; //表示实际输入的城市数目
int Best_Cost; //最小费用
int Best_Cost_Path[MAX_CITY_NUMBER];
//结点
typedef struct Node {
int lcost; //优先级
int cc; //当前费用
int rcost; //剩余所有结点的最小出边费用的和
int s; //当前结点的深度，也就是它在解数组中的索引位置
int x[MAX_CITY_NUMBER]; //当前结点对应的路径
struct Node* pNext; //指向下一个结点
}Node;
//堆
typedef struct MiniHeap {
Node* pHead; //堆的头
}MiniHeap;
//初始化
void InitMiniHeap(MiniHeap* pMiniHeap) {
pMiniHeap->pHead = new Node;
pMiniHeap->pHead->pNext = NULL;
}
//入堆
void put(MiniHeap* pMiniHeap, Node node) {
Node* next;
Node* pre;
Node* pinnode = new Node; //将传进来的结点信息copy一份保存
//这样在函数外部对node的修改就不会影响到堆了
pinnode->cc = node.cc;
pinnode->lcost = node.lcost;
pinnode->pNext = node.pNext;
pinnode->rcost = node.rcost;
pinnode->s = node.s;
pinnode->pNext = NULL;
for (int k = 0; kx[k] = node.x[k];
}
pre = pMiniHeap->pHead;
next = pMiniHeap->pHead->pNext;
if (next == NULL) {
pMiniHeap->pHead->pNext = pinnode;
}
else {
while (next != NULL) {
if ((next->lcost) >(pinnode->lcost)) { //发现一个优先级大的，则置于其前面
pinnode->pNext = pre->pNext;
pre->pNext = pinnode;
break; //跳出
}
pre = next;
next = next->pNext;
}
pre->pNext = pinnode; //放在末尾
}
}
//出堆
Node* RemoveMiniHeap(MiniHeap* pMiniHeap) {
Node* pnode = NULL;
if (pMiniHeap->pHead->pNext != NULL) {
pnode = pMiniHeap->pHead->pNext;
pMiniHeap->pHead->pNext = pMiniHeap->pHead->pNext->pNext;
}
return pnode;
}
//分支限界法找最优解
void Traveler() {
int i, j;
int temp_x[MAX_CITY_NUMBER];
Node* pNode = NULL;
int miniSum; //所有结点最小出边的费用和
int miniOut[MAX_CITY_NUMBER];
//保存每个结点的最小出边的索引
MiniHeap* heap = new MiniHeap; //分配堆
InitMiniHeap(heap); //初始化堆
miniSum = 0;
for (i = 0; i0 && City_Graph[i][j]lcost = 0; //当前结点的优先权为0 也就是最优
浙公网安备 33021202002483