with with

Traveling SalesPerson Problem (Dynamic Programming) - 알고리즘 정의 주어진 Graph의 모든 노드를 한 번씩 방문하여 출발했던 노드로 돌아오는 방법 중, 가장 최단 시간으로 걸리는 경로를 찾는 문제이다. 일명 TSP 알고리즘이다. 위 예시에서는 v1 - v3 with611.tistory.com TSP문제는 DP방식으로 접근해 본 적이 있다. 이번에는 Branch and Bound방식을 사용해 접근해보려 한다. Branch and Bound 방식은 탐색(상태 저장) 공간을 트리구조를 이용한다는 점에서 백 트래킹 방식과 유사하 차이점은, 백 트래킹 방식은 앞서 언급한 적이 있듯 depth-first search 방식으로 탐색을 진행하며, 구현에 따라 모든(여러) 최..

- 알고리즘 정의 주어진 Graph의 모든 노드를 한 번씩 방문하여 출발했던 노드로 돌아오는 방법 중, 가장 최단 시간으로 걸리는 경로를 찾는 문제이다. 일명 TSP 알고리즘이다. 위 예시에서는 v1 - v3 - v4 - v2 - v1로 방문하면 최단 시간이 걸린다. 참고로 출발점은 임의로 잡아도 상관 없다. 왜냐하면 모든 노드를 한 번씩 방문하기 때문에 반드시 특정 노드를 어느 순간 지나기 때문이다. 다만, 이해와 구현의 편의성을 위해 v1을 시점이자 종점으로 삼자. 최적의 경로는 위 경로 중 하나의 경우다. v1 - v2 를 지나 최적 경로 A를 지나 v1로 돌아오거나, v1 - v3 를 지나 최적 경로 A를 지나 v1로 돌아오거나, ..., v1 - vn 를 지나 최적 경로 A를 지나 v1로 돌아오..