¿Qué es un algoritmo codicioso?
En el algoritmo codicioso, un conjunto de recursos se divide de forma recursiva en función de la disponibilidad máxima e inmediata de ese recurso en cualquier etapa de ejecución determinada.
Para resolver un problema basado en el enfoque codicioso, hay dos etapas
- Escaneando la lista de elementos
- Mejoramiento
Estas etapas se cubren paralelamente en este tutorial de algoritmo Greedy, en el curso de la división de la matriz.
Para comprender el enfoque codicioso, deberá tener un conocimiento práctico de la recursividad y el cambio de contexto. Esto le ayuda a comprender cómo rastrear el código. Puede definir el paradigma codicioso en términos de sus propias declaraciones necesarias y suficientes.
Dos condiciones definen el paradigma codicioso.
- Cada solución paso a paso debe estructurar un problema hacia su solución mejor aceptada.
- Es suficiente si la estructuración del problema puede detenerse en un número finito de pasos codiciosos.
Con la teorización continuada, describamos la historia asociada con el enfoque de búsqueda codiciosa.
En este tutorial de algoritmo codicioso, aprenderá:
- Historia de los algoritmos codiciosos
- Estrategias y decisiones codiciosas
- Características del enfoque codicioso
- ¿Por qué utilizar el enfoque codicioso?
- Cómo resolver el problema de selección de actividades
- Arquitectura del enfoque codicioso
- Desventajas de los algoritmos codiciosos
Historia de los algoritmos codiciosos
Aquí hay un hito importante de algoritmos codiciosos:
- Los algoritmos codiciosos se conceptualizaron para muchos algoritmos de recorrido de gráficos en la década de 1950.
- Esdger Djikstra conceptualizó el algoritmo para generar árboles de expansión mínimos. Su objetivo era acortar el tramo de rutas dentro de la capital holandesa, Ámsterdam.
- En la misma década, Prim y Kruskal lograron estrategias de optimización que se basaban en minimizar los costos de ruta a lo largo de rutas pesadas.
- En los años 70, los investigadores estadounidenses Cormen, Rivest y Stein propusieron una subestructuración recursiva de soluciones codiciosas en su libro clásico de introducción a los algoritmos.
- El paradigma de búsqueda codicioso se registró como un tipo diferente de estrategia de optimización en los registros del NIST en 2005.
- Hasta la fecha, los protocolos que ejecutan la web, como Open-Shortest-Path-First (OSPF) y muchos otros protocolos de conmutación de paquetes de red utilizan la estrategia codiciosa para minimizar el tiempo dedicado a una red.
Estrategias y decisiones codiciosas
La lógica en su forma más sencilla se redujo a "codiciosos" o "no codiciosos". Estas declaraciones fueron definidas por el enfoque adoptado para avanzar en cada etapa del algoritmo.
Por ejemplo, el algoritmo de Djikstra utilizó una estrategia codiciosa paso a paso para identificar hosts en Internet mediante el cálculo de una función de costo. El valor devuelto por la función de costo determina si la siguiente ruta es "codiciosa" o "no codiciosa".
En resumen, un algoritmo deja de ser codicioso si en cualquier etapa da un paso que no sea codicioso localmente. Los problemas codiciosos se detienen sin más alcance de codicia.
Características del enfoque codicioso
Las características importantes de un algoritmo de método Greedy son:
- Existe una lista ordenada de recursos, con costos o atribuciones de valor. Estos cuantifican las limitaciones de un sistema.
- Utilizará la cantidad máxima de recursos en el tiempo que se aplique una restricción.
- Por ejemplo, en un problema de programación de actividades, los costos de los recursos están en horas y las actividades deben realizarse en orden de serie.
¿Por qué utilizar el enfoque codicioso?
Estas son las razones para utilizar el enfoque codicioso:
- El enfoque codicioso tiene algunas ventajas y desventajas, que pueden hacer que sea adecuado para la optimización.
- Una razón importante es lograr la solución más factible de inmediato. En el problema de selección de actividades (explicado a continuación), si se pueden realizar más actividades antes de finalizar la actividad actual, estas actividades se pueden realizar dentro del mismo tiempo.
- Otra razón es dividir un problema de forma recursiva en función de una condición, sin necesidad de combinar todas las soluciones.
- En el problema de selección de actividades, el paso de "división recursiva" se logra escaneando una lista de elementos solo una vez y considerando ciertas actividades.
Cómo resolver el problema de selección de actividades
En el ejemplo de programación de actividades, hay una hora de "inicio" y "finalización" para cada actividad. Cada actividad está indexada por un número como referencia. Hay dos categorías de actividades.
- actividad considerada : es la Actividad, que es la referencia a partir de la cual se analiza la capacidad para realizar más de una Actividad restante.
- actividades restantes: actividades en uno o más índices por delante de la actividad considerada.
La duración total da el costo de realizar la actividad. Es decir, (terminar - comenzar) nos da la duración como el costo de una actividad.
Aprenderá que la extensión codiciosa es la cantidad de actividades restantes que puede realizar en el tiempo de una actividad considerada.
Arquitectura del enfoque codicioso
PASO 1)
Escanee la lista de costos de actividad, comenzando con el índice 0 como índice considerado.
PASO 2)
Cuando se puedan terminar más actividades para cuando finalice la actividad considerada, comience a buscar una o más actividades restantes.
PASO 3)
Si no hay más actividades restantes, la actividad restante actual se convierte en la siguiente actividad considerada. Repita el paso 1 y el paso 2, con la nueva actividad considerada. Si no quedan actividades restantes, vaya al paso 4.
PASO 4 )
Devuelve la unión de índices considerados. Estos son los índices de actividad que se utilizarán para maximizar el rendimiento.
Explicación del código
#include#include #include #define MAX_ACTIVITIES 12
Explicación del código:
- Archivos / clases de encabezado incluidos
- Un número máximo de actividades proporcionadas por el usuario.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};
Explicación del código:
- El espacio de nombres para las operaciones de transmisión.
- Una definición de clase para TIME
- Una marca de tiempo de una hora.
- Un constructor predeterminado de TIME
- La variable de horas.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};
Explicación del código:
- Una definición de clase de la actividad.
- Marcas de tiempo que definen una duración
- Todas las marcas de tiempo se inicializan en 0 en el constructor predeterminado
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;
Explicación del código:
- Parte 1 de la definición de la clase del planificador.
- Considered Index es el punto de partida para escanear la matriz.
- El índice de inicialización se utiliza para asignar marcas de tiempo aleatorias.
- Una matriz de objetos de actividad se asigna dinámicamente utilizando el nuevo operador.
- El puntero programado define la ubicación base actual para la codicia.
Scheduler(){considered_index = 0;scheduled = NULL;… …
Explicación del código:
- El constructor del planificador: parte 2 de la definición de la clase del planificador.
- El índice considerado define el inicio actual del análisis actual.
- El alcance de la codicia actual no está definido al principio.
for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++){current_activities[init_index].start.hours =rand() % 12;current_activities[init_index].finish.hours =current_activities[init_index].start.hours +(rand() % 2);printf("\nSTART:%d END %d\n",current_activities[init_index].start.hours,current_activities[init_index].finish.hours);}… …
Explicación del código:
- Un bucle for para inicializar las horas de inicio y finalización de cada una de las actividades programadas actualmente.
- Inicialización de la hora de inicio.
- Inicialización de la hora de finalización siempre después o exactamente a la hora de inicio.
- Una declaración de depuración para imprimir las duraciones asignadas.
public:Activity * activity_select(int);};
Explicación del código:
- Parte 4: la última parte de la definición de la clase del planificador.
- La función de selección de actividad toma un índice de punto de partida como base y divide la búsqueda codiciosa en subproblemas codiciosos.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …
- Utilizando el operador de resolución de alcance (: :), se proporciona la definición de la función.
- El índice considerado es el índice llamado por valor. El greedy_extent es el inicializado solo un índice después del índice considerado.
Activity * Scheduler :: activity_select(int considered_index){while( (greedy_extent < MAX_ACTIVITIES ) &&((this->current_activities[greedy_extent]).start.hours <(this->current_activities[considered_index]).finish.hours )){printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",(this->current_activities[greedy_extent]).start.hours,(this->current_activities[greedy_extent]).finish.hours,greedy_extent + 1);greedy_extent++;}… …
Explicación del código:
- La lógica central: el alcance de la codicia se limita al número de actividades.
- Las horas de inicio de la Actividad actual se verifican como programables antes de que finalice la Actividad considerada (dada por el índice considerado).
- Siempre que sea posible, se imprime una declaración de depuración opcional.
- Avanzar al siguiente índice en la matriz de actividades
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}
Explicación del código:
- El condicional comprueba si se han cubierto todas las actividades.
- De lo contrario, puede reiniciar su codicioso con el índice considerado como el punto actual. Este es un paso recursivo que divide con avidez el enunciado del problema.
- Si es así, vuelve a la persona que llama sin posibilidad de extender la codicia.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}
Explicación del código:
- La función principal utilizada para invocar el planificador.
- Se crea una instancia de un nuevo Programador.
- La función de selección de actividad, que devuelve un puntero de tipo actividad, vuelve a la persona que llama después de que finaliza la búsqueda codiciosa.
Producción:
START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5
Desventajas de los algoritmos codiciosos
No es adecuado para problemas codiciosos donde se requiere una solución para cada subproblema como la clasificación.
En tales problemas de práctica del algoritmo Greedy, el método Greedy puede estar equivocado; en el peor de los casos, incluso conducir a una solución no óptima.
Por lo tanto, la desventaja de los algoritmos codiciosos es no saber qué hay delante del estado codicioso actual.
A continuación se muestra una descripción de la desventaja del método Greedy:
En el escaneo codicioso que se muestra aquí como un árbol (mayor valor mayor codicia), es probable que un estado de algoritmo en el valor: 40 tome 29 como el siguiente valor. Además, su misión termina en 12. Esto equivale a un valor de 41.
Sin embargo, si el algoritmo tomó un camino subóptimo o adoptó una estrategia de conquista. luego 25 irían seguidos de 40, y la mejora general del costo sería 65, que se valora 24 puntos más como una decisión subóptima.
Ejemplos de algoritmos codiciosos
La mayoría de los algoritmos de redes utilizan el enfoque codicioso. Aquí hay una lista de algunos ejemplos de algoritmos Greedy:
- Algoritmo de árbol de expansión mínimo de Prim
- Problema del vendedor ambulante
- Gráfico - Colorear Mapa
- Algoritmo de árbol de expansión mínimo de Kruskal
- Algoritmo de árbol de expansión mínimo de Dijkstra
- Gráfico - Cubierta de vértice
- Problema de la mochila
- Problema de programación de trabajos
Resumen:
Para resumir, el artículo definió el paradigma codicioso, mostró cómo la optimización codiciosa y la recursividad pueden ayudarlo a obtener la mejor solución hasta cierto punto. El algoritmo Greedy se utiliza ampliamente para la resolución de problemas en muchos lenguajes como el algoritmo Greedy Python, C, C #, PHP, Java, etc. La selección de actividad del ejemplo del algoritmo Greedy se describió como un problema estratégico que podría lograr el máximo rendimiento utilizando el algoritmo greedy. Acercarse. Al final, se explicaron los deméritos del uso del enfoque codicioso.
