Els algorismes greedy (o golafres) són una tècnica de disseny d'algorismes que construeixen una solució pas a pas, escollint en cada pas l'opció que sembla ser la millor en aquell moment. Aquesta tècnica és molt útil per a problemes d'optimització on es busca una solució òptima o gairebé òptima.
Conceptes Clau
- Elecció Greedy: En cada pas, es fa una elecció que sembla ser la millor en aquell moment.
- Propietat de Subestructura Òptima: Una solució òptima global es pot construir a partir de solucions òptimes locals.
- Propietat de Greedy Choice: La millor elecció en cada pas condueix a una solució òptima global.
Exemples d'Algorismes Greedy
- Problema del Camí Més Curt (Algorisme de Dijkstra)
L'algorisme de Dijkstra és un exemple clàssic d'algorisme greedy que resol el problema del camí més curt en un graf amb pesos no negatius.
Pseudocodi
function Dijkstra(G, s):
for each vertex v in G:
dist[v] := infinity
prev[v] := undefined
dist[s] := 0
Q := set of all nodes in G
while Q is not empty:
u := vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u:
alt := dist[u] + length(u, v)
if alt < dist[v]:
dist[v] := alt
prev[v] := u
return dist[], prev[]Explicació
- Inicialització: Es defineixen les distàncies inicials a tots els nodes com a infinites, excepte el node d'origen
sque es defineix com a 0. - Selecció Greedy: Es selecciona el node
uamb la menor distància actual. - Actualització: Es revisen tots els veïns del node
ui s'actualitzen les distàncies si es troba un camí més curt.
- Problema de la Motxilla Fraccionària
En aquest problema, es busca omplir una motxilla amb objectes de diferents pesos i valors per maximitzar el valor total, però es permet fraccionar els objectes.
Pseudocodi
function KnapsackFractional(W, items):
for each item in items:
item.value_per_weight := item.value / item.weight
sort items by value_per_weight in descending order
total_value := 0
for each item in items:
if W == 0:
return total_value
if item.weight <= W:
W := W - item.weight
total_value := total_value + item.value
else:
total_value := total_value + item.value_per_weight * W
W := 0
return total_valueExplicació
- Inicialització: Es calcula el valor per unitat de pes per a cada objecte.
- Ordenació: Es classifiquen els objectes en ordre descendent segons el valor per unitat de pes.
- Selecció Greedy: Es seleccionen els objectes en ordre fins que la motxilla està plena o no es poden afegir més objectes.
Exercici Pràctic
Problema: Monedes per Canvi
Donat un conjunt de denominacions de monedes i una quantitat de diners, troba el nombre mínim de monedes necessàries per fer el canvi.
Pseudocodi
function MinCoins(coins, amount):
sort coins in descending order
num_coins := 0
for each coin in coins:
while amount >= coin:
amount := amount - coin
num_coins := num_coins + 1
if amount > 0:
return -1 // No es pot fer el canvi exactament
return num_coinsExplicació
- Ordenació: Es classifiquen les monedes en ordre descendent.
- Selecció Greedy: Es seleccionen les monedes més grans possibles fins que es completi la quantitat.
Exercici
Implementa l'algorisme en el teu llenguatge de programació preferit i prova'l amb les següents denominacions i quantitats:
- Denominacions: [1, 5, 10, 25]
- Quantitat: 63
Solució
def min_coins(coins, amount):
coins.sort(reverse=True)
num_coins = 0
for coin in coins:
while amount >= coin:
amount -= coin
num_coins += 1
if amount > 0:
return -1 # No es pot fer el canvi exactament
return num_coins
# Prova
coins = [1, 5, 10, 25]
amount = 63
print(min_coins(coins, amount)) # Sortida esperada: 6 (2x25, 1x10, 3x1)Resum
Els algorismes greedy són una tècnica poderosa per resoldre problemes d'optimització, però no sempre garanteixen una solució òptima. És important assegurar-se que el problema té les propietats necessàries perquè un algorisme greedy funcioni correctament. En aquest mòdul, hem vist exemples clàssics com l'algorisme de Dijkstra i el problema de la motxilla fraccionària, així com un exercici pràctic per reforçar els conceptes apresos.
Curs d'Anàlisi i Disseny d'Algorismes
Mòdul 1: Introducció als Algorismes
Mòdul 2: Anàlisi d'Algorismes
- Anàlisi de Complexitat Temporal
- Anàlisi de Complexitat Espacial
- Cases de Complexitat: Millor, Pitjor i Promig
Mòdul 3: Estratègies de Disseny d'Algorismes
Mòdul 4: Algorismes Clàssics
- Cerca Binària
- Ordenació per Inserció
- Ordenació per Mescla (Merge Sort)
- Ordenació Ràpida (Quick Sort)
- Algorisme de Dijkstra
- Algorisme de Floyd-Warshall