아무 말

Knight's Tour  Knight's tour(기사의 여행)은 체스보드에서 나이트가 체스보드의 모든 칸을 방문하는 경로이다. 체스보드의 크기와 나이트가 여행을 시작하는 칸에 따라서 knight's tour가 존재하지 않을 수 도 있다. 만약 knight's tour가 존재하고, 나이트가 tour의 마지막 위치에서 시작 위치로 이동이 가능하다면, 이를 closed knight's tour라고 부르며, 그렇지 않을 때 open knight's tour라고 부른다. 아래 두 문장은 knight's tour에 대한 잘 알려진 사실이다. \(n \times n\) 체스보드에서 \(n\)이 홀수라면 \(n \ge 5\)일때 open knight's tour가 반드시 존재한다.\(n\)이 짝수라면, \(n \g..

바이토닉 투어란? 바이토닉 투어(Bitnoic Tour)또는 바이토닉 TSP(Bitonic Traveling Salesman Problem)는 외판원 문제의 일반화로, 유클리드 평면 위의 정점에서 이루어지며, 수직선과 투어를 표현한 다각형이 최대 2번 교차해야 한다는 조건이 붙어있다. 바이토닉 투어는 일반적인 외판원 문제와는 다르게, 다항 시간 내에 해결할 수 있는 방법이 존재한다. 그리고 이를 최적화 하면 \(O(N \log(N))\)에 문제를 해결할 수 있다. 외판원 문제와의 관계 당연하게도 유클리드 평면 위의 외판원 문제의 해와 바이토닉 투어의 해는 다르다. 하지만, 길게 늘어진 공간에서는 같을 수 있는데, 주어지는 모든 점의 좌표가 정수일 경우 이 늘어진 공간의 폭이 \(2 \sqrt{2}\)이하..