Estrategia codicioso a resolver los principales problemas del algoritmo

En este artículo, vamos a ver lo que algoritmo voraz es y la forma en que se puede utilizar para resolver los principales problemas de entrevistas basadas en algoritmos ?

Introducción:

Vamos a empezar la discusión con un ejemplo que le ayudará a entender la técnica de codiciosos . If que pensar en jugar al ajedrez , cuando hacemos un movimiento que pensamos acerca de las consecuencias del movimiento en los estados futuros, pero en case de críquet de juego o el tenis, consideramos estados inmediatos en lugar teniendo en cuenta las consecuencias futuras . Esto significa, en algunos casos, toman decisiones que parece ser correcta en ese momento y, en algunos casos, tomar una decisión en base a las siguientes consecuencias o futuros casos.

La idea de lata local y global ocurren aquí. medios locales el case inmediata cuando los medios globales teniendo en cuenta la situación futura.

El técnica codiciosos se trata de hacer una decisión local, con base n que case inmediata, sobre basa en las consecuencias futuras y por eso la estrategia se conoce como codiciosos .

estrategia Greedy

medios de estrategia Greedy para tomar una decisión en cada paso sin tener en cuenta sus consecuencias en las etapas futuras. Encontramos el mejor movimiento local en cada paso para llegar a la meta. La estrategia codiciosa asume que un grupo de mejores decisiones locales puede conducir a optimización global .

algoritmo codicioso Lo que consiste en?

Las propiedades básicas de la estrategia codiciosa se pueden dividir en dos partes:

  1. Greedy propiedad elección
  2. óptima subestructura

propiedad elección Greedy se trata de hacer optimización local (codicioso). Las decisiones tomadas por los codiciosos pueden depender de los últimos movimientos, pero nunca en los pasos futuros. Iterativa, hacemos cada movimiento codiciosos para reducir el problema a un problema menor y, finalmente, para lograr la optimización global.

Optimal subestructura medios if podemos dividir el problema a otros sub-problemas y tienen soluciones óptimas para que, que se combinarán a una solución para resolver el problema entero grande.

¿Funciona siempre codiciosos?

Ni que decir tiene, hacer una mejor elección local no puede conducir a la mejor opción siempre mundial. Basta pensar en una colina y pensar while está subiendo para encontrar el pico máximo. Usted tomó una estrategia codiciosa y encontró un pico local que no es en absoluto global.

estrategia de esta manera codiciosa no funciona para todos para dar las mejores soluciones.

algoritmo codicioso de un vistazo

por qué utilizar algoritmo voraz?

  • Es sencillo, fácil de examinar y fácil de código.
  • Puesto que estamos haciendo movimientos locales, no hay necesidad de almacenar cualquier cálculo de volver a examinar.

Pero codiciosos tiene trampas

  • No tiene una solución a todos los problemas
  • En muchos casos codiciosos no puede llevar solución óptima
  • En algunos casos, se engaña a un mal solución

Sin embargo, debido a la estructura simple y el carácter estratégico codiciosos tiene una gran cantidad de aplicaciones. En los problemas de codificación de la entrevista también utilizamos la estrategia codiciosa a los problemas codiciosos conocidos. A continuación se presenta una lista de aplicaciones en las que codiciosos se puede utilizar:

  • Clasificación: clasificación topológica, pila de clasificación
  • cola de prioridad
  • codificación Huffman compresión
  • Prim y Kruskal del algoritmo
  • algoritmo de Dijkstra para encontrar el camino más corto en un grafo ponderado
  • Coin problema del cambio de
  • fraccional mochila problema
  • empleo problema de programación

también hay un uso especial de la técnica de codiciosos . Cuando tenemos que encontrar una solución aproximada de un problema complejo, codicioso puede ser una excelente opción.


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *