En un edificio de cinco plantas con un único ascensor con capacidad para dos personas, hay tres personas en cada planta, y todas menos una desean ir a otra planta. El ascensor parte de la planta baja (la 1) y va cargando y descargando personas hasta que todas están donde querían estar, y entonces vuelve a la planta baja. Tomando como unidad la distancia entre dos plantas contiguas, se trata de buscar el recorrido mínimo que permite llevar a cada persona a su destino (lo que equivale a minimizar la distancia recorrida, o el tiempo empleado si la velocidad del ascensor es constante). En el siguiente esquema se indica a qué planta desea ir cada una de las tres personas de cada planta (menos una de la planta 2 que no quiere cambiar):
5: 1-2-3
4: 1-3-5
3: 4-5-5
2: 1-2-4
1: 2-3-4