Scribd
Cargar
44 vistas2 páginas

Algoritmos de Optimización y Búsqueda

El documento presenta varios algoritmos de optimización y búsqueda, incluyendo Voraz, Vuelta Atrás, Divide y Vencerás, Ramificación y Poda, Programación Dinámica, Prim, Dijkstra y Kruskal. Cada algoritmo se describe con su función y lógica de operación, abordando problemas como la selección de candidatos, la mochila, y la construcción de árboles de expansión mínima. Se destacan las estrategias y estructuras de datos utilizadas en cada enfoque para resolver problemas computacionales.

Cargado por

Arturo Barba
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
44 vistas2 páginas

Algoritmos de Optimización y Búsqueda

El documento presenta varios algoritmos de optimización y búsqueda, incluyendo Voraz, Vuelta Atrás, Divide y Vencerás, Ramificación y Poda, Programación Dinámica, Prim, Dijkstra y Kruskal. Cada algoritmo se describe con su función y lógica de operación, abordando problemas como la selección de candidatos, la mochila, y la construcción de árboles de expansión mínima. Se destacan las estrategias y estructuras de datos utilizadas en cada enfoque para resolver problemas computacionales.

Cargado por

Arturo Barba
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

VORAZ: VUELTA ATRÁS:

fun Voraz (c:conjuntoCandidatos):conjuntoCandidatos fun VueltaAtras (v: Secuencia, k: entero)


sol ← 0 {v es una secuencia k-prometedora}
mientras c ≠ 0 ˄ ¬ solucion (sol) hacer IniciarExploraciónNivel (k)
x ← seleccionar (c) mientras OperacionesPendientes (k) hacer
c ← c / {x} extender v con siguiente opción
si factible (sol U {x}) entonces si SoluciónCompleta (v) entonces
sol ← sol U {x} ProcesarSolución (v)
fsi sino
fmientras si Completable (v) entonces
si solucion (sol) entonces devolver sol VueltaAtras (v, k+1)
sino imprimir ("No hay solución") fsi
fsi fsi
ffun fmientras
ffun
DIVIDE Y VENCERÁS:
RAMIFICACIÓN Y PODA:
fun DyV (problema)
si trivial (problema) entonces fun RyP (nodoRaiz, mejorSolución: TNodo, cota: real)
devolver solución-trivial monticulo ← CrearMontículoVacío ()
sino hacer cota ← EstimaciónPes (nodoRaiz)
{p1, p2,... pk} ← descomponer (problema) Insertar (nodoRaiz, monticulo)
para i ϵ (1...k) hacer mientras ¬ MonticuloVacio? (monticulo) ˄
si ← DyV (pi) EstimaciónOpt (Primero (monticulo)) ≤ cota hacer
fpara nodo ← ObtenerCima (monticulo)
fsi para cada hijo extensión valida de nodo hacer
combinar (s1, s2,... sk) si solución (hijo) entonces
ffun si coste (hijo) ≤ cota entonces
cota ← coste (hijo)
PROGRAMACIÓN DINÁMICA (MOCHILA): mejorSolucion ← hijo
fun ObjetosMochila (vol: vector, M: Tabla, n: entero, V: entero, objetos: vector) fsi
var sino
i, W: entero si EstimaciónOpt (hijo) ≤ cota entonces
fvar Insertar (hijo, monticulo)
W←V si EstimaciónPes (hijo) < cota entonces
para i ← n hasta 1 incremento -1 hacer cota ← EstimaciónPes (hijo)
si M[i, W] = M[i-1, W] entonces fsi
objetos[i] ← 0 fsi
sino fsi
objetos[i] ← 1 fpara
W ← W - vol[i] fmientras
fsi ffun
fpara
ffun
PRIM: DIJKSTRA:

fun Prim (G = <N, A>: grafo): conjunto de aristas tipo VectorNat = matriz [0...n] de natural
AR ← 0 fun Dijkstra (G = <N, A>: grafo): VectorNat, VectorNat
NA ← {un nodo cualquiera de N} var
mientras NA ≠ N hacer especial, predecesor: VectorNat
Buscar {u, v} de coste mínimo tal que u ϵ NA y v ϵ N/NA C: conjunto de nodos
AR ← AR U {(u, v)} fvar
NA ← NA U {v} C = {2, 3, … n}
fmientras para i ← 2 hasta n hacer
dev AR especial[i] ← Distancia (1, i)
ffun predecesor[i] ← 1
fpara
KRUSKAL: mientras C contenga más de 1 nodo hacer
v ← nodo ϵ C que minimiza espcial[v]
fun Kruskal (G = <N, A>: grafo): conjunto de aristas C ← C/{v}
var para cada w ϵ C hacer
AR: conjunto de aristas si especial[w] > especial[v] + distancia (v, w) entonces
fvar especial[w] ← especial[v] + distancia (v, w)
Ordenar (A) {Ordena A en pesos crecientes} predecesor[v]
n ← nº de nodos de N fsi
AR ← 0 fpara
Iniciar n conjuntos, uno con cada nodo de N fmientras
mientras AR no tenga n-1 aristas hacer dev especial[], predecesor[]
seleccionar {u,v} mínima ffun
comU ← buscarComponenteConexa (u)
comV ← buscarComponenteConexa (v)
si comU ≠ comV entonces
fusionar (comU, comV)
AR ← AR U {(u, v)}
fsi
fmientras
dev AR
ffun

También podría gustarte