Un robot que puede pisar hasta k = 2 obstáculos
seguidos. Dos programas sobre la misma cuadrícula: uno marca la celda y
otro marca la celda junto con la racha. Uno de los dos contesta mal, y la
celda (1,3) explica por qué.
1. La cuadrícula y la predicción
Gris: obstáculo. De I a F, pasos
mínimos sin pisar más de dos obstáculos seguidos, o −1.
Programa:
¿Qué devuelve este programa?
2. Ejecute
Ámbar: obstáculo
ya alcanzado. Borde rojo: la celda que se está mirando.
Cola: vacía
Paso 0 de 0
En el segundo programa la cola guarda triples: la
tercera componente es la racha.
3. Las llegadas a la celda (1,3)
Viene de
Racha al llegar
Qué pasa
Es la celda con obstáculo de la fila 1, columna 3: se
llega a ella desde (1,2), que es obstáculo, y desde (0,3), que es libre.
4. Por qué falla el primero
5. El costo
¿Cuántos vértices tiene el grafo implícito del segundo programa?
Cada estado se visita a lo sumo una vez y tiene a
lo sumo cuatro aristas, así que el recorrido cuesta Θ(m·n·k). Agregar el
estado multiplica el trabajo por k + 1, y es lo que hace que el programa
conteste bien.
6. Para llevarse
Sin solución aquí. Cambie la regla: el robot puede
pisar a lo sumo k obstáculos en todo el recorrido, seguidos o no.
¿Cuál es el estado ahora? ¿Sigue sirviendo marcar (celda, cuenta)? Diga
cuántos estados hay y dibuje una cuadrícula de 3 × 3 donde las dos reglas
den respuestas distintas.