외판원 문제 시각화
브라우저에서 3–10개 평면 점의 최근접 이웃 순회와 정확한 최단 폐회로를 비교합니다.
사용 방법
사용 방법
- 한 줄에 이름, x, y 형식으로 도시를 입력하세요.
- 최근접 이웃과 정확한 폐회로를 계산하세요.
- 경로 순서, 거리와 그림을 비교하세요.
What is compared
최근접 이웃 경로는 가장 가까운 미방문 점을 반복해 선택합니다. 정확한 결과는 제한된 동적 계획법으로 첫 도시에서 시작하고 끝나는 최단 폐회로를 반환합니다.
Small planar problems only
Enter 3 to 10 unique city names with finite x/y coordinates from −1,000,000,000 to 1,000,000,000. Distances are straight-line coordinate units, not roads, fares, or travel times.
자주 묻는 질문
더 알아보기
최근접 이웃 경로가 항상 최적인가요?
아니요. 빠른 휴리스틱입니다. 입력한 점의 최단 폐회로는 정확한 경로와 비교할 수 있습니다.
여기서 거리는 무엇을 뜻하나요?
좌표상의 직선 유클리드 거리이며 도로, 요금 또는 이동 시간을 뜻하지 않습니다.
도시를 10개까지만 입력할 수 있는 이유는 무엇인가요?
정확한 외판원 계산량이 빠르게 늘어나므로 로컬 계산과 화면 표시가 원활하도록 제한합니다.