El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algoritmes d'Optimització Combinatòria

Següent ►
►

Introducció

L'optimització combinatòria és una branca de les matemàtiques i la informàtica que se centra en trobar la millor solució (o una solució òptima) entre un conjunt finit de possibles solucions. Aquest tipus de problemes són comuns en diverses àrees com la logística, la planificació, la bioinformàtica i molts altres camps.

Objectius del Mòdul

  1. Entendre els conceptes bàsics de l'optimització combinatòria.
  2. Aprendre diferents tècniques i algorismes per resoldre problemes d'optimització combinatòria.
  3. Aplicar aquests algorismes a problemes reals.

Conceptes Bàsics

Definicions Clau

  • Solució Feasible: Una solució que compleix totes les restriccions del problema.
  • Solució Òptima: La millor solució feasible segons una funció objectiu.
  • Funció Objectiu: Una funció que s'ha de maximitzar o minimitzar.

Exemples de Problemes d'Optimització Combinatòria

  • Problema del Viatjant de Comerç (TSP): Trobar el camí més curt que visita un conjunt de ciutats i torna a la ciutat d'origen.
  • Problema de la Motxilla: Seleccionar un subconjunt d'objectes amb un valor màxim sense excedir la capacitat de la motxilla.
  • Problema d'Assignació: Assignar tasques a treballadors de manera que es minimitzi el cost total.

Algorismes Clàssics

Algorisme de Ramificació i Acotació (Branch and Bound)

Aquest algorisme es basa en dividir el problema en subproblemes més petits (ramificació) i utilitzar límits per descartar subproblemes que no poden contenir la solució òptima (acotació).

Exemple: Problema de la Motxilla

def knapsack(capacity, weights, values, n):
    if n == 0 or capacity == 0:
        return 0
    if weights[n-1] > capacity:
        return knapsack(capacity, weights, values, n-1)
    else:
        return max(values[n-1] + knapsack(capacity-weights[n-1], weights, values, n-1),
                   knapsack(capacity, weights, values, n-1))

# Exemple d'ús
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
n = len(values)
print(knapsack(capacity, weights, values, n))  # Sortida: 220

Explicació del Codi

  • Funció knapsack: Aquesta funció recursiva calcula el valor màxim que es pot obtenir amb una capacitat donada.
  • Condicions Base: Si no hi ha més objectes o la capacitat és zero, el valor és zero.
  • Decisió: Si el pes de l'objecte actual és més gran que la capacitat, es descarta. En cas contrari, es considera tant incloure'l com no incloure'l, i es pren el màxim dels dos valors.

Algorisme de Programació Dinàmica

Aquest algorisme descompon el problema en subproblemes més petits i emmagatzema els resultats per evitar càlculs repetits.

Exemple: Problema de la Motxilla (Programació Dinàmica)

def knapsack_dp(capacity, weights, values, n):
    K = [[0 for x in range(capacity + 1)] for x in range(n + 1)]
    for i in range(n + 1):
        for w in range(capacity + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif weights[i-1] <= w:
                K[i][w] = max(values[i-1] + K[i-1][w-weights[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
    return K[n][capacity]

# Exemple d'ús
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
n = len(values)
print(knapsack_dp(capacity, weights, values, n))  # Sortida: 220

Explicació del Codi

  • Taula K: Una matriu bidimensional que emmagatzema els valors màxims per a cada subproblema.
  • Recorregut: Es recorre la matriu omplint cada cel·la amb el valor màxim possible segons les decisions preses (incloure o no incloure l'objecte).

Algorismes Heurístics

Algorisme Greedy

Aquest algorisme pren decisions locals òptimes amb l'esperança de trobar una solució global òptima.

Exemple: Problema de la Motxilla (Greedy)

def knapsack_greedy(capacity, weights, values):
    index = list(range(len(values)))
    ratio = [v/w for v, w in zip(values, weights)]
    index.sort(key=lambda i: ratio[i], reverse=True)
    
    max_value = 0
    for i in index:
        if weights[i] <= capacity:
            capacity -= weights[i]
            max_value += values[i]
        else:
            max_value += values[i] * (capacity / weights[i])
            break
    return max_value

# Exemple d'ús
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(knapsack_greedy(capacity, weights, values))  # Sortida: 240.0

Explicació del Codi

  • Relació Valor/Pes: Es calcula la relació valor/pes per a cada objecte.
  • Ordenació: Els objectes es classifiquen en ordre descendent segons la seva relació valor/pes.
  • Selecció: Es seleccionen els objectes fins que la capacitat es completa.

Exercicis Pràctics

Exercici 1: Problema del Viatjant de Comerç (TSP)

Implementa un algorisme de força bruta per resoldre el problema del viatjant de comerç per a un conjunt petit de ciutats.

Exercici 2: Problema de la Motxilla amb Programació Dinàmica

Modifica l'algorisme de programació dinàmica per retornar també els objectes seleccionats.

Exercici 3: Algorisme Greedy per la Motxilla

Implementa un algorisme greedy per al problema de la motxilla i compara els resultats amb els obtinguts amb programació dinàmica.

Solucions dels Exercicis

Solució Exercici 1

from itertools import permutations

def tsp_brute_force(graph):
    vertices = list(graph.keys())
    min_path = float('inf')
    for perm in permutations(vertices):
        current_path = 0
        for i in range(len(perm) - 1):
            current_path += graph[perm[i]][perm[i+1]]
        current_path += graph[perm[-1]][perm[0]]
        min_path = min(min_path, current_path)
    return min_path

# Exemple d'ús
graph = {
    'A': {'B': 10, 'C': 15, 'D': 20},
    'B': {'A': 10, 'C': 35, 'D': 25},
    'C': {'A': 15, 'B': 35, 'D': 30},
    'D': {'A': 20, 'B': 25, 'C': 30}
}
print(tsp_brute_force(graph))  # Sortida: 80

Solució Exercici 2

def knapsack_dp_items(capacity, weights, values, n):
    K = [[0 for x in range(capacity + 1)] for x in range(n + 1)]
    for i in range(n + 1):
        for w in range(capacity + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif weights[i-1] <= w:
                K[i][w] = max(values[i-1] + K[i-1][w-weights[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
    
    # Recuperar els objectes seleccionats
    res = K[n][capacity]
    w = capacity
    items_selected = []
    for i in range(n, 0, -1):
        if res <= 0:
            break
        if res == K[i-1][w]:
            continue
        else:
            items_selected.append(i-1)
            res -= values[i-1]
            w -= weights[i-1]
    
    return K[n][capacity], items_selected

# Exemple d'ús
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
n = len(values)
print(knapsack_dp_items(capacity, weights, values, n))  # Sortida: (220, [2, 1])

Solució Exercici 3

# Ja implementat en l'exemple de l'algorisme greedy

Conclusió

En aquesta secció hem explorat diversos algorismes per resoldre problemes d'optimització combinatòria, incloent algorismes exactes com la programació dinàmica i heurístics com l'algorisme greedy. Hem vist com aplicar aquests algorismes a problemes clàssics com el problema de la motxilla i el problema del viatjant de comerç. Els exercicis pràctics proporcionats ajuden a consolidar els conceptes apresos i a desenvolupar habilitats per resoldre problemes reals.

En el següent mòdul, explorarem altres tècniques d'optimització com els algorismes genètics i l'optimització de colònia de formigues.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats