최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.18 no.12, 2013년, pp.75 - 82
This paper proposes a
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
TSP는 무엇이며, 어떤 조건을 만족시켜야 하는가? | 본 논문에서는 외판원 문제 (Traveling Salesman Problem, TSP)의 최적 해를 찾는 알고리즘을 제안한다. TSP는 n개의 도시가 있는 경우, 한 도시 (노드)에서 출발하여 n-1개의 도시를 단지 한번 씩 방문하고 출발 도시로 다시 되돌아오는 해밀턴 사이클 (Hamiltonian Cycle, HC) 문제로 경로 길이의 합이 최소가 되는 조건을 만족시켜야 한다[1]. | |
TSP의 해법은 어떻게 분류되는가? | TSP의해법(SolutionMethod)은 정확한방법(Exact Method)과 근사방법 (Approximate Method)으로 분류된다[1,4] | |
TSP의 해법 중 정확한 방법은 무엇을 수행해야 하는가? | 정확한 방법은 최적 해 (Optimal Solution)를 얻음을 보장하기 위해 n개의 도시를 연결하는 도로 (간선)에 대해 전수 탐색 (Exhaustive Search)을 수행해야 한다. 전수 탐색은 대칭행렬 (Symmetric Matrix)에 대해 (n-1)/2회 수행된다[5]. |
D. S. Johnson and L. A. McGeoch, "The Traveling Salesman Problem and Its Variations," Kluwer Academic Publishers, pp. 369-443, 2002.
A. Likas and V. T. Paschos, "A Note on a New Greedy-solution Representation and a New Greedy Parallelizable Heuristic for the Traveling Salesman Problem," Chaos, Solitons and Fractals, Vol. 13, pp. 71-78, 2002.
A. Schrijver, "On the History of Combinatorial Optimization (till 1960)," in Handbook of Discrete Optimization" (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, pp. 1-68, 2005.
E. Charniak and M. Herlihy, "CSC 751 Computational Complexity: Local Search Heuristics," Department of Computer Science, Brown University, 2008.
J. Pleines, "ZIP-Methode: ein Kombinatorischer Ansatz zur Optimalen Losung Allgemeiner Traveling-Salesman-Problem (TSP)," Konnen bekannte Losungen nicht nur auf Gesamtgrphen sondern auf Teilgraphen angewandt werden, so bringt die ZIP-Methode den entscheidenden Quantensprung der rechentechnischen Vereinfachung, http://www. jochen-pleines.de/download/ZIP2006.pdf, 2006.
L. Stougie, "2P350: Optimaliseringsmethoden," http://www.win.tue.nl/-leen/OW/2P350/Week8/week8.pdf, College Wordt ggeven op vinjdagmiddag, 2001.
L. H. Chuin, "IS 703: Decision Support and Optimization," School of Information Systems," Department of Computer Science, Brown University, 2008.
G. Dantzig, R. Fulkerson, and S. Johnson, "Solution of a Large-scale Traveling-Salesman Problem," The Rand Corporation, http://www.cse.wustl.edu/-chen/7102/TSP.pdf, 1954.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.