算法第五章上机实验报告

一、回溯法分析

1.1 说明“最小重量机器设计问题”解空间

首先可以先将第一个工作分配给第一个人，那么第一个工作就已经完成了，第二和第三个人可以从第二和第三个工作中选择，分别出现各自对应的两种情况。其次，第一个人也可以选择第二和第三个工作，那么就是每个人都有可能对应每一个工作，这个问题的解空间就是一颗排列Tree，其每一个节点的策略是选择剩下的元素的一个。

1.2 说明 “最小重量机器设计问题"的解空间树

如图所示，问题的解空间树与之类似。（除去A-B）

首先从B-CDE即为第一个人选择的三个不同的工作，对应三种不同的情况。如果选择B-D，那么第二个人就还有剩下两种选择，H和I，当第二个人选择其中的一种，第三个人都只剩下一种情况即N或者O。

1.3在遍历解空间树的过程中，每个结点的状态值

在遍历解空间树的时候，每个每个节点的状态值就是当前层数（对应第几个人）的选择工作以及到这个人位置所累计的工作费用。

二、我对回溯法的理解

代码实现

#include <iostream>
using namespace std;

int work[100][100]={0};
int x[100]={0};
int minc=1000000,cc=0;
int n;

void backtrack(int t){
	if(t>n){
		if(cc < minc){
			minc = cc;
		}
		return;
	}
	
	for(int i=1;i<=n;i++){
		if(x[i]==0){
		cc += work[t][i];
		x[i]=1;
		if(cc<minc)
		backtrack(t+1);
		x[i]=0;
		cc -= work[t][i];
		}
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>work[i][j];
		}
	}
	backtrack(1);
	cout<<minc;
	return 0;
}

理解收获：回溯法是利用计算机进行每一种情况进行遍历，以此来得到我们所需要的最终结果，在算法递归遍历的时候，我们需要进行剪纸操作，否则递归层数太多会导致运算时间过长。另外，回溯法每到达一次叶节点，就代表一个结果的出现，并且与理想结果比较，若是，则保存，若不是，则return进行回溯到上一个子问题所得到的结果然后进行再次遍历。回溯法根据需要我们要保存状态并记得状态修改。