回溯算法和贪心算法_回溯（类型和算法）

r囧r小猫 2023-03-05 15:50 24阅读 0赞

回溯算法和贪心算法

## 回溯 **(**Backtracking**)** ##

*  The name backtrack was first given by [D. H. Lehmer][] in 1950s.
    
    回溯的名字最早由[DH Lehmer][D. H. Lehmer]在1950年代给出。
 *  The general technique to solve any problem that deal with searching for a set of solution or which ask for an optimal solution satisfying some constraints is known as backtracking.
    
    解决与搜索一组解决方案有关的问题或要求满足某些约束的最佳解决方案的任何问题的通用技术称为回溯。
 *  Some of the problems that can be solved by backtracking are:
    
    回溯可以解决的一些问题是：
    
    1.  Sorting the array of integers in a \{1:n\}.
    2.  8 - Queens problem.
    3.  4 - Queens problem, or in generalized way n queen’s problem.
    4.  Sum of subsets problem.

## 回溯算法的类型 **(**Types of backtracking algorithms**)** ##

There are two **types of backtracking algorithms**:

**回溯算法**有两种**类型** ：

1.  Recursive backtracking algorithm
    
    递归回溯算法
2.  Non - recursive backtracking algorithm
    
    非递归回溯算法

### 1)递归回溯算法 **(**1) Recursive backtracking algorithm**)** ###

Naturally describing backtracking in this way is essential because it is a postorder traversal of a tree.

用这种方法自然地描述回溯是必不可少的，因为它是对树的事后遍历。

**Algorithm:**

**算法：**

1.	Algorithm Backtrack (k)
    2.	// this scheme describes the backtracking process using
    3.	// recursion. On entering, the first k-1 values.
    4.	// x [1], x [2]… x [k-1] of the solution vector.
    5.	// x [1:n] have been assigned. X [] and n are global.
    6.	{
    7.	For (each x [k] £ T (x[1],……,x[k-1])do
    8.	{
    9.	If ( Bk (x [1], x[2],……….,x [k] != 0) then
    10.	{
    11.	If (x[1], x[2], …… , x[k] is a path to  an answer node )
    12.	Then write (x[1:k]);
    13.	If(k<n) then backtrack (k+1);
    14.	}
    15.	}
    16.	}

The solution vector (x1, x2... xk) is treated as a global array x \[1: n\]. All the possible elements for kth position of the tuple that satisfy Bk are generated, one by one and then they are adjoined to the current vector (x1... xk-1). Each time xk is attached, a check is made to find whether a solution has been found. When the for loop of line 7 is completed, no more values for xk exist and the current copy of backtrack ends.

解向量(x1，x2 ... xk)被视为全局数组x \[1：n\] 。 满足Bk的元组的第 k 个位置的所有可能元素都被生成，然后将它们与当前向量(x1 ... xk-1)相连。 每次附加xk时 ，都会进行检查以查找是否已找到解决方案。 当第7行的for循环完成时， xk的值不再存在，并且当前回溯副本结束。

### 2)非递归回溯算法 **(**2) Non - Recursive backtracking algorithm**)** ###

An iterative or non-recursive version of recursive algorithm appears in non-recursive algorithm.

递归算法的迭代或非递归版本出现在非递归算法中。

**Algorithm:**

**算法：**

1.	Algorithm backtrack (k)
    2.	// this scheme describes the backtracking process.
    3.	// all solution are generated in x [1: n] and printed 
    4.	// as soon as they are determined.
    5.	{
    6.	K = 1;
    7.	While (k != 0) do
    8.	{
    9.	If ( there remains are untried x[1] £ T ( x [1], x[2], ….., x [k-1]) and Bk (x[1], ….., x[k]) is true) then
    10.	{
    11.	If ( x[1], …., x[k] is a path to an answer node)
    12.	Then write ( x[1 : k]);
    13.	K = k+1; // consider the next set
    14.	}
    15.	Else k = k-1 ; // backtrack to the previous set
    16.	}
    17.	}

T() here yields the set of all possible values that can be placed as the first component x1 of the solution vector. The component x1 will take values for which the bounding function B1 (x1) is true.

T()在这里产生所有可能值的集合，这些值可以作为解矢量的第一分量x1放置。 分量x1将采用边界函数B1(x1)为真的值。

Elements are generated here in a depth first manner.

这里以深度优先的方式生成元素。

> 翻译自: [https://www.includehelp.com/algorithms/backtracking-types-and-algorithms.aspx][https_www.includehelp.com_algorithms_backtracking-types-and-algorithms.aspx]

回溯算法和贪心算法

[D. H. Lehmer]: https://en.wikipedia.org/wiki/Derrick_Henry_Lehmer
[https_www.includehelp.com_algorithms_backtracking-types-and-algorithms.aspx]: https://www.includehelp.com/algorithms/backtracking-types-and-algorithms.aspx