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

Question

<分区>

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)
  }
}