7

CLRS は、バックトラッキング/分岐限定をカバーしていないようです。オンラインでいくつかのリソースを試しましたが、これらの背後にあるアイデアは得られましたが、ナップサックの問題などのコードを書くことができません。したがって、問題を取り上げてこれらの 3 つのアプローチで解決し、少なくとも疑似コードを提供する何かが必要です。または、あなたが知っているリソースが役に立ちます。

4

2 に答える 2

4

バックトラッキング、分岐/境界などを使用するアルゴリズムには、通常、ソリューション スペースと検索スペースの概念があります。アルゴリズムの目的は、探索空間を横断して解空間のポイントに到達することです。多くの場合、何らかのメトリックによって最適と見なされるポイントに到達するか、解空間が空であることを確立します (探索空間のすべての要素にアクセスする必要はありません)。 .

最初のステップは、検索空間内の要素を効率的な形式で表現するメカニズムを定義することです。表現は、ソリューション空間を形成する要素、測定に使用されるメトリックによって要素の品質を評価する方法、現在の状態から到達できる隣接要素を決定する方法などを表現できるようにする必要があります。

通常、これらのアルゴリズムは、解が見つかるまで探索空間を走査するか、解が存在しない場合は終了します。トラバーサルは一連のポイントを訪問することによって行われ、多くの場合並行して探索空間を探索します。これがブランチの側面です。検索スペースの特定の部分を訪問する決定を下しています。

探索空間のトラバーサル中に、特定のパスには価値がないと判断する場合があるため、パスから到達可能な探索空間の部分を探索しないと決定する場合があります。これは非常に境界的な側面です。

多くの場合、空間の横断は部分解を使用して行われます。たとえば、8 ビットで表される検索空間がある場合、8 ビットのうちの特定の 2 ビットに固定値を割り当て、残りの 6 ビットで表される空間の望ましい解を検索することができます。2 つのビットを特定の固定値に割り当てると、解が存在しない (または解の質が非常に悪い) 状況が発生することがあります。次に、特定の固定値をこれらの 2 ビットに割り当てることによって定義されたサブスペース内でアルゴリズムがそれ以上要素を探索しないように、検索スペースを制限できます。

バックトラッキング ベースのシステムの場合、疑似コードは簡単です。課題は、検索空間を表す効率的な表現を見つけること、部分的な解決策を表すこと、特定の解決策の有効性を見つけること、どのパスを優先するかを決定するためのルールを考え出すこと、解決策の質を測定するための指標を開発すること、いつバックトラックするか、またはバックトラックする距離など...

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

これらはアルゴリズムではなく検索手法です。まず、検索空間とは何かを明確に理解する必要があります。たとえば、利用可能なオブジェクトのすべての可能なサブセットで構成されるナップザック問題の場合です。場合によっては、有効なソリューションと無効なソリューションを定義する制約が存在することがあります。たとえば、ナップザックの総体積を超えるオブジェクトのセットは有効ではありません。また、目的を明確に定義する必要があります (ここで選択したオブジェクトの合計値)。

ウィキペディアには、実際にはBranch and Boundのかなり正確な説明が含まれています。これはかなり大まかな説明ですが、より詳細な説明を行うには、検索スペースの構造に関する仮定が必要になります。バックトラッキング用に疑似コードもありますが、これも非常に一般的なものです。

別の (そしておそらくより良い) アプローチは、これらの手法の適用例を見つけて研究することです。CLRS には DP を含む少なくとも 2 つのアルゴリズムがあり、必要に応じてさらに多くのアルゴリズムを検索できます。

于 2012-08-25T13:50:15.567 に答える