FreeTalk
2013.05.13 02:02
TSP 문제를 푸는 알고리즘..
조회 수 10440 댓글 0
미국 세인트 루이스에 있는 워싱턴 대학의 한 컴퓨터 과학자가 세일즈맨 문제 (Salesman problem)을 좀 더 쉽게 풀 수 있는 알고리즘을 개발하고 시험하였다.
워싱턴대학의 컴퓨터학과 교수인 장박사는 컴퓨터계와 비즈니스계에서 오래된 문제로서 TSP (Traveling Salesman Problem) 이라고 알려져 있는 문제를 풀기 위한 알고리즘을 개발했다. TSP 문제는 우체부가 효과적으로 우편물을 배달하는 경로를 결정하는 것과 유사한 문제들을 포괄적으로 의미한다. 장박사는 AT&T 벨 연구소의 데이빗 존슨 박사와 함께 연구를 수행했다. 존슨박사는 복잡한 계산 분야에서 널리 이름이 알려진 전문가이다.
이들은 장박사의 이름을 딴 장알고리즘을 10개의 이론적인 TSP 문제에 적용해서 그 중 절반의 문제에 대하여 이 알고리즘이 최선의 해를 구한다는 사실을 밝혔다. 이중에는 AT&T 벨 연구소가 관심을 가지고 있는 문제가 포함되어 있다.
장알고리즘은 실제 생활과 관련된 문제에도 적용될 수 있다. 예를 들어 AT&T벨 연구소가 관심을 가지는 문제는 공중전화기에서 동전을 회수하는 경로를 최적화하는 것이다. 장 알고리즘은 동전을 회수할 때 동일한 장소를 두 번 방문하지 않으면서 짧은 시간내에 모든 공중전화에서 동전을 회수해서 회사로 돌아올 수 있는 경로를 결정할 수 있다. 이를 통해 회사는 시간과 비용을 절감할 수 있다.
이들은 공중전화가 100대, 316대, 1000대, 3162대 있는 4가지 경우에 대해 알고리즘을 시험했다. 비교를 위해 6개의 다른 알고리즘을 이용한 시험도 실시했는데 장의 알고리즘이 가장 짧은 경로, 가장 효율적인 경로, 가장 비용이 적게드는 경로를 찾아낸다는 것을 알 수 있었다. 이 알고리즘은 50만개의 노드가 있는 경우에도 적용이 될 수 있으며 공중전화 문제의 경우 단 몇 초만에 해법을 찾아낼 수 있다.
장 알고리즘은 "No-wait flowshop" 문제에도 적용된다. 이 문제는 자동차 각 부분에 페인트 칠을 할 때 처음부터 끝날 때 까지 가장 효율적인 경로를 결정하는 것이다. 그 외에도 컴퓨터의 디스크 드라이버나 유전의 석유시추장비의 이동 경로 결정에도 적용될 수 있다.
연구에서 고려된 TSP 문제는 비대칭으로 한 지점 A에서 B 까지의 거리가 B에서 A까지의 거리와 같지 않은 경우를 말한다. 이러한 비대칭 문제는 실제 세계와 유사하다 . 예를 들어 고속도로를 주행할 때 A에서 B 로 가는 경우에는 주행료를 내지만 반대로는 주행료를 내지 않는 경우가 해당된다. 장 알고리즘은 이러한 비대칭 문제를 해결할 수 있다.
이들의 연구결과는 워싱턴 D.C에서 열렸던 제 3차 알고리즘 공학과 실험에 관한 워크샵에서 발표되었다. 연구결과 중 일부는 출판예정인 Traveling Salesman Problem 에 한 부분으로 포함된다. 이번 연구는 국립과학재단에서 일부 보조를 받았다.
장 알고리즘은 비대칭 TSP 문제를 푸는데 적합한 두 개의 방법 중 하나로 여겨지고 있다. 나머지 하나는 알고리즘을 개발한 두명의 컴퓨터 학자의 이름을 딴 Kanellakis-Papdimitrious local search 알고리즘이다.
장박사는 현재 DNA, RNA, 단백질과 같은 생물학적 자료를 분석하기 위한 효율적인 탐색 알고리즘 연구를 하고 있다. 장박사는 "지난 세기가 정보와 컴퓨터 기술이 이끌었다면 이번 세기는 생물학의 시대가 될 것이다. 정보기술과 생물학을 결합하게 되면 생명공학에 대한 이해와 함께 질병치료를 통한 보다 나은 삶을 사는데 도움이 될 것이다" 라고 말했다. - (kwonsk@nanum.kaeri.re.kr)
-
우리아이가 달라졌어요 - 최강폭군 혜성이
아이는 부모의 거울. 아빠의 지시적/명령적인 행동과 편애에 대한 도전적 반항장애.. -
늙은 쥐의 지혜
한 늙은 쥐가 있었다. 늙은 쥐는 물건 훔치는 데 재주가 뛰어나 쥐들의 선망의 대상이었지만, 나이가 들면서 점차 눈이 어두워져 혼자 힘으로는 다닐 수 없게 되었다. 젊은 쥐들은 늙은 쥐를 비웃으며 말했다. "쓸모도 없는 늙은 쥐에게는 더 이상 음식을 줄 ... -
No Image
맥 Balsamiq Mockups 무료이용 [꼼수]
맥 Balsamiq Mockups 무료이용 [꼼수] MAC and IPhone 2011/09/02 11:53 복사 http://xxsoo.blog.me/130117460218 문제 : Balsamiq Mockups 은 좋은 디자인 툴이다. 하지만 사서 이용하자니 너무 비싸다. 무료 신청기간도 끝났다 ;; Balsamiq Mockups 트라이얼... -
파혼이 늘어나는 이유~ ㅎㅎ
옛날 기사지만 지금도 이런 상황은 흔할 듯.. 양가 어르신들의 패기.. -
No Image
크롬 브라우저에서 원격으롤 게임을..
크롬 브라우저로 서로 싱크 맞추는.. http://www.chrome.com/supersyncsports/ -
No Image
700여개 직업중 만족도 순위
[출처] http://news.sbs.co.kr/section_news/news_read.jsp?news_id=N1001136296 [직업만족도 순위] ** 2012.3. 한국고용정보원 / 20점 만점 순위직업명평균점수1초등학교교장17.86672성우17.60003상담전문가17.56254신부17.50005작곡가17.43336학예사(큐레이... - Read More
-
흑산도 다물도 전경 ㅋㅋ
어렸을 때 잠깐 살았던 동네.. 동네 모습은 기억이 가물가물 하지만 저 때 추억이 제일 많았던 것 같다. 가두리에서 줄낚시도 하고 바닷가에서 발가벗고 해수욕도하고.. 사진을 보니 섬이 작긴 했지만.. 저렇게 작았나 싶기도 하고 ㅋㅋ 6살 때 팬티만 입고 ... -
No Image
생활수학 상식.. 세상이 다 수학이야? ㅋㅋ
보온병은 왜 원기둥인가? 음료수병이나 보온병 등 액체를 담는 용기들은 대부분 원기둥 모양이다. 여기에는 어떤 수학적 이유가 있을까? 용기를 만들 때는 언제나 재료를 적게 들이고도 많은 양의 액체를 담을 수 있어야 한다. 원의 넓이와 일부 정다각형의 넓... -
하루살이와 메뚜기
하루살이가 메뚜기하고 아침부터 놀다가 저녁이 되었습니다. 메뚜기가 하루살이에게 말했습니다. "하루살이야, 벌써 저녁이 되었으니 그만 놀고 내일 만나자." 그러자 하루살이가 메뚜기에게 묻습니다. "내일이 뭔데?" 하루살이는 하루만 살기 때문에 "내일"을... -
No Image
마타도어에 대한 어원과 뜻 ㅋㅋ
근거 없는 사실을 조작해 상대편을 중상 모략하거나 그 내부를 교란시키기 위해 하는 「흑색선전」의미로 정치권에서 널리 쓰임. 마지막에 소의 정수를 찔러 죽이는 투우사(bullfighter)를 뜻하는 스페인어 「Matador(마따도르)」에서 유래. 투우를 시작할 때 ... -
No Image
인터넷으로 영어공부 혼자하기 추천사이트 20선
영어공부를 하기 위해서 꼭 비싼 돈을 지불할 필요가 있을까요... 인터넷과 IT의 발달로 집에서도 무료로 영어공부할 수 있는 기회가 점차 늘어나고 있습니다. 저는 즐겨찾기에 이런 사이트들을 차곡 차곡 저장해두고 있는데요, 여러분께 그 사이트들을 쏵~ 다...