백 트랙킹, 분기 및 바인딩 및 동적 프로그래밍 알고리즘을 학습하는 데 유용한 리소스는 무엇입니까?

Question

CLRS는 bactracking/branch-and-bound를 다루지 않는 것 같습니다. 나는 여러 가지 자원을 온라인으로 시도했다.하지만 이것들 뒤에 아이디어를 얻었지만, 코드를 쓸 수 없다. 말하자면, 배낭 문제. 그래서 나는 문제가 될 수있는 것을 원하고 이러한 3 가지 접근 방식으로 문제를 해결하고 적어도 의사 코드를 제공합니다. 또는 도움이 될만한 리소스가 있습니다.

Answer 1

역 추적, 분기/바운드 등을 사용하는 알고리즘에서 일반적으로 솔루션 공간 및 검색 공간의 개념이 있습니다. 알고리즘의 목적은 검색 공간을 탐색하여 솔루션 공간의 한 지점에 도달하는 것입니다. 특정 지점에서 최적이라고 판단되는 지점이나 솔루션 공간이 비어 있다는 것을 확인하는 경우가 있습니다 (검색 공간의 모든 요소를 ​​방문하지 않아도 됨) .

첫 번째 단계는 검색 공간에서 효율적인 형식으로 요소를 표현하는 메커니즘을 정의하는 것입니다. 표현을 통해 어떤 요소가 솔루션 공간을 형성하는지, 측정에 사용 된 측정 기준에 따라 요소의 품질을 평가하는 방법, 현재 상태에서 도달 할 수있는 인접 요소를 결정하는 방법 등을 표현할 수 있어야합니다.

일반적으로 이러한 알고리즘은 솔루션을 찾을 때까지 검색 공간을 탐색하거나 해결 방법이 없으면 종료됩니다. 순회는 검색 공간을 탐색하기 위해 일련의 점을 자주 방문하여 병렬로 수행됩니다. 이것은 지점 측면입니다. 당신은 검색 공간의 특정 부분을 방문하기로 결정하고 있습니다.

검색 공간을 탐색하는 동안 특정 경로가 가치가 없다고 판단하여 경로에서 도달 할 수있는 검색 공간의 부분을 탐색하지 않기로 결정할 수 있습니다. 이것은 매우 경계적인 측면입니다.

매우 자주 공간 탐색은 부분 해를 사용하여 수행됩니다. 예를 들어 검색 공간이 8 비트로 표시되는 경우 8 비트 중 두 개의 특정 비트에 고정 값을 할당 한 다음 나머지 6 비트가 나타내는 공간에 대해 바람직한 솔루션을 검색 할 수 있습니다. 두 비트를 고정 값으로 지정하면 솔루션이 없거나 솔루션의 품질이 매우 떨어지는 상황이 발생할 수 있습니다. 그런 다음 알고리즘이 특정 고정 값을이 두 비트에 할당하여 정의 된 해당 하위 공간에서 더 이상 요소를 탐색하지 않도록 검색 공간을 바인딩 할 수 있습니다.

역 추적 기반 시스템의 경우 의사 코드는 사소한 것입니다.문제는 검색 공간을 표현하고, 부분 솔루션을 나타내고, 특정 솔루션의 유효성을 찾아 내고, 앞으로 나아갈 경로를 결정하고, 솔루션의 품질을 측정하기위한 메트릭스를 개발하며, 오 언급 한 주제에, 당신은 단지 적어도 ANS 시작 위키 문서를 먹고 싶어 아무도 대답하지 왜 인터넷 자원의 FULL이기 때문에 당신이 알고 ...

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

Answer 2

이들은 알고리즘이 아닌 검색 기술입니다. 먼저 검색 공간이 무엇인지 분명히 이해해야합니다. 예 : 사용할 수있는 객체의 가능한 모든 하위 집합으로 구성되는 배낭 문제의 경우 때때로 어떤 솔루션이 유효하고 어떤 솔루션이 유효하지 않은지를 정의하는 제약이 있습니다. 예를 들어, 배낭의 전체 볼륨을 초과하는 오브젝트 세트는 유효하지 않습니다. 또한 명확하게 정의 된 목표 (여기에서 선택한 객체의 총 가치)를 가져야합니다.

위키 백과에는 실제로 Branch and Bound에 대한 매우 정확한 설명이 포함되어 있습니다. 다소 고수준이지만 자세한 설명은 검색 공간의 구조에 대한 가정을 필요로합니다. backtracking에는 의사 코드가 있지만 매우 일반적입니다.

이러한 기술에 대한 예제 응용 프로그램을 찾아 연구하는 것이 좋습니다. CLRS에 DP가 포함 된 알고리즘이 적어도 두 가지 있습니다. 필요한 경우 더 많은 정보를 얻을 수 있습니다.