d라이브러리

체스를 하다 보면 기사의 습격에 뜻밖의 패배를 당하기도 한다. 다른 말들이 좌표평면과 같은 체스판에서 상하좌우, 또는 대각선으로 움직이는데 반해 기사는 L자 모양으로 움직일 수 있기 때문이다. 그렇다면 기사만 움직여서 체스판의 64개 정사각형을 모두 밟을 수 있을까?

최근 영국 노팅엄 대의 그레이엄 켄달 박사가 수학자들에게 ‘기사의 여행’이라는 문제로 유명한 이 질문에 대한 답변을 내놓았다. ‘기사의 여행 문제’는 64개의 정사각형을 모두 거쳐 출발한 곳으로 돌아오는 ‘닫힌 여행’과, 출발점과 도착점이 서로 다른 ‘열린 여행’의 경우의 수를 구하는 문제이다. 수학자들은 닫힌 여행의 경우의 수는 26조 개 이상이라고 밝혀냈지만, 열린 여행의 경우의 수는 너무 많아서 그 수조차 파악하지 못하고 있었다.

그레이엄 켄달 연구팀은 그 해답을 개미에서 찾았다. ‘개미떼 최적화 알고리즘’을 사용하여 지금까지 약 50만 가지의 새로운 방법을 찾아낸 것이다. 이 알고리즘은 개미가 페로몬을 통해 집으로 돌아오는 과정을 응용했다. 연구팀은 가상의 개미로 특정 지점에 대한 최단거리를 확률분포를 통해 계산해 냈고, 이 최단거리들을 이어 ‘열린 여행’에 대한 경우의 수를 구해냈다.