Resolución de Problemas con Algoritmos Eficientes: Ejemplos Prácticos

Algoritmo ParticiónMitad

Dado un conjunto de n enteros, se desea encontrar, si existe, una partición en dos subconjuntos disjuntos, tal que la suma de sus elementos sea la misma.

Entrada:

• S: Vector
• E: entero
• v: Vector

Código:

para i = 1 hasta 2
  S[E] ← i
  si E = longitud(v) − 1 entonces
    suma1 ← 0
    suma2 ← 0
    para j = 0 hasta longitud(v) − 1
      si S[j] = 1 entonces
        suma1 ← suma1 + v[j]
      sino
        suma2 ← suma2 + v[j]
      fin si
    fin para
    si suma1 = suma2 entonces
      Mostrar(S)
    fin si
  sino
    ParticionMitad(v, S, E + 1)
  fin si
fin para

Algoritmo Cambio

Entrada:

• S: Vector
• Sv: entero
• M: Vector
• Mc: entero
• E: etapa
• v: Vector
• C: entero

Código:

para i = 0 hasta longitud(v) − 1
  S[E] ← v[i]
  Sv ← Sv + v[i]
  si Sv = C entonces
    si NO Mc O E < longitud(M) entonces
      Mc ← E + 1
      copiarVector(S, M)
    fin si
  sino
    si Sv < C entonces
      Mc = Cambio(S, Sv, M, Mc, E + 1, v, C)
    fin si
  fin si
  Sv ← Sv − v[i]
fin para
de졔volver Mc

Algoritmo CaminoMenosEscalas

Dado un sistema de rutas aéreas modelado mediante un grafo, determine la ruta que contenga la mínima cantidad de escalas entre un par de ciudades dadas.

Entrada:

• G: grafo
• o: origen
• d: destino
• mejorCamino: Vector
• longitudMejor: entero
• actualCamino: Vector
• etapa: entero

Salida:

• escalas: cantidad de escalas de la mejor solución encontrada

Código:

actualCamino[etapa] ← o
etapa ← etapa + 1
si o = d entonces
  si longitudMejor = −1 O etapa < longitud(mejorCamino) entonces
    mejorCamino ← actualCamino
    devolver etapa
  sino
    devolver longitudMejor
  fin si
sino
  adyacentes ← adyacentes(G, o)
  para cada o ∈ adyacentes
    si NO pertenece(actualCamino, o) entonces
      longitudMejor ← CaminoMenosEscalas(G, o, d, mejorCamino, longitudMejor, actualCamino, etapa)
    fin si
  fin para
  devolver longitudMejor
fin si

Algoritmo Mochila

Entrada:

• Objetos: Vector
• capacidad: entero
• mejorSolucion: Vector
• valorMejorSolucion: entero
• solucionActual: Vector
• valorSolucionActual: entero
• pesoSolucionActual: entero
• etapa: entero

Salida:

• entero

Código:

para i = 0 hasta 1
  solucionActual[etapa] ← i
  pesoSolucionActual ← pesoSolucionActual + i * Objetos[etapa].peso
  valorSolucionActual ← valorSolucionActual + i * Objetos[etapa].valor
  si pesoSolucionActual ≤ capacidad entonces
    si etapa = longitud(Objetos) − 1 entonces
      si valorMejorSolucion = −1 O valorMejorSolucion < valorSolucionActual entonces
        mejorSolucion ← solucionActual
        valorMejorSolucion ← valorSolucionActual
      fin si
    sino
      si etapa < longitud(Objetos) − 1 entonces
        valorMejorSolucion ← Mochila(Objetos, capacidad, mejorSolucion, valorMejorSolucion, solucionActual, valorSolucionActual, pesoSolucionActual, etapa + 1)
      fin si
    fin si
  fin si
fin para
de졔volver valorMejorSolucion

Algoritmo ProcesadoresTareas

Entrada:

• m: entero (número de procesadores)
• tareas: Vector
• solucionParcial: Vector
• mejorSolucion: Vector
• valorMejorSolucion: entero
• etapa: entero

Salida:

• valorMejorSolucion: entero

Código:

para i = 1 hasta m
  solucionParcial[etapa] ← i
  si etapa + 1 = longitud(tareas) entonces
    valorSolucionParcial ← sumaTareas(m, tareas, solucionParcial)
    si valorMejorSolucion = −1 O valorSolucionParcial < valorMejorSolucion entonces
      mejorSolucion ← solucionParcial
      valorMejorSolucion ← valorSolucionParcial
    fin si
  sino
    valorMejorSolucion ← Tareas(m, tareas, solucionParcial, mejorSolucion, valorMejorSolucion, etapa + 1)
  fin si
fin para
de졔volver valorMejorSolucion

Algoritmo sumaTareas

Entrada:

• m: entero (número de procesadores)
• tareas: Vector
• solucionParcial: Vector

Salida:

• maximoTiempo: entero

Código:

procesadores ← inicializarVector(m)
para i = 0 hasta longitud(tareas) - 1
  procesadores[solucionParcial[i]] ← procesadores[solucionParcial[i]] + tareas[i]
fin para
maximoTiempo ← −1
para i = 0 hasta m - 1
  si procesadores[i] > maximoTiempo entonces
    maximoTiempo ← procesadores[i]
  fin si
fin para
de졔volver maximoTiempo

Algoritmo Hamiltoniano

(Punto de partida y final en el mismo nodo)

Entrada:

• G: Grafo
• solucionParcial: Vector
• etapa: entero

Código:

para cada v ∈ adyacentes(G, solucionParcial[etapa − 1])
  si NO pertenece(v, solucionParcial) entonces
    solucionParcial[etapa] ← v
    si etapa < longitud(solucionParcial) -1 entonces
      Hamiltoniano(G, solucionParcial, etapa + 1)
    sino
      si existeArista(G, solucionParcial[etapa], solucionParcial[0]) entonces
        mostrar(solucionParcial)
      fin si
    fin si
  fin si
fin para