# 기사의 여행

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

체스판 위에서 기사의 여행 경로

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

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

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

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

## [편집] 바깥 고리

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

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

원본 주소 ‘http://ko.wikipedia.org../../../%EA%B8%B0/%EC%82%AC/%EC%9D%98/%EA%B8%B0%EC%82%AC%EC%9D%98_%EC%97%AC%ED%96%89.html’

분류: 수학 토막글 | 그래프 이론

##### Views

- 문서
- 토론
- 현재 버전

##### 찾기

##### 다른 언어

- Deutsch
- English
- Español
- Français
- עברית
- 日本語
- Latina
- Português
- Slovenščina
- ไทย
- 中文