¿Cómo detectar un algoritmo "codicioso"?

Question

Estoy leyendo un tutorial acerca de los algoritmos "codiciosos", pero me cuesta mucho encontrarlos para resolver problemas reales de "Top Coder".

Si yo sé que un determinado problema puede resolverse con un algoritmo de "codiciosos" que es bastante fácil de codificar la solución. Sin embargo, si no me dicen que este problema es "codicioso", no lo veo.

¿Cuáles son las propiedades y patrones comunes de los problemas resueltos con algoritmos "codiciosos"? ¿Puedo reducirlos a uno de los problemas conocidos como "codiciosos" (por ejemplo, MST)?

Answer 1

Formalmente, tendría que probar la propiedad matroid por supuesto. Sin embargo, supongo que, en términos de topcoder, desea saber rápidamente si un problema se puede abordar con avidez o no.

En ese caso, el punto más importante es el optimal sub-structure property. Para esto, debe ser capaz de detectar que el problema se puede descomponer en subproblemas y que su solución óptima es parte de la solución óptima de todo el problema.

Por supuesto, los problemas de codicia vienen en una variedad tan amplia que es casi imposible ofrecer una respuesta correcta general a su pregunta. Mi mejor consejo sería, por tanto, ser pensar en algún lugar a lo largo de estas líneas:

• ¿Tengo que elegir entre diferentes alternativas en algún momento?
• ¿Esta elección da como resultado sub-problemas que se pueden resolver individualmente?
• ¿Podré utilizar la solución del sub-problema para obtener una solución para el problema general?

Junto con mucha y mucha experiencia (solo tenía que decir eso, también) esto debería ayudarlo a detectar rápidamente problemas ambiciosos. Por supuesto, eventualmente puede clasificar un problema como codicioso, que no lo es. En ese caso, solo puede esperar darse cuenta antes de trabajar en el código por mucho tiempo.

(Una vez más, como referencia, que asumen un contexto TopCoder .. nada más realista y de consecuencia práctica yo recomiendo para verificar realmente la estructura matroide antes de seleccionar un algoritmo voraz.)

Answer 2

Una parte de su problema puede ser causado por pensar en "problemas codiciosos". Hay algoritmos codiciosos y problemas donde hay un algoritmo codicioso, que conduce a una solución óptima. Hay otros problemas difíciles que también pueden resolverse mediante algoritmos codiciosos, pero el resultado no será necesariamente óptimo.

Por ejemplo, para el problema del empaquetamiento de bandejas, existen varios algoritmos codiciosos, todos ellos con mucha más complejidad que el algoritmo exponencial, pero solo puede estar seguro de que obtendrá una solución por debajo de un cierto umbral comparado a la solución óptima.

Solo con respecto a los problemas donde los algoritmos codiciosos darán lugar a una solución óptima, supongo que una prueba de corrección inductiva se siente totalmente natural y fácil. Por cada uno de sus pasos codiciosos, está bastante claro que esto fue lo mejor que se puede hacer.

Normalmente, los problemas con soluciones óptimas y codiciosas son fáciles de todos modos, y otros te obligarán a elaborar una heurística codiciosa, debido a limitaciones de complejidad. Por lo general, una reducción significativa mostraría que su problema es, al menos, NP-difícil y, por lo tanto, usted sabe que tendrá que encontrar una heurística. Para esos problemas, soy un gran fan de probar.Implemente su algoritmo e intente descubrir si las soluciones son "bastante buenas" (ideal si también tiene un algoritmo lento pero correcto con el que puede comparar los resultados, de lo contrario podría necesitar verdades terrestres creadas manualmente). Solo si tiene algo que funciona bien, trate de pensar por qué y tal vez incluso trate de encontrar pruebas de los límites. Quizás funcione, quizás descubras casos fronterizos en los que no funciona y necesita un refinamiento.

Answer 3

"Término utilizado para describir una familia de algoritmos. La mayoría de los algoritmos intentan alcanzar una configuración" buena "a partir de alguna configuración inicial, haciendo solo movimientos legales. A menudo hay alguna medida de" bondad "de la solución (suponiendo que se encuentra). El algoritmo codicioso siempre intenta realizar el mejor movimiento legal posible. Tenga en cuenta que este criterio es local: el algoritmo codicioso no "piensa en el futuro", acordando realizar ahora un movimiento de aspecto mediocre, lo que permitirá mejores movimientos posteriores.

Por ejemplo, el algoritmo codicioso para las fracciones egipcias está tratando de encontrar una representación con denominadores pequeños. En lugar de buscar una representación donde el último denominador sea pequeño, se necesita en cada paso la guarida legal más pequeña ominator En general, esto lleva a denominadores muy grandes en pasos posteriores.

La principal ventaja del algoritmo codicioso suele ser la simplicidad del análisis. Por lo general, también es muy fácil de programar. Desafortunadamente, a menudo es subóptimo. " --- ariels (http://www.everything2.com/title/greedy+algorithm?searchy=search)