Contents

FreeTalk
2013.05.13 02:02

TSP 문제를 푸는 알고리즘..

조회 수 10373 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
미국 세인트 루이스에 있는 워싱턴 대학의 한 컴퓨터 과학자가 세일즈맨 문제 (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)


?

  1. No Image

    [linux] 리눅스에 대해.. (백과사전에서..)

    워크스테이션이나 개인용 컴퓨터에서 주로 사용되는 유닉스와 유사한 오퍼레이팅시스템. 1989년 핀란드 헬싱키대학에 재학중이던 리누스 토르발스(Linus Torvalds)가 유닉스를 기반으로 개발한 공개용 오퍼레이팅시스템(OS)으로, 1991년 11월 버전 0.10이 일반...
    Date2013.05.13 CategoryFreeTalk Byhooni Views9001
    Read More
  2. No Image

    TSP 문제를 푸는 알고리즘..

    미국 세인트 루이스에 있는 워싱턴 대학의 한 컴퓨터 과학자가 세일즈맨 문제 (Salesman problem)을 좀 더 쉽게 풀 수 있는 알고리즘을 개발하고 시험하였다. 워싱턴대학의 컴퓨터학과 교수인 장박사는 컴퓨터계와 비즈니스계에서 오래된 문제로서 TSP (Travel...
    Date2013.05.13 CategoryFreeTalk Byhooni Views10373
    Read More
  3. 게시판에서 싸움나는 이유

    게시판에서 싸움나는 이유 A: "어제 중국집 가서 짜장면 시켜 먹었는데 정말 맛있더군요."(평범한 문제 제기) B: "짜장면이 뭐가 맛있어요? 우동이 훨 맛있지"(평범한 반론) C: "우동이요? 에이, 우동보다는 짜장면이죠. 돼지고기도 들어가고."(재반론, A의 ...
    Date2013.05.14 CategoryFreeTalk Byhooni Views11277
    Read More
  4. [펌] 좋은 기획서는 '형용사' 가 없다.

    좋은 기획서는 무엇을까? 좋은 기획서는 어떻게 작성해야 할까? 기획자 커뮤니티를 가면 좋은 기획서를 쓰는방법에 대해서 많이 나열되어 있다. 하지만 나는 기획자가 아니기 때문에 무엇이 좋은 기획서인지? 어떻게 해야 좋은 기획서를 쓸수 있는지 전혀 모...
    Date2013.05.15 CategoryFreeTalk Byhooni Views11055
    Read More
  5. No Image

    모두가 원하는 개발자 되기 10단계

    발자가 되기 위해 프로그래밍 기술만 있으면 된다고 생각한다면, 틀렸다! 코드를 잘 쓰는 것도 중요하지만, 일의 능률을 높이고 더 높은 연봉을 받기 위해서는 많은 이에게 자신이 누구인지 알리는 것이 중요하다. 다시 말해, 스스로를 마케팅해야 한다. 여기...
    Date2013.05.15 CategoryFreeTalk Byhooni Views10541
    Read More
  6. 뭐? 아프니까 청춘이다?

    언젠가, "시크릿"이라는 책이 베스트 셀러 였던 시절에.. 당시 다니던 회사에서 매달 책을 읽고 독후감을 제출해야 했고 평가에 반영됐다. 베스트 셀러라서 읽기 시작했지만.. 읽으면서 꾸준히 화가 났던 그 "시크릿"이 생각나게 하는.. 최근에 나를 열라 폭...
    Date2013.05.28 CategoryFreeTalk Byhooni Views11629
    Read More
  7. No Image

    맥 Balsamiq Mockups 무료이용 [꼼수]

    맥 Balsamiq Mockups 무료이용 [꼼수] MAC and IPhone 2011/09/02 11:53 복사 http://xxsoo.blog.me/130117460218 문제 : Balsamiq Mockups 은 좋은 디자인 툴이다. 하지만 사서 이용하자니 너무 비싸다. 무료 신청기간도 끝났다 ;; Balsamiq Mockups 트라이얼...
    Date2013.05.28 CategoryFreeTalk Byhooni Views9153
    Read More
  8. No Image

    영어로 자기소개 ㅋㅋ

    비밀글입니다.
    Date2013.05.28 CategoryFreeTalk Byhooni Views0
    Read More
  9. No Image

    오래된 아이큐 테스트 문제

    이 퀴즈는 아인슈타인이 생전에 직접 출제한 문제로 알려져 있으며 아인슈타인은 "전 세계 인구의 98%는 풀 수 없다"고 단언한 것으로 전해지고 있다. 당신의 아이큐는 지구촌 인구의 2% 범위에 들 수 있을까. *****[문제] 다음 상황을 전제로 금붕어를 기르는...
    Date2013.05.28 CategoryFreeTalk Byhooni Views10559
    Read More
  10. 무재칠시(無財七施)

    무재칠시(無財七施) 어떤 이가 석가모니를 찾아가 호소를 하였습니다. "저는 하는 일마다 제대로 되는 일이 없으니 이 무슨 이유입니까?" 석가모니께서 말하였습니다. "그것은 네가 남에게 베풀지 않았기 때문이니라" "저는 아무 것도 가진 게 없는 빈털터리입...
    Date2013.05.28 CategoryFreeTalk Byhooni Views7677
    Read More
  11. 혈액형으로 보는 관계도 ㅎㅎ

    맞나? ㅋㅋ
    Date2013.05.28 CategoryFreeTalk Byhooni Views11699
    Read More
  12. 바이오리듬에 대해 ㅎㅎ

    https://www.hooni.net/biolythm/bio_landscape.php 바이오리듬의 확립은 1906년 독일의 의사 프리즈가 발견하였다. 프리즈는 환자들을 치료하면서 환자들의 출생일을 기점으로 하여 체계적인 통계를 바탕으로 신체리듬, 감성리듬, 지성리듬의 세가지가 변화...
    Date2013.05.28 CategoryFreeTalk Byhooni Views8018
    Read More
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 73 Next
/ 73