¿Cómo puedo cambiar este algoritmo codicioso para predecir la puntuación más alta en general?
Hola, a todos, este es mi primer mensaje aquí.
Así que hoy, durante mi clase en la universidad, nuestro profesor nos dio una tarea para escribir un algoritmo:
Escribe una función que devuelva la cantidad de pasos que necesitas dar para obtener la mayor puntuación en un juego de mesa:
Reglas del juego:
– Tiras un dado y te mueves de acuerdo con eso (de 1 a 6 pasos).
– La cantidad de casillas en el tablero puede variar entre 2 y 99.999.
– Cuando pisas una casilla, recibes o pierdes puntos (los puntos en cada casilla van desde -99.999 hasta 99.999).
– Si estás al final del tablero y tu tirada de dado te hace salir de los límites, no te mueves.
Mi enfoque:
Es una especie de algoritmo codicioso:
– Cuenta cada paso y verifica si es mayor o igual a 0,
– Si es negativo, verifica las próximas 6 casillas y muévete a aquella con la puntuación más alta, para perder la menor cantidad de puntos.
Me di cuenta de que mi enfoque es incorrecto después de imaginar este ejemplo:
Imagina un arreglo de {1, -40, -40, -40, -40, -1, -38, -40, -40, -40, -40, -40, 1}
Mi algoritmo codicioso comienza en 1 y ve cuatro -40, un -38 y un -1. Elige -1 porque es la mejor opción, pero ahora terminaremos con un resultado de: 1 + (-1) + (-38) + 1 = -37, sin embargo, si elegimos -38 en lugar de -1, terminaremos con: 1 + (-38) + 1 = -36.
Este es solo un ejemplo simple de los problemas que podrían surgir, imagino que tendría que verificar todas las rutas posibles, porque los algoritmos codiciosos no verifican la mejor ruta posible, solo la mejor aplicable en un momento particular.
Me preguntaba si un grafo con todas las posibilidades podría ser una opción aquí, pero si tuviéramos un arreglo con solo números negativos, terminaríamos con un grafo de tamaño máximo de algo así como (99999^6?), lo que resultaría en ocupar demasiada memoria.
Soy un novato y se me acabaron las ideas. ¿Podría alguien orientarme en la dirección correcta?
davy.ai
Solución
En primer lugar, debemos entender que este problema se puede resolver fácilmente utilizando programación dinámica. Para obtener el resultado óptimo, debemos realizar un seguimiento de la puntuación máxima que podemos obtener para cada ficha y construir la cuenta de pasos que debemos tomar en consecuencia.
Podemos definir un arreglo
maxScorede tamañoN, dondeNes el número de fichas en el tablero. Iteraremos sobre las fichas desde el final hasta el principio y calcularemos la puntuación máxima que podemos obtener desde esa ficha.Para hacer esto, podemos definir la siguiente relación de recurrencia:
Donde
s[i]es la puntuación de la ficha en la que nos encontramos actualmente, ymaxScore[i+j]es la puntuación máxima que podemos obtener comenzando desde la ficha que se encuentra ajpasos de distancia.Una vez que hayamos calculado
maxScorepara todas las fichas, podemos iterar desde la primera ficha y calcular el número mínimo de pasos que debemos tomar para llegar al final con la puntuación máxima.Podemos definir otro arreglo
minStepsde tamañoN, dondeminSteps[i]es el número mínimo de pasos que debemos tomar comenzando desde la fichaipara llegar al final con la puntuación máxima. Podemos calcular esto utilizando la siguiente relación de recurrencia:Donde se suma
1al número mínimo de pasos que debemos tomar para llegar a la siguiente ficha, y tomamos el mínimo sobre todas las fichas posibles en las que podemos aterrizar desde la ficha actual.El resultado final que debemos devolver es
minSteps[0], que es el número mínimo de pasos que debemos tomar comenzando desde la primera ficha para llegar al final con la puntuación máxima.Complejidad
La complejidad temporal de esta solución es
O(N * 6), dondeNes el número de fichas en el tablero. Necesitamos iterar sobre todas las fichas, y para cada ficha, debemos iterar sobre las próximas 6 fichas para calcular la puntuación máxima que podemos obtener.La complejidad espacial de esta solución es
O(N), ya que solo necesitamos almacenarmaxScoreyminSteps, ambos de tamañoN. Esta solución debería funcionar bien para tableros de tamaño moderado, hasta unas pocas cientos de miles de fichas. Para tableros más grandes, es posible que tengamos que considerar algunas optimizaciones, como memoización o poda de rutas innecesarias.