Algorithmic Solutions: Python and MiniZinc Code Snippets
Iterador de Fuerza Bruta (Base N)
Implementación de un iterador genérico para generar combinaciones en una base N, esencial para problemas de búsqueda exhaustiva como Knapsack o la generación de permutaciones.
def next_number(digits, base):
next_digits = digits.copy()
carry = 1
for digit in range(len(next_digits) - 1, -1, -1):
next_val = next_digits[digit] + carry
carry = next_val // base
if carry == 0:
next_digits[digit] = next_val
return next_digits
next_digits[digit] = 0
return next_digits
class My_Iterator:
def __init__(self, num_digits, base):
self.num_digits = num_digits
self.base = base
def next(self):
d = [0] * (self.num_digits - 1) + [-1]
max_combination = [self.base - 1] * self.num_digits
while d != max_combination:
d = next_number(d, self.base)
yield d
return
Problema de la Mochila (Fuerza Bruta)
Solución al problema 0/1 Knapsack utilizando el iterador de fuerza bruta para generar todas las posibles combinaciones de inclusión de ítems.
from my_iterator import *
def solve(capacity, input_list):
best_value = 0
solution = []
items = []
# Parsear la lista de entrada (valor, peso)
for item in input_list:
value, weight = map(int, item.split())
items.append((value, weight))
num_items = len(items)
# Base 2: 0 (no tomar) o 1 (tomar)
it = My_Iterator(num_items, 2)
for combination in it.next():
total_weight = 0
total_value = 0
chosen_items = []
for i, take in enumerate(combination):
if take == 1:
value, weight = items[i]
total_weight += weight
total_value += value
chosen_items.append(i + 1)
# Verificar si es una solución válida y mejor
if total_weight <= capacity and total_value > best_value:
best_value = total_value
solution = chosen_items
return best_value, solution
Ordenamiento Topológico (Fuerza Bruta)
Encuentra todos los ordenamientos topológicos válidos de un grafo dirigido, verificando cada permutación posible de nodos.
from my_iterator import *
import networkx as nx
from itertools import permutations
def solve(input_list):
solutions_list = []
# Construir el grafo a partir de la lista de aristas
G = nx.DiGraph()
max_node = 0
edges = []
for line in input_list:
u, v = map(int, line.split())
edges.append((u, v))
max_node = max(max_node, u, v)
num_nodes = max_node + 1
nodes = list(range(num_nodes))
# Usar fuerza bruta para generar todas las permutaciones posibles
for digits in permutations(nodes):
G.clear()
G.add_nodes_from(nodes)
G.add_edges_from(edges)
# Verificar si la permutación actual es un orden topológico válido
pos = {node: i for i, node in enumerate(digits)}
valid = all(pos[u] < pos[v] for u, v in edges)
if valid:
solutions_list.append(list(digits))
return len(solutions_list), solutions_list
Iterador con Dominios Concretos
Clase iteradora que genera combinaciones donde cada dígito tiene su propio conjunto de valores permitidos (dominios).
class My_Iterator:
def __init__(self, num_digits, digit_values):
self.num_digits = num_digits
self.digit_values = digit_values
def next(self):
# Creamos un vector de índices para recorrer los dominios
indices = [0] * self.num_digits
while True:
# Generamos la combinación actual
current = [self.digit_values[i][indices[i]] for i in range(self.num_digits)]
yield current
# Incrementamos los índices tipo "contador"
for i in reversed(range(self.num_digits)):
indices[i] += 1
if indices[i] < len(self.digit_values[i]):
break
indices[i] = 0
else:
# Si hemos recorrido todas las combinaciones, terminamos
return
Componentes Conectados (BFS)
Algoritmo de Búsqueda en Amplitud (BFS) para identificar y listar los componentes conectados de un grafo.
import networkx as nx
from simple_queue import Queue
def solve(graph):
visited = set()
components = []
for node in graph.nodes:
if node not in visited:
queue = Queue()
queue.enqueue(node)
component = []
while not queue.isEmpty():
current = queue.dequeue()
if current not in visited:
visited.add(current)
component.append(current)
for neighbor in graph.neighbors(current):
if neighbor not in visited:
queue.enqueue(neighbor)
components.append(component)
return components
Devolución del Cambio (DFS)
Uso de Búsqueda en Profundidad (DFS) para encontrar la combinación de monedas que minimiza la cantidad total de monedas para un cambio dado.
from sys import maxsize as infinite
def solve(coins, change):
solutions_list = []
min_length = [infinite] # Lista para permitir acceso/modificación desde inner function
def dfs(index, current_sum, current_path):
# Caso base: solución válida
if current_sum == change:
if len(current_path) < min_length[0]:
min_length[0] = len(current_path)
solutions_list.clear()
solutions_list.append(current_path.copy())
elif len(current_path) == min_length[0]:
solutions_list.append(current_path.copy())
return
# Si superamos el cambio, terminamos esa rama
if current_sum > change:
return
# Explorar todas las monedas (se permite reutilizar la misma moneda)
for i in range(index, len(coins)):
dfs(i, current_sum + coins[i], current_path + [i + 1]) # Guardamos el índice como enunciado
dfs(0, 0, [])
if not solutions_list:
return None
return solutions_list
Árbol de Expansión Mínimo (Kruskal)
Implementación del algoritmo de Kruskal para encontrar el Árbol de Expansión Mínimo (MST), utilizando DFS para la detección de ciclos.
import minigraph as nx
def check_cycle(tree, new_edge):
start, end = new_edge[0], new_edge[1]
visited = set()
def dfs(node):
if node == end:
return True
visited.add(node)
for neighbor in tree.neighbors(node):
if neighbor not in visited:
if dfs(neighbor):
return True
return False
return dfs(start)
def solve(input_list):
tree_edges_list = []
edges = []
# Leer y almacenar todas las aristas con su peso
for line in input_list:
u, v, w = line.split()
edges.append((u, v, int(w)))
edges.sort(key=lambda x: x[2])
tree = nx.Graph() # Inicializar grafo vacío (árbol)
for u, v, _ in edges:
tree.add_node(u)
tree.add_node(v)
for edge in edges:
# Si agregar la arista no crea un ciclo
if not check_cycle(tree, edge):
tree_edges_list.append(edge)
tree.add_edge(edge[0], edge[1], weight=edge[2])
return tree_edges_list
Coloreado de Grafos (Algoritmo RLF)
Algoritmo heurístico Recursive Largest First (RLF) para la coloración de grafos, priorizando nodos con mayor grado y aquellos que restringen más a los nodos no coloreados.
import minigraph as nx
def rlf_graph_coloring(graph):
nodes = set(graph.nodes())
colors = {}
color = 0
while nodes:
# 1. Elegir el nodo v con el mayor grado en el subgrafo no coloreado
v = max(nodes, key=lambda x: graph.degree(x))
color_class = {v}
forbidden = set(graph.neighbors(v))
nodes.remove(v)
while True:
# Candidatos: nodos no coloreados y no adyacentes a ningún nodo en color_class
candidates = [n for n in nodes if n not in forbidden]
if not candidates:
break
# 2. Elegir el candidato u que tenga el mayor número de vecinos en 'forbidden'
u = max(
candidates,
key=lambda n: (
len(set(graph.neighbors(n)) & forbidden),
graph.degree(n),
-n # si hay empate, toma menor índice
)
)
color_class.add(u)
nodes.remove(u)
forbidden.update(graph.neighbors(u))
for n in color_class:
colors[n] = color
color += 1
sorted_dict = {k: colors[k] for k in sorted(colors)}
return list(sorted_dict.values())
Distancia Mínima (Memoization)
Cálculo de la distancia mínima en un grafo ponderado utilizando programación dinámica con memoización (similar a Bellman-Ford o Dijkstra recursivo).
import minigraph as nx
def solve(graph, from_node, to_node):
memo = {}
parent = {}
def dist(v):
if v == from_node:
return 0
if v in memo:
return memo[v]
min_cost = float('inf')
best_u = None
for u in graph.predecessors(v):
edges = graph.edges(u, data=True)
weight = None
for src, dst, data in edges:
if dst == v:
weight = data.get('weight', 0)
break
if weight is None:
continue # No hay arista válida
d = dist(u) + weight
if d < min_cost:
min_cost = d
best_u = u
memo[v] = min_cost
parent[v] = best_u
return min_cost
min_distance = dist(to_node)
# Reconstrucción del camino
if min_distance == float('inf'):
return float('inf'), []
path = []
current = to_node
while current != from_node:
path.append(current)
current = parent[current]
path.append(from_node)
path.reverse()
return min_distance, path
Camino Mínimo (BFS)
Algoritmo de Búsqueda en Amplitud (BFS) para encontrar el camino más corto en términos de número de aristas (grafo no ponderado).
import networkx as nx
from simple_queue import *
def bfs_path(graph, first_node, last_node):
visited = set()
parent = {}
queue = Queue()
queue.enqueue(first_node)
visited.add(first_node)
parent[first_node] = None
while not queue.isEmpty():
current = queue.dequeue()
if current == last_node:
break
for neighbor in graph.neighbors(current):
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = current
queue.enqueue(neighbor)
# Reconstruir la ruta desde last_node hacia first_node
route = []
current = last_node
if last_node not in parent:
return []
while current is not None:
route.append(current)
current = parent.get(current)
route.reverse()
return route
Función Partition (Quicksort)
Implementación del paso de partición utilizado en el algoritmo Quicksort, reordenando los elementos alrededor de un pivote.
def partition(items, left_pos, right_pos):
pivot = items[left_pos]
i = left_pos + 1
j = right_pos
while True:
# Avanzar i mientras el valor sea menor o igual al pivote
while i <= j and items[i] <= pivot:
i += 1
# Retroceder j mientras el valor sea mayor al pivote
while i <= j and items[j] > pivot:
j -= 1
# Si los índices se cruzan, salir
if i > j:
break
# Intercambiar los valores en i y j
items[i], items[j] = items[j], items[i]
# Finalmente, intercambiar el pivote con el elemento en j
items[left_pos], items[j] = items[j], items[left_pos]
return j
Programación Dinámica con Memoización
Implementación de una función recursiva con memoización para resolver un problema de programación dinámica definido por la relación de recurrencia t(p, q).
def solve(p, q):
# Creamos un diccionario para guardar subproblemas
memo = {}
def t(p, q):
if (p, q) in memo:
return memo[(p, q)]
if p == q:
memo[(p, q)] = 1
return 1
# Opción 1: tomar t(p+1, q)
op1 = t(p + 1, q)
# Opción 2: sumatoria desde k=p hasta k=q-1 de t(p,k) + t(k+1,q)
op2 = 0
for k in range(p, q):
op2 += t(p, k) + t(k + 1, q)
result = max(op1, op2)
memo[(p, q)] = result
return result
return t(p, q)
MiniZinc: Asignación de Trasplantes de Riñón
Modelo de optimización para maximizar la compatibilidad total en la asignación de donantes a receptores.
% Variables de decisión: asignar a cada donante un receptor
array[PARTICIPANTS] of var PARTICIPANTS: assignment;
% Todos los receptores deben estar emparejados una sola vez
constraint all_different(assignment);
% Se prohíben emparejamientos con 0% de compatibilidad
constraint
forall(i in PARTICIPANTS) (
compatibility[donor_categories[i], recipient_categories[assignment[i]]] > 0
);
% Función objetivo: maximizar la compatibilidad total
var int: total_compatibility =
sum(i in PARTICIPANTS)(
compatibility[donor_categories[i], recipient_categories[assignment[i]]]
);
solve maximize total_compatibility;
output [
"Compatibilidad total: ", show(total_compatibility), "\n",
"Emparejamiento: ", show(assignment)
];
MiniZinc: Dosis de Pesticidas (Restricciones)
Modelo para asignar dosis de pesticidas minimizando la suma total, sujeto a restricciones de diferencia y ordenamiento.
array[1..N] of var min_dosis..max_dosis: dosis;
constraint all_different(dosis);
% Restricción: No progresión aritmética de longitud 3
constraint forall(i in 1..N-2) (
2 * dosis[i+1] != dosis[i] + dosis[i+2]
);
% Restricción: Dosis crecientes en la segunda mitad
constraint forall(i in 1..N div 2, j in (N div 2 + 1)..N) (
dosis[i] < dosis[j]
);
solve minimize sum(dosis);
MiniZinc: Planificación de Ayuda Humanitaria
Modelo de scheduling que utiliza la restricción cumulative y asegura que las tareas de alta prioridad se completen antes que las de baja prioridad.
array[1..n] of var 0..sum(durations) : start_times;
var int : total_time;
constraint alldifferent(start_times);
% Restricciones de recursos (camiones y transportistas)
constraint cumulative(start_times, durations, camiones, t);
constraint cumulative(start_times, durations, transportistas, k);
% Restricción de prioridad: Prioridad 1 debe empezar antes que Prioridad 2
constraint forall(e in 1..n where priorities[e] == 1) (
forall(e2 in 1..n where priorities[e2] == 2) (
start_times[e] < start_times[e2]
)
);
constraint total_time = max([start_times[i] + durations[i] | i in 1..n]);
solve minimize total_time;
MiniZinc: Flujo Máximo en Tuberías
Modelo de flujo máximo que incorpora restricciones de capacidad, conservación de flujo y rangos de presión en las tuberías.
% Restricción: el flujo no puede exceder la capacidad
constraint forall(e in 1..num_edges)(
flow[e] <= capacity[e]
);
% Restricción: presión en rango permitido
constraint forall(e in 1..num_edges)(
let {
var int: pressure = base_pressure[e] + k * flow[e]
} in
pressure >= pressure_range[e, 1] /\ pressure <= pressure_range[e, 2]
);
% Restricción: conservación del flujo para nodos intermedios
constraint forall(n in 1..num_nodes where n != source /\ n != sink)(
let {
set of int: in_edges = {e | e in 1..num_edges where edges[e, 2] == n},
set of int: out_edges = {e | e in 1..num_edges where edges[e, 1] == n}
} in
sum(e in in_edges)(flow[e]) = sum(e in out_edges)(flow[e])
);
% Restricción: definición del flujo total que llega al sumidero
constraint
max_flow = sum(e in 1..num_edges where edges[e, 2] == sink)(flow[e]);
MiniZinc: Flujo Máximo con Capacidad de Nodo
Extensión del modelo de flujo máximo que incluye restricciones de capacidad en los nodos (estaciones de bombeo).
% Conservación de flujo en nodos intermedios (estaciones de bombeo)
constraint forall(eb in 1..num_nodes where eb != source /\ eb != sink) (
sum(i in 1..num_edges where edges[i, 1] == eb) (flow[i]) ==
sum(j in 1..num_edges where edges[j, 2] == eb) (flow[j])
);
% Restricciones de capacidad de arista
constraint forall(t in 1..num_edges) (
flow[t] >= 0 /\
flow[t] <= capacity[t]
);
% Restricción de capacidad de nodo (si node_capacity[n] está definido)
constraint forall(n in 1..num_nodes where node_capacity[n] != -1) (
sum(i in 1..num_edges where edges[i, 2] == n) (flow[i]) <= node_capacity[n]
);
constraint max_flow = sum(i in 1..num_edges where edges[i, 2] == sink) (flow[i]);
solve maximize max_flow;
MiniZinc: Knapsack 0/1 (Variables Binarias)
Modelo clásico del problema de la mochila 0/1 utilizando variables binarias para decidir qué ítems incluir.
array[ITEMS] of var 0..1: x;
var int: total_value = sum(i in ITEMS)(x[i] * value[i]);
constraint sum(i in ITEMS)(x[i] * weight[i]) <= capacity;
solve maximize total_value;
output [
"taken = {",
concat([ if fix(x[i]) = 1 then show(i) ++ ", " else "" endif | i in ITEMS ]),
"}\n",
"Total Value = ", show(total_value), "\n",
"----------\n=========="
];
MiniZinc: Ladrón de Casas (Restricciones Adyacentes)
Modelo para maximizar el valor robado sin robar casas adyacentes y respetando un límite máximo de casas robadas (x).
array[1..n] of var 0..1: taken;
% No se pueden robar casas adyacentes
constraint forall(i in 1..n-1)(taken[i] + taken[i+1] <= 1);
% Límite máximo de casas robadas
constraint sum(i in 1..n)(taken[i]) <= x;
var int: total_value = sum(i in 1..n)(taken[i] * value[i]);
solve maximize total_value;
output [
"taken = ", show(taken), "\n",
"total_value = ", show(total_value), "\n",
"--------------\n=========="
];
MiniZinc: Planificación Temporal (Cumulative)
Modelo de scheduling que minimiza el tiempo total de finalización (makespan) utilizando la restricción cumulative.
array[1..n] of var 0..sum(tiempo) : comienzo;
var 0..sum(tiempo) : total = max([comienzo[i] + tiempo[i] | i in 1..n]);
% prog: recursos requeridos por cada tarea
% k: capacidad total del recurso
constraint cumulative(comienzo, tiempo, prog, k);
solve minimize total;
MiniZinc: Reparto de Caramelos (Notas)
Modelo para distribuir caramelos basado en las notas de los estudiantes, asegurando que la cantidad de caramelos refleje las diferencias de nota.
% Asumiendo que 'x' es el array de caramelos asignados
% total_caramelos = sum(x); % Esto debería ser una definición de variable, no una restricción
% Restricción: La cantidad de caramelos de i es menor que el doble de la cantidad de j
constraint forall(i in 1..n, j in 1..n)(x[i] < 2*x[j]);
% Restricciones basadas en la comparación de notas adyacentes
constraint forall(i in 2..n)(
(nota[i] == nota[i-1] -> x[i] == x[i-1]) /\
(nota[i] > nota[i-1] -> x[i] > x[i-1]) /\
(nota[i] < nota[i-1] -> x[i] < x[i-1])
);
MiniZinc: Sudoku Solver
Modelo de satisfacción para resolver Sudokus utilizando la restricción alldifferent en filas, columnas y bloques 3×3.
% R es el rango de filas/columnas (e.g., 1..9)
% Restricción: Todas las filas deben tener valores diferentes
constraint
forall(r in R) (
alldifferent([s[r, c] | c in R])
);
% Restricción: Todas las columnas deben tener valores diferentes
constraint
forall(c in R) (
alldifferent([s[r, c] | r in R])
);
% Restricción: Todos los bloques 3x3 deben tener valores diferentes
constraint
forall(sr in 0..2, sc in 0..2) (
alldifferent([s[3*sr + r, 3*sc + c] | r in 1..3, c in 1..3])
);
solve satisfy;
output [
show([s[r, c] | r in R, c in R])
];
MiniZinc: Knapsack 0/1 (Variables de Conjunto)
Modelo alternativo del problema de la mochila 0/1 utilizando una variable de conjunto para representar los ítems seleccionados.
var set of 1..n : taken;
var int : valor;
% Restricción de capacidad
constraint capacity >= sum(i in taken)(weight[i]);
% Definición del valor total
constraint valor = sum(i in taken) (value[i]);
solve maximize valor;
MiniZinc: Ubicación de Instalaciones
Modelo de optimización para minimizar el costo total de abrir instalaciones y asignar clientes a ellas.
var float: total_cost = sum(f in Facilities)(open[f] * installation_costs[f]) +
sum(c in Clients, f in Facilities)(transportation_costs[f, c] * assign[f, c]);
solve minimize(total_cost);
% Restricción: Si un cliente es asignado a una instalación, esta debe estar abierta
constraint forall(c in Clients, f in Facilities where assign[f, c] == 1)(open[f] == 1);
% Restricción: Cada cliente debe ser asignado a exactamente una instalación
constraint forall(c in Clients)(sum(f in Facilities)(assign[f,c]) == 1);
MiniZinc: TSP (Minimizar Arista Máxima)
Modelo del Problema del Viajante (TSP) que busca un circuito que minimice la longitud de la arista más larga del recorrido.
array[City] of var City: succ;
var int : maxEdge;
% Debe formar un circuito hamiltoniano
constraint circuit(succ);
% Restricciones de distancia y límite de arista
constraint forall(c in City)(
distance[c, succ[c]] != -1 /\
distance[c, succ[c]] <= maxAllowedEdge
);
% Definición de la arista máxima
constraint maxEdge = max(c in City)(distance[c, succ[c]]);
solve minimize maxEdge;
output [
"succ = \(succ)" ++
"\nmaxEdge = \(maxEdge)"
];
MiniZinc: Palillos (Criptoaritmética)
Modelo de satisfacción para resolver una ecuación criptoaritmética, donde las variables representan dígitos desconocidos.
% Asumiendo que 'x' es un array de variables de decisión que representan dígitos
constraint suma_palillos = sum(i in x)(palillos[i]);
constraint alldifferent(x);
% Ecuación criptoaritmética
constraint 2*1000+3*100+x[1]*10+3+x[2]*1000+9*100+8*10+x[3]==x[4]*1000+3*100+x[5]*10+1;
solve satisfy;
MiniZinc: Scheduling de Aerolíneas
Modelo de satisfacción para asignar vuelos a franjas horarias, respetando los límites de tiempo y la capacidad de cada franja.
constraint forall(i in Flights)(
assigned_time_slot[i] >= start_time[i] /\
assigned_time_slot[i] <= end_time[i]
);
constraint forall(i in TimeSlots)(
sum(j in Flights where assigned_time_slot[j] == i)(1) <= slot_capacity[i]
);
solve satisfy;
MiniZinc: Shop Scheduling (Minimizar Retraso)
Modelo de scheduling que busca minimizar el retraso total de las tareas respecto a sus fechas de vencimiento (due dates).
array[1..n] of var 0..sum(duration): start;
array[1..n] of int: resources = [1 | i in 1..n];
array[1..n] of var int: delay;
var int: total_delay = sum(delay);
constraint forall(i in 1..n)(
delay[i] = max(0, start[i] + duration[i] - due_date[i])
);
constraint cumulative(start, duration, resources, 1);
solve minimize total_delay;
MiniZinc: TSP (Minimizar Distancia Total)
Modelo clásico del Problema del Viajante (TSP) que busca minimizar la distancia total recorrida en un circuito cerrado.
array[1..numCities] of var int: succ;
var int: total_distance = sum(i in 1..numCities)(distance[i, succ[i]]);
constraint circuit(succ);
constraint forall(i in 1..numCities)(distance[i, succ[i]] != -1);
solve minimize total_distance;
Algoritmo de Prim (MST)
Implementación del algoritmo de Prim para encontrar el Árbol de Expansión Mínimo (MST), comenzando desde un nodo inicial.
import minigraph as nx
def solve(graph, node):
prim = nx.Graph()
visited_nodes = set()
visited_edges = set()
visited_nodes.add(node)
# Pool inicial de aristas conectadas al nodo de partida
edges_pool = set([(e[0], e[1], e[2]["weight"]) for e in graph.edges(node, data=True)])
edges_list = list()
# Continuar hasta que todos los nodos estén en el MST
while len(graph.nodes()) != len(prim.nodes()):
# Encontrar la arista de menor peso que no ha sido visitada
try:
edge = min(
edges_pool - visited_edges,
key=lambda e : e[2]
)
except ValueError:
break
visited_edges.add((edge[0], edge[1], edge[2]))
u, v, weight = edge
# Determinar qué nodo es nuevo (el que se añade al MST)
new_node = None
if u in visited_nodes and v not in visited_nodes:
new_node = v
elif v in visited_nodes and u not in visited_nodes:
new_node = u
if new_node is not None:
visited_nodes.add(new_node)
# Añadir arista al MST
prim.add_edge(u, v, weight=weight)
edges_list.append(edge)
# Añadir nuevas aristas del nuevo nodo al pool
for x in [(e[0], e[1], e[2]["weight"]) for e in graph.edges(new_node, data=True)]:
edges_pool.add(x)
return edges_list
Codificación de Huffman
Implementación del algoritmo de Huffman para generar códigos de longitud variable basados en la frecuencia de los caracteres, minimizando la longitud total codificada.
import minigraph as nx
def solve(string):
def get_freqs(string):
freqs = dict()
for char in string:
freqs[char] = freqs.get(char, 0) + 1
return freqs
def build_ordered_dict(freqs, other=None):
if other is not None:
freqs.update(other)
# Ordenar por frecuencia descendente
return dict(sorted(freqs.items(), key=lambda char : char[1], reverse=True))
def huffman_code(graph: nx.DiGraph, freqs, root):
sol = dict()
def dfs(node, prefix):
# Si el nodo es una hoja (carácter original)
if node[0] in freqs.keys():
sol[node[0]] = prefix
return
i = 0
# Recorrer vecinos ordenados (por frecuencia)
for n in sorted(graph.neighbors(node), key=lambda k : k[1]):
dfs(n, f"{prefix}{i}")
i += 1
dfs(root, "")
return sol
def build_graph(freqs):
heap = dict(freqs)
graph = nx.DiGraph()
root_node = None
while len(heap) >= 2:
# Tomar los dos nodos de menor frecuencia
node1 = heap.popitem()
node2 = heap.popitem()
sum_freq = node1[1] + node2[1]
label = f"{node1[0]}{node2[0]}"
new_node = (label, sum_freq)
graph.add_node(new_node)
graph.add_edge(new_node, (f"{node1[0]}", node1[1]))
graph.add_edge(new_node, (f"{node2[0]}", node2[1]))
# Reinsertar el nuevo nodo y reordenar
heap = build_ordered_dict(heap, {label : sum_freq})
root_node = new_node
if len(heap) == 1:
root_node = list(heap.items())[0]
return graph, root_node
freqs = build_ordered_dict(get_freqs(string))
graph, root_node = build_graph(dict(freqs))
huffman = huffman_code(graph, freqs, root_node)
# Calcular la longitud total codificada
sol = sum([freqs[k] * len(huffman[k]) for k in freqs.keys()])
return sol
Programación Dinámica: Tabulación
Implementación de la técnica de tabulación (bottom-up) para resolver un problema de subsecuencia (posiblemente la Subsecuencia Creciente Más Larga – LIS) y reconstruir la solución.
def solve_tabulation(items):
table = [0] * len(items)
taken = []
def fill_table():
# aux almacena la longitud de la subsecuencia creciente que termina en items[i]
aux = [1] * len(items)
for i in range(len(items) - 2, -1, -1):
for j in range(i + 1, len(items)):
if items[i] < items[j]:
aux[i] = max(aux[i], aux[j] + 1)
max_length = max(aux)
# Reconstrucción de la subsecuencia
for i in range(len(items)):
if aux[i] == max_length:
table[i] = 1
max_length -= 1
if max_length == 0:
break
return
def fill_taken():
nonlocal taken
for i in range(len(items)):
if table[i] == 1:
taken.append(i + 1)
return
fill_table()
fill_taken()
return len(taken), taken
Resumen de Algoritmos y Modelos
Implementaciones en Python
- Iterador de Fuerza Bruta (Base N)
- Problema de la Mochila (Fuerza Bruta)
- Ordenamiento Topológico (Fuerza Bruta)
- Iterador con Dominios Concretos
- Componentes Conectados (BFS)
- Devolución del Cambio (DFS)
- Árbol de Expansión Mínimo (Kruskal)
- Coloreado de Grafos (RLF)
- Distancia Mínima (Memoization)
- Camino Mínimo (BFS)
- Función Partition (Quicksort)
- Programación Dinámica con Memoización (Fórmula)
- Algoritmo de Prim (MST)
- Codificación de Huffman
- Programación Dinámica: Tabulación
Modelos de Optimización en MiniZinc
- Asignación de Trasplantes de Riñón
- Dosis de Pesticidas (Restricciones)
- Planificación de Ayuda Humanitaria (Prioridades)
- Flujo Máximo en Tuberías (Presión)
- Flujo Máximo con Capacidad de Nodo
- Knapsack 0/1 (Variables Binarias)
- Ladrón de Casas (Restricciones Adyacentes)
- Planificación Temporal (Cumulative)
- Reparto de Caramelos (Notas)
- Sudoku Solver
- Knapsack 0/1 (Variables de Conjunto)
- Ubicación de Instalaciones
- TSP (Minimizar Arista Máxima)
- Palillos (Criptoaritmética)
- Scheduling de Aerolíneas
- Shop Scheduling (Minimizar Retraso)
- TSP (Minimizar Distancia Total)