지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2012.10
- 수록면
- 155 - 165 (11page)
이용수
초록· 키워드
오류제보하기
본 논문은 지금까지 해결하지 못한 NP-Hard 문제들 중의 하나인 외판원 문제를 해결할 수 있는 알고리즘을 제안한다. 제안된 알고리즘은 간선교환 방법을 적용한 발견적 알고리즘이다. 초기해를 구하는 전형적인 방법은 첫 번째 노드부터 가장 인접한 노드를 방문하여 외판원의 경로를 결정하는 방법이다. 본 논문에서는 각 노드의 최소 간선을 선택하여 선택된 간선들 중 최소값을 가진 노드부터 출발하는 Min-Min 방법과 최대값을 가진 노드부터 출발하는 Min-Max 방법을 적용하고 두 방법 중 최소 경로길이를 가진 방법을 초기해로 결정하였다. 초기해로부터 최적해를 구하는 과정은 기존의 2-간선 교환 방법 (2-opt)을 기본적으로 적용하고, 추가로 확장된 3-opt와 4-opt를 제안하였다. 이와 같은 방법을 7개의 실제 데이터들에 적용한 결과 지금까지 알려진 최적해를 빠르고 정확히 구하는데 성공하였다.
목차
등록된 정보가 없습니다.
참고문헌 (16)
참고문헌 신청
1. [인터넷자원] - Wikipedia / / Travelling Salesman Problem / Wikimedia Foundation Inc
2. [학술지(정기간행물)] - A. Likas / 2002 / A Note on a New Greedy-solution Representation and a New Greedy Parallelizable Heuristic for the Traveling Salesman Problem / Chaos, Solitons and Fractals 13 : 71 ~ 78
3. [단행본] - A. Schrijver / 2005 / On the History of Combinatorial Optimization (till 1960), in Handbook of Discrete Optimization / Elsevier : 1 ~ 68
4. [단행본] - J. Denzinger / 2008 / The Teamwork Method for Knowledge -Based Distributed Search: The travelling salesman problem / University of Kaiserslautern
5. [기타자료] - J. Pleines / 2006 / ZIP-Methode: ein Kombinatorischer Ansatz zur Optimalen Lősung Allgemeiner Traveling- Salesman-Problem (TSP) / Kőnnen bekannte Lősungen nicht nur auf Gesamtgrphen sondern auf Teilgraphen angewandt werden, so bringt die ZIP-Methode den entscheidenden Quantensprung der rechentechnischen Vereinfachung
2. [학술지(정기간행물)] - A. Likas / 2002 / A Note on a New Greedy-solution Representation and a New Greedy Parallelizable Heuristic for the Traveling Salesman Problem / Chaos, Solitons and Fractals 13 : 71 ~ 78
3. [단행본] - A. Schrijver / 2005 / On the History of Combinatorial Optimization (till 1960), in Handbook of Discrete Optimization / Elsevier : 1 ~ 68
4. [단행본] - J. Denzinger / 2008 / The Teamwork Method for Knowledge -Based Distributed Search: The travelling salesman problem / University of Kaiserslautern
5. [기타자료] - J. Pleines / 2006 / ZIP-Methode: ein Kombinatorischer Ansatz zur Optimalen Lősung Allgemeiner Traveling- Salesman-Problem (TSP) / Kőnnen bekannte Lősungen nicht nur auf Gesamtgrphen sondern auf Teilgraphen angewandt werden, so bringt die ZIP-Methode den entscheidenden Quantensprung der rechentechnischen Vereinfachung
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0