상태공간트리
-
알고리즘: 해밀턴 회로문제(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년이상 걸린다) 이번에는..
-
알고리즘: 그래프 색칠하기(m-coloring)(Backtracking 문제)알고리즘 2020. 11. 12. 17:55
m-coloring 문제는 비방향그래프에서 서로 인접한 정점이 같은 색을 같지 않도록 m개의 다른 색으로 칠하는 방법을 찾는 문제다. 예를 들어, 이 그래프에서는 두 가지 색으로 문제를 푸는 것은 불가능하다. 세가지 색을 이용하면 6가지의 해답을 얻을 수 있다 그래프 색칠하기의 주요 응용분야는 지도 색칠하기이다. (이외에도 GSM에서 주파수 할당문제, Aircraft scheduling, final exam timetable등에 사용된다) 여기서 우리는 지도를 평면그래프(planar graph)로 나타낼 수 있는데 평면그래프란 두 개의 이음선이 서로 교차하지 않도록 그린 그래프를 말한다. 다음은 왼쪽의 지도를 평면그래프로 나타낸 것이다. (만약 v1과 v5를 연결하거나 v2와 v4를 연결한다면 평면 그래..
-
알고리즘: 몬테칼로 알고리즘을 이용한 효율성 추적!알고리즘 2020. 11. 9. 23:17
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자) 되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 seungjuitmemo.tistory.com 이 전의 포스팅에서 되추적 알고리즘의 효율성에 대해서 문제 삼았고 이를 해결하지 못했다. 되추적 알고리즘이 어떤 특정 사례를 얼마나 효율적으로 처리하는지에 대한 추정치가 있다면 그 사례에 대해서 그 알고리즘을 사용하는게 타당한 지 결정할 수 있다. 몬테칼로 알고리즘은 확률 알고리즘이기 때문에 표본공간의 무작위 표본의 평균치를 가지고 표본공간에서 정의된 무작위..
-
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자)알고리즘 2020. 11. 9. 20:11
되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 잡아먹히지 않도록 n개의 여왕말을 위치시키는 것이다. 즉, 어떤 여왕말끼리도 같은 행이나 열, 대각선상에 위치할 수 없다. 이 문제에서 순서는 여왕말을 둘 n개의 각각 다른 위치이고, 집합은 서양 장기판에서 말을 둘 수 있는 n제곱개의 위치들이 되고, 기준은 어떤 여왕말도 서로 잡아 먹히지 말아야 한다는 것이다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. DFS에 대해 간단히 설명하면 부모의 노드에서 내려갈 수 있는 자식노드까지 내려가고 그 이후의 자식 노드가 없다면 다시 부모노드로 돌아가면서..