가장 빠른 길이 항상 가능한 길일까?

그림에서 무엇을 볼까요?

출발지와 도착지 사이의 세 경로에 시간과 배터리 비용을 표시한 지도

배송 로봇은 정해진 시간 안에 물품을 가져가야 합니다. 출발지에서 목적지로 가는 후보는 세 가지입니다. A는 빠르지만 배터리를 많이 쓰고 제한 구역을 지납니다. B는 시간과 소모량이 중간이며, C는 느리지만 배터리를 적게 씁니다. ‘가장 빠르다’는 장점만으로 실행 가능한 경로라고 판단할 수 없습니다.

이 활동의 목표는 제시된 세 경로 중 제한 시간과 배터리 조건을 만족하는 경로를 찾고, 그중 가장 빠른 길을 고르는 것입니다. 도로망 전체에서 모든 가능한 길을 찾는 일반적인 최단 경로 알고리즘과는 범위가 다릅니다. 탐색 범위를 명시하면 ‘최적’이라는 말의 의미도 분명해집니다.