Los problemas a los que es aplicable el algoritmo codicioso deben satisfacer dos atributos: (1) Propiedad codiciosa: la solución óptima general se puede lograr a través de una serie de soluciones óptimas locales, y cada elección puede depender de decisiones previas. . (2) Subestructura óptima: la solución óptima general de un problema contiene las soluciones óptimas de sus subproblemas.
Algoritmo codicioso, la palabra "codicioso" como su nombre indica, por lo que su característica habitual es prestar más atención al estado actual. La elección realizada por el método codicioso es la opción óptima para el estado actual. y su capacidad para resolver el problema es Según esta naturaleza, la perspectiva es una "parte" microscópica en lugar de pensar y mirar los problemas desde una perspectiva global y macro.
Los problemas que deben resolverse mediante el método codicioso "no tienen efectos secundarios": la decisión actual no afectará las decisiones posteriores, porque si los problemas están estrechamente relacionados, el proceso de solución será muy confuso. El algoritmo codicioso se utiliza a menudo para problemas de optimización combinatoria y su proceso de solución es un proceso de juicio de varios pasos. Si un problema a resolver tiene las características anteriores, es muy probable que pueda resolverse mediante un algoritmo codicioso.
El núcleo del diseño de algoritmos codiciosos es: "criterios de selección codiciosos", combinados con el "problema de organización de actividades" en el libro "Diseño y análisis de algoritmos", este problema tiene el "tiempo de inicio más temprano" y el "tiempo más corto". duración" "Tres criterios de selección codiciosos para la" hora de finalización más temprana ".
Cuando se selecciona el "criterio de selección codicioso", la información de datos conocida debe preprocesarse de acuerdo con esto. El preprocesamiento habitual es "clasificar". En esta pregunta, los ordenaremos en orden ascendente según el tiempo de finalización.
Después de preprocesar (ordenar) los datos, se recorren en orden a la vez y se seleccionan de acuerdo con las condiciones para construir dos conjuntos, uno de los cuales se utiliza para contener elementos que cumplen las condiciones, y el otro se utiliza para contener elementos que cumplan las condiciones. No hay ningún elemento de juicio, es un proceso paso a paso. (Las aplicaciones típicas con esta característica son el algoritmo Prim y el algoritmo Kruskal utilizados para resolver el árbol de expansión mínimo que aprendí en el curso "Estructura de datos". Ambos recopilan aristas calificadas en un conjunto paso a paso y luego las agregan desde otro conjunto Seleccione los bordes que cumplen con el "criterio codicioso" de un conjunto y colóquelos en el conjunto de árbol de expansión mínimo).