Memo Memo Memo Memo

백트래킹_되추적

• 알고리즘: 해밀턴 회로문제(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년이상 걸린다) 이번에는..

  Read More