기사의 여행

위키백과 ― 우리 모두의 백과사전.

기사의 여행은 체스판의 기사에 대한 수학적인 알고리즘 문제의 일종이다. 체스의 말 움직이는 규칙에 따라 기사를 모든 칸으로 정확히 한 번씩 갈 수 있도록 하는 방법을 찾는 문제이다. 이 문제의 해법은 수없이 많다. 기사가 마지막 위치에 가서 첫 번째 위치로 공격을 할 수 있는 상태가 되면 여행이 닫혀 있다고 하고, 그렇지 않으면 여행이 열려 있다고 한다.

오일러를 비롯한 많은 수학자들이 이 문제의 다양한 변형에 대하여 연구하였다. 예를 들어 다음과 같은 다양한 변형 문제가 있다.

• 체스판의 크기가 다른 문제
• 두 명의 선수가 경기를 하는 경우를 다룬 문제
• 기사가 움직이는 방법을 조금 다르게 한 문제

기사의 여행 문제는 그래프 이론에서 NP-완전인 해밀톤 경로 문제의 특별한 경우이다.

[편집] 바깥 고리

• 머리를 내밀어 봅시다: 기사의 여행 - 기사의 여행 문제를 푸는 방법 중의 하나인 Warnsdorff의 규칙을 이용한 C언어 소스 코드

이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.