学习回溯法、分支定界和动态规划算法的好资源有哪些？

Question

CLRS似乎没有涉及回溯/分支限界算法。虽然我尝试了几个在线资源，但我无法编写代码来解决例如背包问题这样的问题，尽管我理解了它们的理念。因此，我想要一个东西，可能需要使用这三种方法之一解决问题，并至少给出伪代码。或者任何您认为有帮助的资源。

- user1624400

---

你知道为什么没有人回复吗？因为互联网上关于这些话题的资源已经非常丰富了，你只需要找到至少一篇维基百科文章并从那里开始。 - FUD

Answer 1

在使用回溯、分支/界限等算法中，通常存在解空间和搜索空间的概念。该算法的目标是遍历搜索空间，以达到解空间中的某一点，并经常是按照某种度量标准被认为是最优的点，或者确定解空间为空（而不需要访问搜索空间中的每个元素）。

第一步是定义一个机制，以高效的格式表达搜索空间中的元素。该表示应允许您表达哪些元素构成解空间，以度量用于衡量的方式评估元素的质量，以及确定从当前状态可以到达的相邻元素等方式。

通常这些算法将遍历搜索空间直到找到解决方案，或者如果不存在解决方案则退出。通过访问一系列点来遍历搜索空间，通常与并行探索搜索空间。这是分支方面; 您正在做出决策，以访问搜索空间的某些部分。

在遍历搜索空间期间，他们可能会确定特定路径不值得，因此他们可能会决定不探索从该路径可达的搜索空间的部分。这是非常有限的方面。

往往通过使用部分解决方案来遍历空间。例如，如果您具有由八位表示的搜索空间，则可以为八位中的两个特定位分配固定值，然后搜索剩余六位表示的空间的理想解决方案。您可能会发现将两位分配给固定值的特定赋值会导致不存在解决方案（或解决方案的质量非常差）的情况。然后，您可以限制搜索空间，以便算法不再探索通过将特定固定值分配给这两个位所定义的任何子空间中的任何元素。

对于基于回溯的系统，伪代码是微不足道的。挑战在于找到有效的表示来表示搜索空间，表示部分解决方案，找出特定解决方案的有效性，制定确定要采取哪个路径的规则，开发用于衡量解决方案质量的度量标准，弄清何时回溯或回溯多远等等...

StateStack.push(StartState)
loop{
  curState = StateStack.top
  nextState = calculateNextState(curState)
  StateStack.push(nextState)
  if(reachedFinalGoal(nextState)){
     break;
  }
  if(needToBackTrack(StateStack)){
     curState = nextState
     stateToBackTrackTo = calculateStateToBackTrackTo(stateStack)
     while(curState != stateToBackTrackTo){
       stateToGoBackTo = stateStack.pop
       curState = RollBackToState(stateToGoBackTo)
  }
}

- VSOverFlow

---

优美地陈述了关于“空格”的内容。 - WestCoastProjects

Answer 2

这些都是搜索技巧，而不是算法。首先，您应该清楚地了解搜索空间是什么。例如，在背包问题的情况下，它将包含所有可用对象的可能子集。有时会有约束条件来定义哪些解决方案是有效的，哪些是无效的，例如超过背包总体积的对象集是无效的。此外，您还应该有明确定义的目标（在此处为所选对象的总价值）。

事实上，Wikipedia中包含了分支定界的相当准确的描述。它是相当高级的，但是任何更详细的描述都需要对搜索空间的结构进行假设。对于回溯，甚至有一些伪代码，但同样非常通用。

另一种（也许更好的）方法是找到这些技术的示例应用并研究它们。 CLRS中至少有几种涉及DP的算法，如果需要，您肯定可以在Google上找到更多。

- Qnan