Algoritmos voraz - Historial de revisiones

Carlos idict: Texto reemplazado: «
» por «»

2019-07-15T08:00:34Z

Texto reemplazado: «<div align="justify">» por «»

Arletisjcconsolacion: /* Fuente */

2012-11-06T14:11:01Z

‎Fuente

PuertoPadre5 jc: /* Ejemplos de algoritmos voraces */

2011-04-11T16:59:02Z

‎Ejemplos de algoritmos voraces

PuertoPadre5 jc en 14:25 26 mar 2011

2011-03-26T14:25:55Z

PuertoPadre5 jc en 13:52 26 mar 2011

2011-03-26T13:52:31Z

Jose02051jc: /* Esquema */

2011-03-17T20:38:14Z

‎Esquema

Humberto0601ad jc en 23:33 21 ene 2011

2011-01-21T23:33:54Z

Year bot: Removida de referencia

2010-04-03T04:12:22Z

Removida de referencia

Kenia idict: Algoritmos voraces trasladada a Algoritmos voraz

2010-04-02T20:14:59Z

Algoritmos voraces trasladada a Algoritmos voraz

Asanto uci: Página creada con '{{Referencia}}Algoritmo voraz Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurís…'

2010-04-02T15:33:23Z

Página creada con '{{Referencia}}Algoritmo voraz Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurís…'

Página nueva

{{Referencia}}Algoritmo voraz

Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.

 

== Esquema ==

Dado un conjunto finito de entradas C, un algoritmo voraz devuelve un conjunto S (seleccionados) tal que y que además cumple con las restricciones del problema inicial. Cada conjunto S que satisfaga las restricciones se le suele denominar prometedor, y si éste además logra que la función objetivo se minimice o maximice (según corresponda) diremos que S es una ''solución óptima''.

=== Elementos de los que consta la técnica ===

*El conjunto C de '''candidatos''', entradas del problema.
*Función '''solución'''. Comprueba, en cada paso, si el subconjunto actual de candidatos elegidos forma una solución (no importa si es óptima o no lo es).
*Función de '''selección'''. Informa de cuál es el elemento más prometedor para completar la solución. Éste no puede haber sido rechazado o escogido con anterioridad. Cada elemento es considerado una sola vez. Luego, puede ser rechazado o aceptado y pertenecerá a .
*Función de '''factibilidad'''. Informa si a partir de un conjunto se puede llegar a una solución. Lo aplicaremos al conjunto de seleccionados unido con el elemento más prometedor.
*Función '''objetivo'''. Es aquella que queremos maximizar o minimizar, el núcleo del problema.

=== Funcionamiento ===

El algoritmo escoge en cada paso al mejor elemento posible, conocido como el '''elemento más prometedor'''. Se elimina ese elemento del conjunto de candidatos ( ) y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados ( ) produce una solución factible.

En caso de que así sea, se incluye ese elemento en S. Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.

Una vez finalizado el bucle, el algoritmo comprueba si el conjunto S es una solución o no, devolviendo el resultado apropiado en cada caso. El algoritmo se muestra a continuación:

// Esquema general de un algoritmo voraz

'''función'''
// C es el conjunto de candidatos//

'''mientras y no solución(S) hacer'''

'''si entonces'''

'''si solución(S) entonces'''
'''devolver ''' //S es una solución//
'''si no'''
'''devolver ''' //No hay soluciones//

 

== Ejemplos de algoritmos voraces ==

*[[Algoritmo de Kruskal]]
*[[Algoritmo de Prim]]
*[[Algoritmo de Dijkstra]]
*[[Algoritmo para la ubicación óptima]]

 

== Temas relacionados ==

*[[Algoritmo]]
*[[Algoritmo heurístico]]

 

== Referencias ==

*Brassard, Gilles; Bratley, Paul (1997). «Algoritmos voraces», Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84-89660-00-X. 

== Fuente ==

*Wikipedia, enciclopedia libre 

[[Category:Algoritmos|Category: Algoritmos]]

@@ Línea 1: / Línea 1: @@
-<div align="justify">
 {{Definición
 |nombre= Algoritmo voraz.
 |imagen=
 |tamaño=
-|concepto=<div align="justify">Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. </div>  }}
+|concepto=Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. </div>  }}
 '''Algoritmo voraz'''. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.

@@ Línea 64: / Línea 64: @@
 == Fuente  ==
 * [http://es.wikipedia.org| Wikipedia, Enciclopedia Libre]. <br>
 [[Category:Algoritmos]]

@@ Línea 44: / Línea 44: @@
 == Ejemplos de algoritmos voraces  ==
-* [http://Algoritmo de Kruskal]
+* [http://Algoritmo de Kruskal].
-* [http://Algoritmo de Prim ]
+* [http://Algoritmo de Prim Algoritmo de Prim].
-* [http://Algoritmo de Dijkstra]
+* [http://Algoritmo de Dijkstra].
-* [http://algoritmo para la Ubicación Óptima]
+* [http://Algoritmo para la Ubicación Óptima].
 <br>
 == Temas relacionados  ==

@@ Línea 44: / Línea 44: @@
 == Ejemplos de algoritmos voraces  ==
-* [http://algoritmo de kruskal |Algoritmo de Kruskal]
+* [http://Algoritmo de Kruskal]
-*[http://algoritmo de prim |Algoritmo de Prim ]
+* [http://Algoritmo de Prim ]
-*[http://algoritmo de dijkstra |Algoritmo de Dijkstra]
+* [http://Algoritmo de Dijkstra]
-*[http://algoritmo para la ubicación óptima |Algoritmo para la Ubicación Óptima]
+* [http://algoritmo para la Ubicación Óptima]
 <br>
@@ Línea 53: / Línea 53: @@
 == Temas relacionados  ==
-*[http://algoritmo| Algoritmo]
+*[[Algoritmo]]
-*[http://algoritmo heurístico|Algoritmo Heurístico]
+*[http://Algoritmo Heurístico]
 <br>

@@ Línea 1: / Línea 1: @@
-{{Referencia}}Algoritmo voraz
+'''Algoritmo voraz'''
 Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.
@@ Línea 67: / Línea 67: @@
-[[Category:Algoritmos|Category: Algoritmos]]
+[[Category:Algoritmos]]

@@ Línea 1: / Línea 1: @@
-'''Algoritmo voraz'''
+<div align="justify">
-Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.
+'''Algoritmo voraz'''. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.
 <br>
@@ Línea 19: / Línea 24: @@
 === Funcionamiento  ===
-El [[algoritmo]] escoge en cada paso al mejor elemento posible, conocido como el '''elemento más prometedor'''. Se elimina ese elemento del conjunto de candidatos ( ) y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados ( ) produce una solución factible.
+El [[Algoritmo]] escoge en cada paso al mejor elemento posible, conocido como el '''elemento más prometedor'''. Se elimina ese elemento del conjunto de candidatos ( ) y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados ( ) produce una solución factible.
 En caso de que así sea, se incluye ese elemento en S. Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.
@@ Línea 25: / Línea 30: @@
 Una vez finalizado el bucle, el algoritmo comprueba si el conjunto S es una solución o no, devolviendo el resultado apropiado en cada caso. El algoritmo se muestra a continuación:
-   // Esquema general de un [[algoritmo]] voraz
+   // Esquema general de un [[Algoritmo]] voraz
+    '''función'''
     // C es el conjunto de candidatos//
+       '''mientras  y no solución(S) hacer'''
-   '''mientras  y no solución(S) hacer'''
+             '''si  entonces'''
+        '''si solución(S) entonces'''
-     '''si  entonces'''
+    '''devolver ''' //S es una solución//
      '''si no'''
-     '''devolver ''' //No hay soluciones//
+    '''devolver ''' //No hay soluciones//
 <br>
 == Ejemplos de algoritmos voraces  ==
-*[[Algoritmo de Kruskal]]
+* [http://algoritmo de kruskal |Algoritmo de Kruskal]
-*[[Algoritmo de Prim]]
+*[http://algoritmo de prim |Algoritmo de Prim ]
-*[[Algoritmo de Dijkstra]]
+*[http://algoritmo de dijkstra |Algoritmo de Dijkstra]
-*[[Algoritmo para la ubicación óptima]]
+*[http://algoritmo para la ubicación óptima |Algoritmo para la Ubicación Óptima]
 <br>
@@ Línea 52: / Línea 53: @@
 == Temas relacionados  ==
-*[[Algoritmo]]
+*[http://algoritmo| Algoritmo]
-*[[Algoritmo heurístico]]
+*[http://algoritmo heurístico|Algoritmo Heurístico]
 <br>
@@ Línea 61: / Línea 62: @@
 *Brassard, Gilles; Bratley, Paul (1997). «Algoritmos voraces», Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84–89660–00–X.<br>
-== Fuente ==
+== Fuente  ==
+* [http://es.wikipedia.org| Wikipedia, Enciclopedia Libre]. <br>
-*Wikipedia, enciclopedia libre<br>
+* MsC José Ramón Ávila Cruz. [[Joven Club Puerto Padre V|Joven Club Puerto Padre V]]. 2011
 [[Category:Algoritmos]]

@@ Línea 7: / Línea 7: @@
 == Esquema  ==
-Dado un conjunto finito de entradas C, un algoritmo voraz devuelve un conjunto S (seleccionados) tal que y que además cumple con las restricciones del problema inicial. Cada conjunto S que satisfaga las restricciones se le suele denominar prometedor, y si éste además logra que la función objetivo se minimice o maximice (según corresponda) diremos que S es una ''solución óptima''.
+Dado un conjunto finito de entradas C, un [[algoritmo]] voraz devuelve un conjunto S (seleccionados) tal que y que además cumple con las restricciones del problema inicial. Cada conjunto S que satisfaga las restricciones se le suele denominar prometedor, y si éste además logra que la función objetivo se minimice o maximice (según corresponda) diremos que S es una ''solución óptima''.
 === Elementos de los que consta la técnica  ===
@@ Línea 19: / Línea 19: @@
 === Funcionamiento  ===
-El algoritmo escoge en cada paso al mejor elemento posible, conocido como el '''elemento más prometedor'''. Se elimina ese elemento del conjunto de candidatos ( ) y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados ( ) produce una solución factible.
+El [[algoritmo]] escoge en cada paso al mejor elemento posible, conocido como el '''elemento más prometedor'''. Se elimina ese elemento del conjunto de candidatos ( ) y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados ( ) produce una solución factible.
 En caso de que así sea, se incluye ese elemento en S. Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.
@@ Línea 25: / Línea 25: @@
 Una vez finalizado el bucle, el algoritmo comprueba si el conjunto S es una solución o no, devolviendo el resultado apropiado en cada caso. El algoritmo se muestra a continuación:
-   // Esquema general de un algoritmo voraz
+   // Esquema general de un [[algoritmo]] voraz
    '''función'''
@@ Línea 39: / Línea 39: @@
       '''devolver ''' //No hay soluciones//
 <br>
 == Ejemplos de algoritmos voraces  ==

@@ Línea 59: / Línea 59: @@
 == Referencias  ==
-*Brassard, Gilles; Bratley, Paul (1997). «Algoritmos voraces», Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84-89660-00-X.<br>
+*Brassard, Gilles; Bratley, Paul (1997). «Algoritmos voraces», Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84–89660–00–X.<br>
 == Fuente ==

← Revisión anterior	Revisión del 20:14 2 abr 2010
(Sin diferencias)