메뉴바로가기본문바로가기

동아사이언스

개미가 알려 주는 '기사의 여행'의 비밀

통합검색

개미가 알려 주는 '기사의 여행'의 비밀

2014.03.24 11:26
개미 특성으로 체스에서 기사(Knight)의 움직임에 대한 경우의 수 밝혀내
위키미디어 제공
위키미디어 제공

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

 

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

태그

이 기사가 괜찮으셨나요? 메일로 더 많은 기사를 받아보세요!

댓글 0

10 + 5 = 새로고침
###
    과학기술과 관련된 분야에서 소개할 만한 재미있는 이야기, 고발 소재 등이 있으면 주저하지 마시고, 알려주세요. 제보하기