回溯法学习笔记

1、回溯法被称为具有剪枝函数的深度优先生成法。

2、剪枝函数

可行性约束函数
上界函数

3、排列树、子集树、解空间树

4、

下列哪个结点属于回溯法的结点类型？（）

A.扩展结点
B.活结点
c.收缩结点
D.死结点
正确答案：A、B、D
解析：
在回溯算法中，结点类型的理解是关键。这个问题涉及到三种类型的结点：扩展结点、活结点和死结点。
让我们一一解释这些术语，以便更好地理解。

扩展结点（A）
扩展结点是指当前正在考察的结点。在回溯算法中，当我们到达一个新结点，并且正在探索从这个结点出
发的所有可能的分支时，这个结点被称为扩展结点。简单来说，扩展结点就是当前的焦点或工作结点。

活结点（B）
活结点是指那些已经被部分探索过，但其子结点还没有被完全探索的结点。这意味着从这个结点出发可能
还存在到达解的路径。在回溯过程中，如果一个结点还未被完全排除（即仍然有可能通向解），它就是一个活结点。

收缩结点
这个选项在回溯算法的常用术语中并不常见，可能是个错误的选项或者是对其他术语的不标准表述。

死结点（D）
死结点是指那些已经被确定不能产生问题解的结点。在回溯算法中，当从一个结点出发的所有可能路径都已经被
探索且均未能找到有效的解时，这个结点就成为死结点。简而言之，死结点是没有希望的结点，回溯算法会回退
到这些结点的父结点继续搜索。

总结
所以，当我们谈论回溯法的结点类型时，扩展结点、活结点和死结点都是重要的概念。扩展结点代表当前的工作焦点，
活结点代表仍有潜在可能性的结点，而死结点则表示已经被排除的结点。
理解这些概念对于掌握回溯算法的策略和过程至关重要。

5、回溯法的解题步骤