목록0-1 knapsack problem (1)

나만의 개발노트

[알고리즘] Backtracking

Backtracking*상태 공간 트리에서 DFS를 수행하여 promissing 노드만 탐색한다.non-promissing한 노드는 가지치기(pruning)하여 효율적으로 탐색한다 *상태 공간 트리(State Space Tree) 루트 노드부터 리프 노드까지의 경로가 후보 솔루션이 된다.non-promissing한 경로는 탐색하지 않고 부모 노드로 돌아가 다른 자식 노드를 탐색한다.void checknode(node v){ node u; if(promising(v)) //현재 노드(v)가 promising하다면, if(there is a solution at v) //v에서 결론이 나오면, 결론 반환 write the solution; ..
[알고리즘] 2024. 6. 5. 15:31
이전 Prev 1 Next 다음