아이코시안게임 (1) 썸네일형 리스트형 기사의 여행 | 오일러의 해밀턴 경로와 Warnsdorff의 휴리스틱 알고리즘 knight를 움직여 체스판 전체를 중복 없이 다 지날 수 있을까요? 기사의 여행 문제는 64개의 꼭짓점을 갖는 기사 그래프(knight’s graph)에서 해밀턴 경로와 해밀턴 순환을 찾는 문제입니다. ( 나이트문제는 수학사에 자주 등장한다. 이전영상: 과르니의 체스퍼즐(듀드니방법 , 위상기하학적접근) 이 그래프는 8×8 체스판에서 나이트가 움직일 수 있는 방향들을 변으로 하죠. 문제를 풀기만도 벅찼는데 역시 오일러는 단순하게 풀기만 하는 것이 아니라 대칭성 있는 방식으로 풀어내는군요. 나이트의 이동경로는 두 칸 전진 후 좌 또는 우로 한 칸이라고 기억하시는 게 편하죠. 왼쪽 체스판에서 나이트가 움직이는 방식을 보여줍니다. 레온하르트 오일러를 비롯한 많은 수학자들이 이 문제의 다양한 변형에 대하여 연구.. 이전 1 다음
