一、实验目的

1. 了解分治策略算法思想
2. 掌握快速排序、归并排序算法
3. 了解其他分治问题典型算法

二、实验内容

1. 编写一个简单的程序，实现归并排序。
   编写一段程序，实现快速排序。
2. 编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：
   （1）每个选手必须与其它n-1个选手各赛一次
   （2）每个选手一天只能赛一场
   （3）循环赛进行n-1天

三、算法思想分析

1. 归并排序
   基本思想为先将一个待排序序列分成两段大小大致相同的段，然后对这两个段同样递归地进行二分，直到不能再分为止，然后把足够小的相邻序列合并成有序序列（依据最优子结构且各个子问题相互独立），再上溯，合并，直到整个序列有序化。
   合并时需要对两个已有序的序列合并成一个有序队列，因此在合并操作时就需要进行有序化操作，在这里因为本身子序列已经有序，所以采用设置两个子序列的首尾指针，首指针移动来比较两个子序列中的较小元素并存到新序列，直到一方首尾指针重合，再将另一个序列的剩余部分直接接到新序列即可。
2. 快速排序
   基本思想为通过一次排序将需要排序的序列分割成独立的两部分，首先设置一个基准数，进行一次排序后，其中一部分的所有数据比基准数小，另一部分的所有数据都比基准数大，这样基准数当前位置就是其在有序序列的位置，然后对新分出的两个序列递归地进行排序处理（由于两方互不影响，其满足最优子结构，有独立性），直到序列大小最小，这样通过一次分治的排序可以将所有元素放到有序序列的正确位置上，从而将整个序列有序化，整体是一个“挖坑填数+分治”的过程。
3. 循环赛日程表
   基本思想为将整个n * n表格分成n/2 * n/2的四部分，对左上角与右上角的部分递归地进行分割（独立性），直到大小为2 * 2的最小可分配部分，针对最小部分，将每个部分的左上角部分赋给右下角（在最优子结构下2 * 2的部分左上角和右上角都是一个元素），右上角部分赋给左下角，再上溯到4 * 4，重复合并操作，一直到大小为n，这样获得的表就是一个已分配好的表，其中第一列是比赛的每一方，后七列的每一列分别代表当天的对阵。

四、实验过程分析
在做本次实验的过程中，我起初对递归的理解程度不是很深，归并和快排的思想相对还好理解，实现起来也有规律可循，但当做到循环赛日程表时，发现分割从归并与快排的一维升到了二维，就在递归的设计上犯了难，通过一段时间的研究与调试，最后发现当规模没有降到最小时其实都是在进行分割，只有当规模够小之后才能简单进行合并操作，再将部分完成的矩阵升规模再合并直到完成整个矩阵。
通过分治的实验，我对分治的最优子结构性质，独立性，规模缩小策略等相关概念与思想的理解相对更加的深入，这对我在整个课程的学习中都是一个十分显著的成果，而且通过代码的实现，我对分治的基本策略与递归的结合的使用更加的娴熟了，这提高了我的编程能力。

五、算法源代码及用户屏幕
1.归并排序
①代码

#include<iostream>
using namespace std;

void merge(int array[], int left, int middle, int right) {
	int length = right - left + 1;
	//申请空间用于存储合并之后的序列
	int temp[right - left + 1];
	//设置标号
	int begin1 = left;
	int end1 = middle;
	int begin2 = middle + 1;
	int end2 = right;
	//设置新数组的计数器
	int i = 0;
	//比较，进入序列
	while ((begin1 <= end1) && (begin2 <= end2)) {
		if (array[begin1] < array[begin2]) {
			temp[i] = array[begin1];
			begin1++; i++;
		}
		else
		{
			temp[i] = array[begin2];
			begin2++; i++;
		}
	}
	//将剩余部分直接接到最后的序列上
	while (begin1 <= end1) {
		temp[i] = array[begin1];
		begin1++; i++;
	}
	while (begin2 <= end2) {
		temp[i] = array[begin2];
		begin2++; i++;
	}
	for (int j = 0; j < length; j++)
	{
		array[left + j] = temp[j];
	}

}
//递归调用完成操作
void mergeSort(int data[], int left, int right) {
	if (left < right) {
		int middle = (left + right) / 2;
		//先分后合并
		mergeSort(data, left, middle);
		mergeSort(data, middle + 1, right);
		merge(data, left, middle, right);
	}
}

int main() {
	int n;
	cout << "Please input the number of numberSet: ";
	cin >> n;
	int array[n];
	cout << "Please input the number: ";
	for (int i = 0; i < n; i++) {
		cin >> array[i];
	}
	mergeSort(array, 0, n - 1);
	cout << "the result is: ";
	for (int i = 0; i < n; i++) {
		cout << array[i] << " ";
	}
	system("pause");
	return 0;
}

②用户界面
首先输入序列中数的个数，然后输入无序序列，回车之后返回有序序列

2.快速排序
①代码

#include <iostream>
using namespace std;
int splitArray(int data[], int left, int right) {
	//获取最左边的元素
	int temp = data[left];
	//从左向右查找小于标志位的元素，换到左边，移指针
	while (left < right) {
		while ((left < right) && (data[right] >= temp)) {
			right--;
		}
		data[left] = data[right];
	//从右向左查找大于标志位的元素，换到右边，移指针
		while ((left < right) && (data[left] <= temp)) {
			left++;
		}
		data[right] = data[left];
	}
	//将标志位填到空位
	data[left] = temp;
	return left;
}
//先将标志位填好，然后左右递归调用
void quickSort(int data[], int left, int right) {
	if (left < right) {
		int middle = splitArray(data, left, right);
		quickSort(data, left, middle - 1);
		quickSort(data, middle + 1, right);
	}
}
int main() {
	int n;
	cout << "Please input the number of numberSet: ";
	cin >> n;
	int array[n];
	cout << "Please input the number: ";
	for (int i = 0; i < n; i++) {
		cin >> array[i];
	}
	quickSort(array, 0, n - 1);
	cout << "the result is: ";
	for (int i = 0; i < n; i++) {
		cout << array[i] << " ";
	}
	system("pause");
	return 0;

}

②用户界面
首先输入序列中数的个数，然后输入无序序列，回车之后返回有序序列

3.循环赛日程表
①代码

#include<iostream>
using namespace std;
#define NUM 100

void queue(int data[NUM][NUM], int left, int right, int num) {
	int middle = (left + right) / 2;
	//将左上角送到右下角
	for (int i = 0; i < num; i++) {
		for (int j = left; j <= middle; j++) {
			data[i + num][j + num] = data[i][j];
		}
	}
	//将左下角送到右上角
	for (int i = 0; i < num; i++) {
		for (int j = middle + 1; j <= right; j++) {
			data[i + num][j - num] = data[i][j];
		}
	}
}

void queueRace(int data[NUM][NUM], int left, int right, int num) {
	int middle = (left + right) / 2;
	//当没有到临界条件（块足够小）时，递归调用
	if (num > 1) {
		queueRace(data, left, middle, num / 2);
		queueRace(data, middle + 1, right, num / 2);
	}
	//合并块
	queue(data, left, right, num);
}

int main() {
	int n;
	cout << "Please input the number of queues: ";
	cin >> n;
	cout << "The result of race is: " << endl;
	int data[NUM][NUM] = { 0 };
	for (int i = 0; i < n; i++) {
		data[0][i] = i + 1;
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			data[i][j] = 0;
		}
	}
	queueRace(data, 0, n - 1, n / 2);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (j == n - 1)cout << data[i][j] << endl;
			else cout << data[i][j] << " ";
		}
	}
	system("pause");
	return 0;
}

②用户界面
首先输入需要比赛的队伍数（2的倍数），回车之后显示比赛日程表

计算机算法设计与分析主要通过介绍常见的算法设计策略及复杂性分析方法，培养学生分析问题和解决问题的能力，为开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。该课程理论与实践并重，内容具有综合性、广泛性和系统性，是一门集应用性、创造性及实践性为一体的综合性极强的课程，通过对本课程的学习，对如下算法有了深刻的理解。

一、递归与分治策略：大整数的乘法、矩阵乘法、棋盘覆盖、合并排序、快速排序

程序直接或间接调用自身的编程技巧称为递归算法。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归优秀在代码简洁，但首先需要有清晰的思路理清递归的循环条件及出口。递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

有时递归需要多次重复某一计算，可以用数组记录下需要的数据进行调用大大降低空间复杂度。在用分治法设计算法时，最好使子问题的规模大致相同。如分成大小相等的k个子问题，许多问题可以取k＝2。

分治法所能解决的问题一般具有以下几个特征：

（1）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质；

（2）利用该问题分解出的子问题的解可以合并为该问题的解；

（3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

二、动态规划：最长公共子序列、凸多边形最优三角剖分、图像压缩、0-1背包问题、最优二叉搜索树

动态规划是解决多阶段决策问题的一种方法。据空间顺序或时间顺序对问题的求解划分阶段。根据题意要求，对每个阶段所做出的某种选择性操作。用数学公式描述与阶段相关的状态间的演变规律。

如果一类问题的求解过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策，并影响到下一个阶段的决策。在做每一步决策时，列出各种可能的局部解.依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。以每一步都是最优的来保证全局是最优的。

动态规划与分治法所能解决问题的特征类似，主要区别在于动态规划所分解出的各个子问题不是相互独立的，即子问题之间包含公共的子子问题。

三、贪心算法：活动安排问题、装载问题、哈夫曼编码、单源最短路径、最小生成树

在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。

利用贪心法求解的问题应具备如下2个特征：

1、贪心选择性质，指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到；

2、最优子结构性质。

四、回溯法：装载问题、n后问题、0-1背包问题、最大团问题、旅行售货员问题

以深度优先的方式系统地搜索问题的解的方法称为回溯法，分为递归回溯和迭代回溯两种。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间树称为子集树。当所给的问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。回溯算法可以很方便地遍历一个集合的所有子集或者所有排列。

在生成解空间树时，定义以下几个相关概念：活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。扩展结点：当前正在生成其儿子结点的活结点叫扩展结点（正扩展的结点）。死结点：不再进一步扩展或者其儿子结点已全部生成的结点就是死结点。

在确定了解空间的组织结构后，回溯从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点成为一个活结点，同时成为当前的扩展结点。在当前的扩展结点，搜索向深度方向进入一个新的结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。若在当前扩展结点处不能再向深度方向移动，则当前的扩展结点成为死结点，即该活结点成为死结点。此时回溯到最近的一个活结点处，并使得这个活结点成为当前的扩展结点。回溯法以这样的方式递归搜索整个解空间（树），直至满足中止条件。

在回溯法搜索解空间树时，通常采用两种策略（剪枝函数）避免无效搜索以提高回溯法的搜索效率：用约束函数在扩展结点处减去不满足约束条件的子树；用限界函数减去不能得到最优解的子树。

回溯法是一种组织搜索的一般技术，有“通用的解题法”之称，用它可以系统的搜索一个问题的所有解或任一解。有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。应用回溯法求解时，需要明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

五、分支界限法：单元最短路径问题、装载问题、0-1背包问题、最大团问题、旅行售货员问题

分支限界法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为限界）。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，凡是界限超出已知可行解值的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

六、结语

在动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题后，才能做出选择（子问题->选择->原问题）。在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择，然后再去解出这个选择后产生的相应的子问题（原问题->选择->子问题）。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

大多数问题动态规划都可以解决，但是太慢。因此有些问题贪心确实比动态快的多。不过相对的贪心解决问题并不如动态规划精细，得出来的不一定是最优解，只能说是相对最优，根据情况选择不同的算法解决问题才是王道。

在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。

通过对课程的理论学习与实践，我掌握了许多经典的算法思想，思维创新能力和实践能力得到了有效的提高，并且一题多解的情况让我对不同的算法有了更加深刻的认识。这些知识在我今后的学习中将会得到更深层次的理解与应用。

数据结构和算法是非常难啃的东西 ，以下我会用VS2019可以编译 并且以代码和典型例子为基础 来讲解 几个典型的计算机学生应该掌握并且使用非常熟练的算法以下内容 需要大家有基本的数据结构知识， 如果学过 巩固数据结构基本的一些知识

型特例)

1.贪心法【以狄杰斯特拉算法为特例】

贪心算法思想：

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心算法的基本要素：

1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

贪心算法的基本思路：

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

1. 不能保证求得的最后解是最佳的；

2. 不能用来求最大或最小解问题；

3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

从问题的某一初始解出发；

while 能朝给定总目标前进一步 do

求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解；

```cpp
#include <iostream>
using namespace std;
#define max 10000
void yuan(int n, int** a, int m)//实现贪心法的函数
{
	int* b = new int[n + 1], * s = new int[n + 1];//增加一块空间，b用来存放目的节点到其它节点的最小距离，S用来标记
	int i, j;
	for (i = 1; i <= n; i++)
	{
		b[i] = a[m][i]; s[i] = 0;//可以做假设  从第一个开始m=1 放入b数组中，此时是没有更新的距离，不是最短距离都没有标记
	}
	s[m] = 1;//此时标记本身，自身到自身肯定是最短距离
	for (int ii = 1; ii < n; ii++)//最外层循环，以节点为单位 操作每个节点
	{
		int min = max, w = 1;//所有大于Max的值都算作 无穷大 w=1
		for (int k = 1; k <= n; k++)
			if (min > b[k] && (!s[k]))
			{
				w = k; min = b[k];
				
			}//求出节点1相邻的节点中最短的距离
		s[w] = 1;//标记这个节点 记住已记住， 以后不再操作
		
		for (i = 1; i <= n; i++)
			if (!s[i])//对没有标记的节点进行操作，更新最小值。如此循环
			{
				if (b[i] > b[w] + a[w][i])
					b[i] = b[w] + a[w][i];
			}
	}
	for (j = 1; j <= n; j++)
		if (j != m)
			cout << m << "-->" << j << " : " << b[j] << endl;
}
int main()
{
	int n, m, ** a, i, j;
	cout <<"请输入顶点数和起始的顶点号：随后输入顶点 到另几个顶点的长度（包括自身）";
	while (cin >> n >> m)
	{
		a = new int* [n + 1];
		for (i = 0; i <= n; i++)
			a[i] = new int[n + 1];
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				cin >> a[i][j];
		yuan(n, a, m);
	}
	return 0;

}

``
不懂的可以自己画图 然后用邻接矩阵法画出一个图，试一试；

分治法（二分查找）

将整个问题分解成若干小问题后再分而治之。如果分解得到的子问题相对来说还是太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。
分治算法可以由递归过程来表示，因为分治法就是一种找大规模问题与小规模问题关系的方法，是递归设计的一种具体策略。

步骤
1.分解
将原问题分解为若干规模较小，相互独立，与原问题相同的子问题。
2.解决
若干子问题较小而容易被解决则直接解决，否则再继续分解为更小的子问题，直到容易解决。
3.合并
将已求解的各个子问题的解，逐步合并为原问题的解。

有的问题分解后不需要合并子问题的解，此时就不需要再做第3步了。多数问题需要子问题的解，按照题意使用恰当的方法合并成为整个问题的解。需要具体问题具体分析。

#include<stdio.h>
float a[5]={3,6,9,2,5};
int main(){
	void maxmin(int i,int j,float &fmax,float &fmin,int &count);//fmax的地址,fmin的地址 
	float fmax=0,fmin=0;
	int count=0;
	maxmin(0,4,fmax,fmin,count);
	//传递地址是为了能够把值带出来 
	printf("fmax=%f\nfmin=%f\ncount=%d\n",fmax,fmin,count); 
	return 0;
}
void maxmin(int i,int j,float &fmax,float &fmin,int &count){
	int mid;
	int k;
	float lmax,lmin,rmax,rmin;
	count++;
	//递归结束条件(子问题的解)
	//当分到只剩一个数
	if(i==j){
		fmax=a[i];fmin=a[i];
	} 
	else if(i==j-1){//(i,j为下标，在分解过程中,i总在左,j总在右 )假如只剩两个数 
		if(a[i]>a[j]){
			fmax=a[i];
			fmin=a[j];
		} 
		else if(a[j]>a[i]){
			fmax=a[j];
			fmin=a[i];
		}
	}
	else{//其他情况（还剩很多数），则继续递归分解 
		mid=(i+j)/2;//继续分半
		maxmin(i,mid,lmax,lmin);
		maxmin(mid+1,j,rmax,rmin);
		if(lmax>rmax) fmax=lmax;
		else fmax=rmax;
		if(lmin<rmin) fmin=rmin;
		else fmin=rmin;
	}
}

动态规划法[背包问题]

以下是我综合了动态规划的特点给出的动态规划的定义：动态规划是一种多阶段决策最优解模型，一般用来求最值问题，多数情况下它可以采用自下而上的递推方式来得出每个子问题的最优解（即最优子结构），进而自然而然地得出依赖子问题的原问题的最优解。

划重点：

多阶段决策，意味着问题可以分解成子问题，子子问题，。。。，也就是说问题可以拆分成多个子问题进行求解
最优子结构，在自下而上的递推过程中，我们求得的每个子问题一定是全局最优解，既然它分解的子问题是全局最优解，那么依赖于它们解的原问题自然也是全局最优解。
自下而上，怎样才能自下而上的求出每个子问题的最优解呢，可以肯定子问题之间是有一定联系的，即迭代递推公式，也叫「状态转移方程」，要定义好这个状态转移方程， 我们就需要定义好每个子问题的状态（DP 状态），那为啥要自下而上地求解呢，因为如果采用像递归这样自顶向下的求解方式，子问题之间可能存在大量的重叠，大量地重叠子问题意味着大量地重复计算，这样时间复杂度很可能呈指数级上升（在下文中我们会看到多个这样重复的计算导致的指数级的时间复杂度），所以自下而上的求解方式可以消除重叠子问题。
简单总结一下，最优子结构，状态转移方程，重叠子问题就是动态规划的三要素，这其中定义子问题的状态与写出状态转移方程是解决动态规划最为关键的步骤，状态转移方程如果定义好了，解决动态规划就基本不是问题了。
既然我们知道动态规划的基本概念及特征，那么怎么判断题目是否可以用动态规划求解呢，其实也很简单，当问题的定义是求最值问题，且问题可以采用递归的方式，并且递归的过程中有大量重复子问题的时候，基本可以断定问题可以用动态规划求解，于是我们得出了求解动态规划基本思路如下（解题四步曲）

#include<iostream>
using namespace std;
#include <algorithm>
 
int main()
{
	int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
	int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
	int bagV = 8;					        //背包大小
	int dp[5][9] = { { 0 } };			        //动态规划表
 
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= bagV; j++) {
			if (j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
 
	//动态规划表的输出
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}
 
	return 0;
}
 

搜索法【旅行商问题】

回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

基本思想类同于：

图的深度优先搜索
二叉树的后序遍历
【

     分支限界法：广度优先搜索

     思想类同于：图的广度优先遍历

                            二叉树的层序遍历

  】

2. 详细描述
   详细的描述则为：

    回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。
   
    回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。
   
    问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。
   

3. 回溯法应用
   当问题是要求满足某种性质（约束条件）的所有解或最优解时，往往使用回溯法。

   它有“通用解题法”之美誉。
   

#include<iostream>
#include<algorithm>
#define MAX 100
using  namespace std;
int n;                               //城市个数
int a[MAX][MAX];                   //城市间距离
int x[MAX];                       //记录路径
int bestx[MAX]  = {0};           //记录最优路径
int bestp = 63355;              //最短路径长
int cp = 0;                    //当前路径长
void backpack(int t){
     if(t>n){
        if((a[x[n]][1])&&(a[x[n]][1]+cp<bestp)){
              bestp = a[x[n]][1]+cp;
              for(int i = 1;i<=n;i++){
                 bestx[i] = x[i];
              }
        }
     }else{
         for(int i = t;i<=n;i++){
             /*约束为当前节点到下一节点的长度不为0,限界为走过的长度+当前要走的长度之和小于最优长度*/
            if((a[x[t-1]][x[i]])&&(cp+a[x[t-1]][x[i]]<bestp)){
                swap(x[t],x[i]);   
                cp+=a[x[t-1]][x[t]];
                backpack(t+1);
                cp-=a[x[t-1]][x[t]];
                swap(x[t],x[i]);
            }
         }
    }
}
int main(){
    cout<<"输入城市个数:"<<endl;
    cin>>n;      //顶点数
    for(int i = 1;i<=n;i++){
         x[i] = i;
    }
    cout<<"输入城市之间的距离(0表示城市间不通):"<<endl;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    backpack(2);
    cout<<"最少旅行费用为: "<<bestp<<endl;
    cout<<"旅行路径为:"<<endl;
    for(int i = 1;i<=n;i++){
       cout<<bestx[i]<<" ";
    }
    cout<<bestx[1];
    return 0;
}