여행 세일즈맨 문제란 무엇인가요?
질문: 여행 세일즈맨 문제란 무엇인가요?
A: 여행 세일즈맨 문제(TSP)는 컴퓨터 과학 및 운영 연구 분야의 고전적인 알고리즘 문제입니다. 이 문제는 최적화에 초점을 맞추며, 더 나은 솔루션은 종종 더 저렴하고, 더 짧거나 더 빠른 솔루션을 의미합니다.
질문: TSP는 어떻게 표현되나요?
A: TSP는 노드 집합의 위치를 설명하는 그래프로 가장 쉽게 표현할 수 있습니다.
질문: 누가 TSP를 처음 정의했나요?
A: 여행하는 세일즈맨 문제는 1800년대에 아일랜드의 수학자 W. R. 해밀턴과 영국의 수학자 토마스 커크먼에 의해 정의되었습니다.
질문: 1930년대에는 누가 이 문제를 더 연구했나요?
A: 1930년대에 빈과 하버드의 수학자 칼 멩거가 더 깊이 연구했습니다.
질문: 해슬러 휘트니는 얼마 후 무엇을 소개했나요?
A: 프린스턴 대학교의 해슬러 휘트니는 이 문제를 정의한 직후 "여행 세일즈맨 문제"라는 이름을 도입했습니다.
질문: 이 맥락에서 "더 나은 솔루션"이란 무엇을 의미하나요?
A: 이 맥락에서 더 나은 솔루션이란 더 저렴하거나, 더 짧거나, 더 빠른 솔루션을 의미하는 경우가 많습니다.
질문: 멩거가 TSP를 연구할 때 어떤 알고리즘이 명백하다고 생각했나요?
A: 멩거는 TSP를 연구할 때 명백한 무차별 대입 알고리즘을 고려했으며, 최접근 이웃 휴리스틱을 사용한다고 해서 항상 최적의 결과를 얻을 수 있는 것은 아니라는 것을 관찰했습니다.
