'여행하는 외판원 문제'가 무엇인지 알려주세요.

Question

안녕하세요. 오늘도배웁니다.

어떤 소설을 읽다보니 '여행하는 외판원 문제'라는 표현이 있더라구요.

어떤 의미인지 알고 싶습니다.

감사합니다.

Answer 1

안녕하세요. 빛나라 하리 입니다.

여행하는 외판원 문제 (TPS)의 주요 원인은 모든 도시를 한 번 씩 방문하고 시작점으로 돌아오는 최소 비용

경로는 찾는 최적화 문제의 특성에 있습니다.

Answer 2

'여행하는 외판원 문제'는 여러 도시를 한 번씩 방문하고 출발지로 돌아오는 최단거리 경로를 찾는 문제입니다.

모든 도시간 거리를 고랴해야 하므로 경우의 수가 폭발적으로 늘어나는 조합최적화문제입니다.

컴퓨터 과학에서 NP-난해 문제로 분류디며 뮬류, 배송, 경로 최적화에 응용됩니다.

Answer 3

'여행하는 외판원'은 여러 도시를 한 번씩 방문하고 출발점으로 돌아오는 가장 짧은 경로를 찾는 조합 최적화 문제(Travelling Salesman Problem, TSP)를 의미하는데요.

이 문제는 실제 외판원이 여러 도시를 방문하여 물건을 판매할 때 최소의 이동 거리 또는 비용으로 모든 곳을 방문하는 최적의 순서를 찾는 문제에서 유래되었다고 합니다.

소설책에 이러한 내용이 있었던건가요? 무슨책인지 궁금하네요.