검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Accelerating the Held-Karp Algorithm for the Symmetric Traveling Salesman Problem 대칭형 여행 외판원 문제에 대한 Held-Karp 알고리즘 가속화

Kazuro KIMURA, Shinya HIGA, Masao OKITA, Fumihiko INO

  • 조회수

    0

  • 이것을 인용

요약 :

본 논문에서는 동적 프로그래밍을 통해 대칭형 여행 세일즈맨 문제를 해결하는 Held-Karp 알고리즘의 가속 방법을 제안한다. 제안된 방법은 두 가지 기법으로 가속을 달성한다. 먼저, 하위 문제를 병렬로 해결할 수 있도록 데이터 독립적인 하위 문제를 찾습니다. 둘째, 시계 방향과 시계 반대 방향 모두에서 최적의 경로를 계산하는 MITM(Meet in the Middle) 기술을 사용하여 하위 문제의 수를 줄입니다. 우리는 시간과 공간의 복잡성 측면에서 MITM의 영향에 대한 이론적 분석을 보여줍니다. 실험에서는 제안한 방법을 단일 코어 CPU에서 실행되는 이전 방법과 비교했습니다. 실험 결과, 8코어 CPU에서 제안한 방법이 싱글 코어 CPU에서 제안한 방법보다 9.5~10.5배 빠른 것으로 나타났다. 또한 제안된 방법은 그래픽 처리 장치(GPU)에서 30코어 CPU보다 40~8배 더 빠르다. 부작용으로 제안한 방법은 메모리 사용량을 48% 감소시켰다.

발행
IEICE TRANSACTIONS on Information Vol.E102-D No.12 pp.2329-2340
발행일
2019/12/01
공개일
2019/08/23
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2019PAP0008
원고의 종류
Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
범주
정보시스템의 기초

작성자

Kazuro KIMURA
  Osaka University
Shinya HIGA
  Osaka University
Masao OKITA
  Osaka University
Fumihiko INO
  Osaka University

키워드