외판원이 여러 도시를 전부 딱 한 번씩 방문하고 출발점으로 돌아와야 해요. 가장 짧은 순서는 무엇일까요? 캔버스를 클릭해서 도시를 놓고, 직접 순서를 정해보거나 컴�터의 답과 비교해보세요.
왜 어려울까요? 도시가 n개면 가능한 방문 순서는 (n-1)!/2가지예요. 도시 5개면 12가지로 쉽지만, 10개면 18만 가지, 15개면 400억 가지가 넘어요! 그래서 완벽한 최적해를 컴퓨터로도 다 확인하긴 힘들고, 실제로는 "꽤 좋은 답"을 빠르게 찾는 방법을 많이 써요.
도시 수 0가능한 경로 수 -현재 경로 길이 -
캔버스를 클릭해서 도시(점)를 3개 이상 놓아보세요. 도시들은 놓은 순서대로 자동 연결돼요.