미국 연구팀이 지난 32년간 컴퓨터 전문가들을 괴롭혀 온 난제를 해결하는데 성공했다.
미 노스웨스턴대 최적화기술센터와 아르곤국립연구소 연구원인 장-피에르 구는 과학자들 사이에 `NUG30''으로 알려져 있는 조합 최적화문제를 인터넷으로 연결된 컴퓨터 네트워크로 해결했다고 29일 밝혔다.
이 문제는 30개의 장소에 시설간 물류 비용을 최소화할 수 있도록 30개의 시설을 배정하는 문제로 지난 32년간 컴퓨터 전문가들이 풀려고 시도했으나 실패했으며 현 세대에는 해결이 불가능한 것으로 결론내렸었다.
구는 "이 문제를 속도가 빠른 워크스테이션 컴퓨터 한대로 계산하려면 약 7년이걸리만 수많은 컴퓨터를 인터넷으로 병렬 연결, 컴퓨터의 계산능력을 최대화함으로써 NUG30을 푸는데 일주일이 채 안걸렸다"고 말했다. 이 계산문제는 지금까지 컴퓨터로 수행된 최적화 문제 중 가장 규모가 크고 복잡한 계산의 하나로 여겨지고 있다.
아이오와대 커트 앤슈라이처는 "30자리나 되는 문제의 복잡성은 상상하기 조차 힘들다"며 "이 계산은 빠른 컴퓨터를 가지고 각각의 장소에 배정 가능한 시설을 조사해서 가장 좋은 것을 선택하는 것으로 생각하면 된다"고 말했다.
그는 "할당 숫자가 너무 크기 때문에 초당 1조번씩 계산을 해도 계산을 끝내는 데에는 우주의 나이보다 100배나 긴 시간이 걸릴 것"이라고 말했다.
문제를 푸는 핵심은 고도의 알고리듬 설계와 강력한 계산능력에 있다. 이들이 개발한 알고리듬은 최적 할당이 될 가능성이 없는 것을 반복적으로 제거함으로써 할당 숫자를 처리가능한 수준으로 줄여나간다.
또 연구팀은 노스웨스턴대와 위스콘신대, 아르곤연구소, 조지아공대 등에 있는 워스크테이션을 인터넷으로 연결, 최대 1천대 이상의 컴퓨터가 동시에 계산에 참가하도록 함으로써 계산 성능을 극대화했다.
