몬테칼로
-
알고리즘: 분기한정법(Branch-and-bound)을 이용한 0-1 배낭채우기문제 (0-1 knapsack problem) 공부하기!알고리즘 2020. 11. 15. 21:31
이번 포스팅은 분기한정법(branch-and-bound)을 이용한 0-1 배낭채우기 문제에 대해서 알아본다. 이전의 포스팅에서는 동적계획법(Dynamic programming)과 되추적(Backtracking)을 이용한 0-1 배낭채우기에 대해서 알아봤었다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 알고리즘: 되추적(BackTracking)을 이용한 0 - 1 배낭채우기 문제(0- 1 knapsack problem)..
-
알고리즘: 되추적(BackTracking)을 이용한 0 - 1 배낭채우기 문제(0- 1 knapsack problem) 공부하기알고리즘 2020. 11. 15. 00:33
이전에는 동적계획법을 이용하여 0-1 knapsack 문제에 대해 다루었다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 이번 포스팅은 좀 더 효율적인 0-1 knapsack problem 알고리즘에 대해 알아본다. 기존의 0-1 knapsack problem은 상태공간트리에서 되추적을 이용하였다. 이 문제는 최댓값을 구하는 최적화 문제이기때문에 검색이 완전히 끝나기 전까지는 마디가 해답을 포함하고 있는지 알지 못한다...
-
알고리즘: 해밀턴 회로문제(Hamiltonian Circuit Problem)(Backtracking 문제)알고리즘 2020. 11. 12. 19:17
해밀턴 회로문제(HCP)를 알아보기전에 외판원 문제(TSP)에 대해 간단히 알아보자 이전에 외판원 문제(TSP)에 대해 포스팅했었다. 알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드) 외판원이 출장시간을 줄이기 위해 거주하고 있는 도시에서 출발하여 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아온다고 했을 때 가장 짧은 여행길을 seungjuitmemo.tistory.com 외판원 문제(TSP)의 경우 가장 빠른 방법으로 20개의 도시를 모두 돌고 돌아오는데 걸리는 시간을 계산하면 약 45초가 소요된다. (brute force를 이용하면 19!으로 3800년이상 걸린다) 이번에는..