FreeTalk
2013.05.13 02:02
TSP 문제를 푸는 알고리즘..
조회 수 10443 댓글 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)
-
[click] 사람마다 다른 생각 차이
그림에서 연관된 두 가지를 선택하세요. 그리고 그 이유를 말해보세요. .quizButton { background-color:#4473c5; -moz-border-radius:10px; -webkit-border-radius:10px; border-radius:10px; border:1px solid #3c5894; display:inline-block; cursor:pointe... -
[2015년 달라지는 것들] 부동산 중개료 낮추고, 子女장려금(18세 이하 1인당 年 최대 50만원) 신설… 證市 변동 폭 ±30%로
[노동·교통·환경] 최저임금 시간당 5210원에서 5580원으로 입사지원서류 반환 의무화, 민자고속道 무료 긴급 견인 ▲최저임금 시간당 5580원=최저임금이 2014년 시간당 5210원에서 2015년 5580원으로 인상된다. ▲입사 지원 서류 의무 반환=근로자 300명 이상 ... -
YG신인 비아이...대박 사건
본인이 좋아하는 아이돌의 아버지가, 알고보니 삼촌회사 횡령해서 돈빼먹고 망하게 한 장본인이었음. -
WOL(Wake On LAN) 활용 방법 ㅋㅋ
WOL(Wake On LAN) 활용 알아두면 정신 건강에 좋을 상식들 사전지식 1. WOL(Wake On Lan)은 꺼져 있는 컴퓨터를 켜는 기능, 기술을 말한다. 2. 전원이 꺼져있는 컴퓨터를 켜는 기능은 단순히 특정IP로 매직패킷을 보내는 것이다. 3. 매직패킷(Magic Packet) ... -
Who dies? Quiz
누가 죽게되는지 맞춰보시오 ㅋㅋ 문제 풀이는.. 스크롤을 아래로 조금만 내려보면 나옴.. . . . . . . . . . . 결국 다 죽음.. 공에 맞지 않은 A와 E는 에볼라로 죽음 ㅋㅋ 다른 풀이 방법도.. 이건 어떻게 될까? . . . . . . . . . . 이건 모두 공 맞아 죽음... -
UI/UX 모바일 기획시 참고 사이트
모바일 웹/어플리케이션 UI,UX 라이브러리 사이트 들을 소개합니다 이번에 베타서비스 진행중인 Shining을 만들면서 링크들이에요 우선 요즘은 UX가 중요해지는데 특성상 이미지로는 확인이 어려워 Gif로 UX 레퍼런스가 공유되고 있죠. http://blog.mariuszwoz... -
No Image
TSP 문제를 푸는 알고리즘..
미국 세인트 루이스에 있는 워싱턴 대학의 한 컴퓨터 과학자가 세일즈맨 문제 (Salesman problem)을 좀 더 쉽게 풀 수 있는 알고리즘을 개발하고 시험하였다. 워싱턴대학의 컴퓨터학과 교수인 장박사는 컴퓨터계와 비즈니스계에서 오래된 문제로서 TSP (Travel... -
Trigger Words란? 클릭·전환을 유도하는 단어
trigger words에 의한 전환률 28% 증가 사례split test를 통해 trigger word를 발굴, 전환률을 끌어올린 사례입니다. 원본 – 전환률 14.5% 대안본 – 전환률 18.6% https://vwo.com/blog/ab-test-case-study-how-two-magical-words-increased-conversion-rate-b... -
Technical Debt (기술부채)
아름다운 쓰레기와 사상누각 사이 어딘가 얼마 전 개발자 면접을 볼 때 면접자 분이 물었다. XX: Python으로 개발을 하신다고 들었어요. 회사 내에서 어떤 코딩 컨벤션을 사용하시나요? YY: 아.. 그게 이제 맞추려고 하고 있어요. 부끄럽다. 하지만 아직도 못 ... -
Synology NAS 컨텐츠를 Apple TV(Airplay)로 볼 때 자막이 안나오는 경우
시놀로지 NAS에서 바로 애플TV(Airplay)를 통해 동영상을 볼 수 있는데.. 이 때 자막이 안나온다면 이런 부분을 점검 해보자! ㅋㄷ 1. DSM5.0 이상인지 확인한다. - 이 글을 쓰는 시점에서 5.0 보다 낮은 버전은 없겠지만.. 혹시나.. - Synology 쪽에서 2013... -
No Image
Split Test란? (A/B Testing) - 웹사이트 및 광고 운영 최적화를 위한 도구
Split Test는 A/B test 혹은 A/B split test 등으로 불리기도 하는데 기존의 원본과 대안으로 제시된 대안본들을 동시에 운영한 후 각각의 성과를 비교하여 우수한 것을 선정해 내는 테스트 방식입니다. 웹페이지의 헤드라인, 블로그 포스트 제목, 버튼 텍스트... -
No Image
SpaceGlasses are the future of computing
이거 대박.. 이미 판매되고 있다네.. ㅠㅠ