Antes de comenzar oficialmente, me gustaría hacer algunas digresiones:
Sé que los algoritmos codiciosos son un poco difíciles para muchos estudiantes. La dificultad no está en entender el concepto, sino en saber hacerlo tan pronto como lo ves, luego abandonarlo tan pronto como lo haces y luego rendirte a mitad de camino.
Me gustaría decir que esto es normal, porque el algoritmo codicioso es una idea algorítmica, pero no hay una rutina de la que hablar. A diferencia de la última vez que aprendimos árboles binarios, la resolución del problema fue la iteración recursiva. , que se puede hacer de arriba a abajo, de abajo hacia arriba, de izquierda a derecha, la rutina es obvia.
No hace falta decir que cuando se trata de programación dinámica, es más fácil distinguir entre algoritmos codiciosos y programación dinámica.
¿Qué debo hacer si encuentro estos problemas? Simplemente haga esto, solo haga este resumen de preguntas.
Algoritmo codicioso
Para aprender el algoritmo codicioso, primero debes aprender su concepto.
El algoritmo codicioso se refiere a partir del estado inicial del problema y tomar la mejor u óptima opción (más favorable) en cada paso para obtener el valor óptimo (o mejor valor) del resultado.
A través de este concepto, podemos conocer dos puntos clave del algoritmo codicioso:
El algoritmo codicioso siempre toma la mejor decisión a la hora de resolver problemas.
El resultado obtenido por el algoritmo codicioso no es necesariamente el resultado óptimo, pero definitivamente es un resultado más cercano a la solución óptima.
Parece que estos dos puntos pueden resultar difíciles de entender. Utilizo dos ejemplos para entender.
Ejemplo 1: Ahora tenemos cuatro monedas, a saber, 20, 10, 5 y 1. ¿Cuántas monedas necesito para recaudar 36 yuanes?
Según el algoritmo codicioso, definitivamente necesitaremos unas veinte cartas para que salgan. Este problema requiere 1, dejando 36-20 = 16.
Después de mirar 20, veamos 10 yuanes. Necesitamos 10 yuanes y 10 yuanes. Ahora tenemos 16-10 = 6.
A continuación veremos 5 y 1, que requieren 1 respectivamente.
La respuesta final que obtuvimos fue que si queremos recolectar 36 yuanes, necesitamos al menos 4 billetes.
En este ejemplo, se utiliza el billete más grande para igualar cada vez y el saldo restante se iguala con denominaciones más pequeñas. Esto es lo que dijimos a la 1 en punto. A la hora de resolver problemas, siempre tomamos la mejor decisión en el momento.
Ejemplo 2: Tomemos como ejemplo la dispersión de monedas. Ahora tenemos tres monedas: 10, 9 y 1. Si queremos recolectar 18 yuanes, ¿cuántas monedas necesitamos al menos?
En este ejemplo, si todavía utilizamos la estrategia codiciosa anterior, se acabará.
Cuando subí, vi que se necesitaban 10 yuanes, por lo que esta pregunta requería 1 y la cantidad restante era 8 yuanes, por lo que no podía usar 9 apuestas, solo podía usar 8 apuestas de 1 yuan, así que el resultado final fue que usé 9 Note.
Y a través del conocimiento de la escuela primaria, podemos ver a simple vista que está bien usar dos billetes de 9 yuanes.
Este ejemplo ilustra el segundo punto: el resultado obtenido por el algoritmo codicioso no es necesariamente el nudo óptimo.
¿Ves si esto es estúpido? Estúpido tiene razón.
Ahora debes recordar una cosa: los algoritmos codiciosos solo son útiles en determinadas situaciones. En cuanto a qué es una situación parcial, depende de la pregunta.
Oye, no hagas nada primero y luego mira. Por ejemplo, en los dos ejemplos anteriores, debes mirar las reglas entre números. En el Ejemplo 1, las monedas son múltiplos entre sí, pero en el Ejemplo 2, no hay ningún patrón.
Esto hay que hacerlo haciendo más preguntas y resumiendo más.
¿Cuándo utilizar la avaricia?
Para ser honesto, aquí es donde el algoritmo codicioso nos resulta "difícil", es decir, no existe ningún modelado que nos diga directamente "esto es codicioso".
Si es así es difícil Para ser honesto, la mayoría de ellos se utilizan en problemas de optimización combinatoria como los ejemplos de la sección anterior, y el proceso de solución implica juicios de varios pasos.
Cuando se encuentra con un problema de este tipo, su idea puede depender del algoritmo codicioso, pero es sólo "puede".
Debido a que ve un problema de este tipo, cuando piensa en un algoritmo codicioso, primero debe idear una estrategia codiciosa usted mismo y luego debe verificar si los resultados producidos por la estrategia codiciosa que utiliza. son óptimos. De lo contrario, es posible que desee utilizar la programación dinámica que aprenderemos en el próximo proyecto.
Puede preguntar cómo verificarlo, solo proporcione algunos ejemplos confiables para verificar.
Por supuesto, lo "confiable" que digo aquí son sólo algunos casos especiales. De lo contrario, puede simplemente citar algunos ejemplos y descubrir que todos son correctos. En este momento, sentirá que lo que está haciendo es correcto. Tal vez los ejemplos que dio sean correctos.
Me gustaría decir algunas palabras más aquí:
De hecho, en términos generales, la forma más confiable de verificar la exactitud de un algoritmo codicioso como este es mediante la derivación matemática. como la inducción matemática y la ingeniería inversa, etc.
¿Pero cómo decirlo? Aunque la derivación matemática es correcta y el resultado es correcto, es completamente innecesario para nosotros, sin mencionar que muchas personas no pueden derivarlo en absoluto. Incluso si lo hicieran, no significaría mucho para nosotros. Después de todo, los objetivos son diferentes, por eso llegan lejos.
Desde nuestra perspectiva, podemos verificar plenamente la mayoría de los problemas citando algunos casos especiales.
Por supuesto, si quieres preguntarme cómo dar ejemplos especiales, solo puedo decirte: solo haz más preguntas.
Pasos de solución del método codicioso.
Los pasos de resolución de problemas del algoritmo codicioso son en realidad muy similares al algoritmo de divide y vencerás.
Cuando hablé antes sobre el algoritmo de divide y vencerás, hablé de los tres pasos del algoritmo de divide y vencerás:
División: divide el problema original en partes más pequeñas. subproblemas, y los subproblemas están relacionados entre sí de forma independiente, la forma es la misma que la del problema original.
Conquer resuelve recursivamente subproblemas particionados.
Combinación: Este paso no es necesario. Algunos problemas implican fusionar soluciones de subproblemas en soluciones al problema original. Algunos problemas no lo requieren, siempre y cuando se encuentre la solución al subproblema.
Los pasos del algoritmo codicioso son similares. Si está seguro de que el algoritmo codicioso tiene solución, hay tres pasos:
(1) Descomponer el problema en múltiples subproblemas.
(2) Elija una estrategia codiciosa adecuada para obtener la solución óptima local para cada subproblema.
(3) Fusionar las soluciones óptimas locales de los subproblemas en la solución óptima del problema original.
¿Crees que esto es fácil? Jejeje, lo sabrás cuando hagas las preguntas, a veces lo que ves no es el sentimiento real.
Eso es todo acerca del algoritmo codicioso. Realmente no hay mucho en teoría. Sólo para darte una impresión después de leerlo.
Mientras entiendas las cosas teóricas, no tienes más remedio que aprender la codicia. Simplemente haga más preguntas y practique más, y lo entenderá cuanto más lo lea.
De hecho, una serie de acciones son: Oye, este problema parece ser muy codicioso, pruébalo, obtén un resultado, encuentra algunos casos especiales para probar, es la solución óptima, todo está bien. , no es la mejor solución, luego piense si se puede resolver usando programación dinámica o algo así.
Finalmente, no hay necesidad de entrar en pánico por los algoritmos codiciosos. Para decirlo sin rodeos, incluso si no aprendes bien, no será un gran problema. En general, hay relativamente pocas personas que realizan exámenes en entrevistas.