일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 배열
- 스프링
- JAVA SPRING
- 페이코 추천인코드
- Flutter
- 자바 스프링
- 한정 분기
- php 프로그래밍 입문 3판
- 자바
- php 프로그래밍 입문 솔루션
- 페이코 추천인
- 플러터
- 최단 경로
- php 프로그래밍 입문 문제풀이
- SWEA
- 파이썬
- php 프로그래밍 입문
- C
- 백준
- php 프로그래밍
- spring
- php 프로그래밍 입문 예제
- 페이코 초대코드
- C언어
- Java
- programmers
- 페이코 친구코드
- php
- 플러터 개발환경 설정
- php 프로그래밍 입문 연습문제
- Today
- Total
목록상태 공간 트리 (2)
ImJay
0-1 Knapsack Problem 최고 우선 검색을 사용한 한정분기 (Branch and Bound) 서론 한정 분기 전략의 동기 : 되추적의 비효율되추적의 탐색 과정에서 Valid가 적용되더라도 여전히 상당한 비율의 정점을 방문하지 않아도 됨을 발견 되추적의 비효율 해결책 : 각 노드를 방문할 때마다 한계치(bound)를 계산 한계치(Bound) : 해당 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계 값 0/1 Knapsack Problem의 최고 우선 검색을 사용한 한정분기(Branch and Bound) 전략 1. 그 노드의 profit과 weight를 계산한다. 2. 그 노드의 bound를 계산한다. 3. 현재 노드의 profit이 maxprofit보다 크면 maxpr..
색칠 문제 - 백트래킹(Backtracking) 상태 공간 트리와 알고리즘 서론 상태 공간 트리(State Space Tree)는 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리입니다. 백트래킹(Backtracking)은 상태 공간 트리에서 새로운 탐색이 무의미하다고 판단되면, 다른 새로운 탐색이 가능한 선택 포인트(choice point)로 backtrack하여 새로운 탐색을 시도합니다. 더 이상의 선택 포인트가 존재하지 않으면, 탐색은 실패로 끝납니다. 되추적은 갈림길에 표시를 해두고 막다른 골목에 다다르면 갈림길까지 되돌아가서 다른 골목으로 가보는 방법입니다. 깊이 우선 탐색과 관련 있습니다. 색칠 문제(Coloring Problem)는 주어진 그래프에서 인접한 정점은 같은 색을 칠할 수..