As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center提供指导。




已关闭8年。




CLRS似乎没有涵盖bactracking/branch-and-bound。我在网上尝试了几种资源,尽管有了这些想法,但我无法为背包问题编写代码。因此,我想要一种可能会遇到问题的方法,并使用这三种方法解决该问题,并至少给出伪代码。
否则,您所拥有的任何资源都会有所帮助。

最佳答案

在使用回溯,分支/绑定(bind)等的算法中,通常存在解决方案空间和搜索空间的概念。该算法的目标是遍历搜索空间以到达解空间中的某个点,通常是某个度量认为最合适的点,或者确定解空间为空(不访问搜索空间中的每个元素) 。

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

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

在遍历搜索空间期间,他们可以确定特定路径不值得,因此他们可以决定自己将不会探索从该路径可到达的搜索空间部分。这是非常有局限性的方面。

通常,空间的遍历是通过使用部分解决方案来完成的。例如,如果您有一个由八位表示的搜索空间,则可以将固定值分配给八位中的两个特定位,然后为剩余的六位表示的空间搜索理想的解决方案。您可能会发现,将两位特定分配给固定值会导致不存在解决方案的情况(或者解决方案的质量很差)。然后,您可以限制搜索空间,以使算法不再探索通过向这两个位分配特定的固定值而在该子空间中定义的其他元素。

对于基于回溯的系统,伪代码是微不足道的。挑战在于找到有效的表示形式来表示搜索空间,代表部分解决方案,找出特定解决方案的有效性,提出规则来确定采用哪种方法,制定衡量度量质量的度量标准,找出解决方案何时回溯,或回溯多远等等...

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

09-10 01:49
查看更多