7

CLRS 似乎没有涵盖回溯/分支绑定。我在网上尝试了几个资源，虽然我得到了这些背后的想法，但我无法为背包问题编写代码。所以，我想要的东西，可能是，解决一个问题，用这 3 种方法解决它，至少给出伪代码。或者任何你喜欢的资源都会有帮助。

4

2 回答 2

4

在使用回溯、分支/绑定等的算法中，通常有解决方案空间和搜索空间的概念。该算法的目标是遍历搜索空间以到达解空间中的一个点，通常是某个度量认为最优的点，或者确定解空间是空的（不访问搜索空间中的每个元素） .

第一步是定义一种机制，以一种有效的格式表达搜索空间中的元素。该表示应该允许您表达哪些元素构成了解决方案空间，一种通过用于测量的度量来评估元素质量的方法，一种确定您可以从当前状态到达的相邻元素的方法等等。

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

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

很多时候，空间的遍历是通过使用部分解决方案来完成的。例如，如果您有一个由 8 位表示的搜索空间，您可以将固定值分配给 8 位中的两个特定位，然后为剩余的 6 位表示的空间搜索一个理想的解决方案。您可能会发现将两位特定分配给一个固定值会导致无法存在解决方案（或解决方案的质量非常差）的情况。然后，您可以绑定搜索空间，以便算法不再探索该子空间中的任何元素，该子空间通过为这两个位分配特定的固定值来定义。

对于基于回溯的系统，伪代码是微不足道的。挑战在于找到有效的表示来表示搜索空间，表示部分解决方案，找出特定解决方案的有效性，提出规则来确定先走哪条路径，制定衡量解决方案质量的指标，弄清楚什么时候回溯，或者回溯多远等等……

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)
  }
}
于 2012-08-25T19:11:45.383 回答
0

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

实际上，Wikipedia 包含对Branch and Bound的非常准确的描述。它相当高级，但任何更详细的描述都需要对搜索空间的结构进行假设。对于回溯，甚至还有一些伪代码，但又非常笼统。

另一种（可能更好）的方法是找到这些技术的示例应用并进行研究。在 CLRS 中至少有几个涉及 DP 的算法，如果需要，您当然可以搜索更多。

于 2012-08-25T13:50:15.567 回答