-
-
Save Ismael-VC/33e40ed7a4ad9ccd4c77 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
## Algoritmos de caminos más cortos | |
from estructuras import Cola, ColaMin | |
from conectividad import ordenamiento_topologico | |
inf = float('inf') #Tratar infinito como un numero | |
def recorrido_a_lo_ancho(G, s): | |
dist, padre = {v:inf for v in G}, {v:v for v in G} | |
dist[s] = 0 | |
Q = Cola([s]) | |
while Q: | |
u = Q.desencolar() | |
for v in G[u]: | |
if dist[v] == inf: | |
Q.encolar(v) | |
dist[v], padre[v] = dist[u] + 1, u | |
return dist, padre | |
def relajar(G, u, v, dist, padre): | |
d = dist[u] + G[u][v] #Estimar distancia de s a v pasando por u---v | |
if d < dist[v]: #¿Es un camino mas corto? | |
dist[v], padre[v] = d, u #Actualizar distancia y camino mas corto | |
return True #Hubo cambios | |
return False #No hubo cambios | |
def inicializar_caminos_mas_cortos(G, s): | |
dist, padre = {u:inf for u in G}, {v:v for v in G} | |
dist[s] = 0 #distancia de s a si mismo es 0 | |
return dist, padre | |
def dijkstra(G, s): | |
dist, padre = inicializar_caminos_mas_cortos(G, s) | |
H = ColaMin(dist) #Crear una cola con prioridad mínima dist[.] | |
while H: #¿Todavia hay vertices por explorar? | |
u = H.extraer_min() #Elegir el mas cercano a s | |
for v in G[u]: #Actualizar caminos de sus vecinos | |
if v in H and relajar(G, u, v, dist, padre): | |
H.bajar_prioridad(v, dist[v]) | |
return dist, padre | |
def bellman_ford(G, s): | |
dist, padre = inicializar_caminos_mas_cortos(G, s) | |
for k in G: #Hacer |V| repeticiones | |
sin_cambios = True | |
for u in G: | |
for v in G[u]: | |
if relajar(G, u, v, dist, padre): | |
sin_cambios = False | |
if sin_cambios: break | |
else: | |
raise ValueError('Ciclo negativo') | |
return dist, padre | |
def caminos_mas_cortos_en_gads(G, s): | |
dist, padre = inicializar_caminos_mas_cortos(G, s) | |
vertices = ordenamiento_topologico(G) | |
for u in vertices: | |
for v in G[u]: | |
relajar(G, u, v, dist, padre) | |
return dist, padre | |
if __name__ == '__main__': | |
from grafos import Grafo | |
#Recorrido a lo ancho | |
print('Un grafo simple:') | |
G = Grafo(dirigido = False) | |
G.trazar('S', 'A', 'B', 'C', 'S', 'D', 'E', 'S') | |
print(G) | |
print() | |
dist, padre = recorrido_a_lo_ancho(G, 'S') | |
print('Árbol generado por el recorrido a lo ancho iniciando en S:') | |
print(Grafo.arbol(padre)) | |
print() | |
print('Distancias encontradas por el recorrido:') | |
for u in dist: | |
print('d({}, {}) = {}'.format('S', u, dist[u])) | |
print() | |
print('Un digrafo pesado con pesos positivos:') | |
G = Grafo(pesado = True) | |
G.trazar('A', 4, 'B', 3, 'C', 1, 'B', 2, 'D') | |
G.trazar('A', 2, 'C', 4, 'D') | |
G.trazar('B', 3, 'E', 1, 'D') | |
G.trazar('C', 4, 'D') | |
G.trazar('C', 5, 'E') | |
print(G) | |
print() | |
dist, padre = dijkstra(G, 'A') | |
print('Árbol generado por el algoritmo de Dijkstra iniciando en A:') | |
print(Grafo.arbol(padre)) | |
print() | |
print('Distancias encontradas por el algoritmo:') | |
for u in dist: | |
print('d({}, {}) = {}'.format('A', u, dist[u])) | |
print() | |
print('Un digrafo pesado sin ciclos negativos:') | |
G = Grafo(pesado = True) | |
G.trazar('S', 10, 'A', 2, 'E', -2, 'B', 1, 'A') | |
G.trazar('S', 8, 'G', 1, 'F', -4, 'A') | |
G.trazar('B', 1, 'C', 3, 'D', -1, 'E') | |
G.trazar('F', -1, 'E') | |
print(G) | |
print() | |
dist, padre = bellman_ford(G, 'S') | |
print('Árbol generado por el algoritmo de Bellman-Ford iniciando en S:') | |
print(Grafo.arbol(padre)) | |
print() | |
print('Distancias encontradas por el algoritmo:') | |
for u in dist: | |
print('d({}, {}) = {}'.format('A', u, dist[u])) | |
print() | |
print('Un digrafo pesado sin ciclos dirigidos:') | |
G = Grafo(pesado = True) | |
G.trazar('S', 2, 'B', 7, 'C', 1, 'E') | |
G.trazar('A', 3, 'B', 2, 'E') | |
G.trazar('A', 5, 'S', 6, 'C', -1, 'D', -2, 'E') | |
G.trazar('B', 4, 'D') | |
print(G) | |
print() | |
print('Ordenamiento topologico:') | |
print(', '.join(ordenamiento_topologico(G))) | |
print() | |
dist, padre = caminos_mas_cortos_en_gads(G, 'S') | |
print('Árbol de caminos más cortos desde S calculado en orden topológico:') | |
print(Grafo.arbol(padre)) | |
print() | |
print('Distancias encontradas por el algoritmo:') | |
for u in dist: | |
print('d({}, {}) = {}'.format('S', u, dist[u])) | |
print() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
## Descripción: ejemplos de implementación y aplicación | |
## del recorrido en profundidad en grafos. | |
## Autor: Mario Abarca | |
## Lenguaje: Python 3 | |
## Fecha: 4 de febrero de 2015 | |
def componentes_conexas(G): | |
def visita(v): #subrutina | |
cc[v] = componente_actual | |
for u in G[v]: | |
if u not in cc: #u no visitado <=> u no tiene componente | |
visita(u) | |
cc = dict() #Etiqueta de componente conexa | |
componente_actual = 0 | |
for v in G: | |
if v not in cc: | |
visita(v) | |
componente_actual += 1 | |
return cc | |
def voltear(G): #Regresa un nuevo grafo con las aristas en direccion contraria | |
H = {v:[] for v in G} | |
for v in G: | |
for u in G[v]: | |
H[u].append(v) | |
return H | |
def postorden(G): | |
def visita(u): #Subrutina del recorrido en profundidad | |
visitados.add(u) | |
for v in G[u]: | |
if v not in visitados: | |
visita(v) | |
lista.append(u) | |
lista, visitados = [], set() | |
for u in G: | |
if u not in visitados: #¿Faltan vértices por visitar? | |
visita(u) #Vistarlos | |
return lista | |
def ordenamiento_topologico(G): | |
lista, post = postorden(G), dict() | |
for i, u in enumerate(lista): | |
post[u] = i | |
#¿El recorrido generó una arista de retroceso? | |
if any(post[u] < post[v] for u in G for v in G[u]): | |
raise ValueError('No existe orden topológico para este grafo.') | |
return list(reversed(lista)) | |
def componentes_fuertemente_conexas(G): | |
def visita(v): #Subrutina | |
cfc[v] = componente_actual | |
for u in G[v]: | |
if u not in cfc: #u no visitado <=> no tiene componente | |
visita(u) | |
V = postorden(voltear(G)) #Calcular posorden sobre el grafo volteado | |
V.reverse() #Invertir el orden | |
cfc = dict() #Etiqueta de comp. fuertemente conexa | |
componente_actual = 0 | |
for v in V: #en posorden invertido sobre el grafo revertido | |
if v not in cfc: | |
visita(v) | |
componente_actual += 1 | |
return cfc | |
if __name__ == '__main__': | |
from grafos import Grafo | |
## Componentes conexas | |
print('Un grafo simple:') | |
G = Grafo(dirigido = False) | |
G.trazar('B', 'A', 'E', 'I', 'J') | |
G.trazar('F') | |
G.trazar('L', 'H', 'K', 'G', 'H', 'C', 'G') | |
G.trazar('C', 'D', 'H') | |
print(G) | |
cc = componentes_conexas(G) | |
print('Etiqueta de componentes conexas:') | |
for v in cc: | |
print('cc({}) = {}'.format(v, cc[v])) | |
print() | |
## Ordenamiento topologico | |
print('Un digrafo sin ciclos dirigidos:') | |
G = Grafo() | |
G.trazar('A', 'D', 'F') | |
G.trazar('A', 'B', 'D', 'C', 'F') | |
G.trazar('A', 'C') | |
G.trazar('B', 'E', 'D') | |
G.trazar('G', 'D') | |
G.trazar('G', 'F') | |
G.trazar('G', 'E') | |
print(G) | |
print() | |
orden = ordenamiento_topologico(G) | |
print('Lista de vertices en orden topológico:') | |
print(', '.join(orden)) | |
print() | |
## Componentes fuertemente conexas | |
print('Un digrafo con ciclos dirigidos:') | |
G = Grafo() | |
G.trazar('A', 'B', 'C', 'F', 'H', 'K', 'L', 'J', 'I', 'G', 'H') | |
G.trazar('B', 'E', 'F', 'C') | |
G.trazar('E', 'B', 'D') | |
G.trazar('E', 'G', 'J') | |
print(G) | |
print() | |
cfc = componentes_fuertemente_conexas(G) | |
print('Componentes fuertemente conexas del digrafo:') | |
for v in cfc: | |
print('cfc({}) = {}'.format(v, cfc[v])) | |
print() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
## Estructuras de datos usadas en Optimización Combinatoria | |
from collections.abc import Sized, Iterable, Container, Mapping | |
### NODOS ### | |
class _Nodo: | |
__slots__ = 'valor', 'siguiente' | |
def __init__(self, valor, siguiente = None): | |
self.valor, self.siguiente = valor, siguiente | |
### COLAS ### | |
class Cola(Sized, Iterable, Container): | |
__slots__ = '_frente', '_atras', '_contador' | |
def __init__(self, elementos = None): | |
self._frente, self._atras = None, None | |
self._contador = 0 | |
if elementos is not None: | |
for elemento in elementos: | |
self.encolar(elemento) | |
def encolar(self, elemento): | |
nodo = _Nodo(elemento) | |
if self._frente is None: | |
self._atras = nodo | |
self._frente = nodo | |
else: | |
self._atras.siguiente = nodo | |
self._atras = nodo | |
self._contador += 1 | |
def desencolar(self): | |
if self._frente is not None: | |
elemento = self._frente.valor | |
self._frente = self._frente.siguiente | |
self._contador -= 1 | |
return elemento | |
else: raise IndexError('desencolar en una Cola vacía') | |
def __len__(self): | |
return self._contador | |
def __iter__(self): | |
nodo = self._frente | |
while nodo is not None: | |
yield nodo.valor | |
nodo = nodo.siguiente | |
def __contains__(self, elemento): | |
for miembro in self: | |
if miembro == elemento: | |
return True | |
return False | |
def __repr__(self): | |
return 'Cola({})'.format(list(self) if self else '') | |
### PILAS ### | |
class Pila(Sized, Iterable, Container): | |
__slots__ = '_cima', '_contador' | |
def __init__(self, elementos): | |
self._cima = None | |
self._contador = 0 | |
for elemento in elementos: | |
self.apilar(elemento) | |
def apilar(self, elemento): | |
self._cima = _Nodo(elemento, self._cima) | |
self._contador += 1 | |
def desapilar(self): | |
if self._cima is not None: | |
elemento = self._cima.valor | |
self._cima = self._cima.siguiente | |
self._contador -= 1 | |
else: raise IndexError('desapilar en una Pila vacía') | |
def __len__(self): | |
return self._contador | |
def __iter__(self): | |
nodo = self._cima | |
while nodo is not None: | |
yield nodo.valor | |
nodo = nodo.siguiente | |
def __contains__(self, elemento): | |
for miembro in self: | |
if miembro == elemento: | |
return True | |
return False | |
def __repr__(self): | |
return 'Pila({})'.format(list(self) if self else '') | |
### COLAS DE PRIORIDAD MINIMA ### | |
def _padre(indice): return (indice - 1)//2 | |
def _hijo_izquierdo(indice): return 2*indice + 1 | |
def _hijo_derecho(indice): return 2*(indice + 1) | |
class ColaMin(Mapping): | |
def __init__(self, prioridades = None): | |
self._elementos = [] #arreglo de elementos | |
self._prioridades = [] #arreglo de prioridades | |
self._asas = dict() #tabla asociativa de elementos a indices | |
if prioridades is not None: | |
if not isinstance(prioridades, dict): | |
raise TypeError('') | |
for (elemento, prioridad) in prioridades.items(): | |
self.introducir_con_prioridad(elemento, prioridad) | |
def introducir_con_prioridad(self, elemento, prioridad): | |
self._elementos.append(elemento) | |
self._prioridades.append(prioridad) | |
self._asas[elemento] = len(self) - 1 | |
self._flotar(len(self) - 1) | |
def extraer_min(self): | |
if not self: #¿Es vacio? | |
raise IndexError('No se puede extraer de una ColaMin vacia') | |
self._intercambiar(0, len(self) - 1) #Intercambiar primero con ultimo | |
#Extraer el ultimo elemento: | |
elemento = self._elementos.pop() | |
self._prioridades.pop() | |
del self._asas[elemento] | |
self._hundir(0) #Recuperar la propiedad del monticulo | |
return elemento | |
def bajar_prioridad(self, elemento, prioridad): | |
i = self._asas[elemento] #Obtener indice del elemento actual | |
if self._prioridades[i] <= prioridad: | |
raise ValueError('La prioridad debe ser menor que la actual') | |
self._prioridades[i] = prioridad #Bajar prioridad | |
self._flotar(i) #Recuperar la propiedad del monticulo | |
def _intercambiar(self, i, j): | |
elem_i, elem_j = self._elementos[i], self._elementos[j] | |
prio_i, prio_j = self._prioridades[i], self._prioridades[j] | |
self._elementos[i], self._elementos[j] = elem_j, elem_i | |
self._asas[elem_i], self._asas[elem_j] = j, i | |
self._prioridades[i], self._prioridades[j] = prio_j, prio_i | |
def _flotar(self, i): | |
while i > 0 and self._prioridades[i] < self._prioridades[_padre(i)]: | |
self._intercambiar(i, _padre(i)) | |
i = _padre(i) | |
def _hundir(self, i): | |
while True: | |
izq, der, hmin = _hijo_izquierdo(i), _hijo_derecho(i), i | |
if izq < len(self) and \ | |
self._prioridades[izq] < self._prioridades[hmin]: | |
hmin = izq | |
if der < len(self) and \ | |
self._prioridades[der] < self._prioridades[hmin]: | |
hmin = der | |
if hmin != i: | |
self._intercambiar(i, hmin) | |
i = hmin | |
else: break | |
def __len__(self): | |
return len(self._elementos) | |
def __iter__(self): | |
for elemento in self._elementos: | |
yield elemento | |
def __getitem__(self, elemento): | |
return self._prioridades[self._asas[elemento]] | |
def __repr__(self): | |
if not self: | |
return 'ColaMin()' #Monticulo vacio | |
t = ['{!r}:{!r}'.format(x, p) for x, p in self.items()] | |
return 'ColaMin({{{}}})'.format(', '.join(t)) | |
### ESTRUCTURA PARA CONJUNTOS DISJUNTOS ### | |
class ConjuntosDisjuntos: | |
__slots__ = '_padre', '_rango' | |
def __init__(self): | |
self._padre, self._rango = dict(), dict() | |
def hacer_conjunto(self, x): | |
self._padre[x] = x | |
self._rango[x] = 0 | |
def unir(self, x, y): | |
x, y = self.hallar_conjunto(x), self.hallar_conjunto(y) | |
if x != y: | |
if self._rango[x] > self._rango[y]: | |
self._padre[y] = x | |
else: | |
self._padre[x] = y | |
if self._rango[x] == self._rango[y]: | |
self._rango[y] += 1 | |
def hallar_conjunto(self, x): | |
if x != self._padre[x]: | |
self._padre[x] = self.hallar_conjunto(self._padre[x]) | |
return self._padre[x] | |
if __name__ == '__main__': | |
pass |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from estructuras import Cola | |
from grafos import Grafo | |
inf = float('inf') | |
#Subrutina de Edmonds-Karp para encontrar un camino de aumento | |
def aumento_en_anchura(G, H, s, t, f): | |
P, Q, F = {s: None}, Cola([s]), {s: inf} #Árbol, Cola, Flujo | |
def marcar(inc): #Incremetar flujo? | |
if v in P or inc <= 0: return #Visitado o inalcanzable | |
F[v], P[v] = min(F[u], inc), u #¿Mayor flujo?, ¿desde dónde? | |
Q.encolar(v) #v descubierto | |
while Q: #¿Hay vértices por descubrir? | |
u = Q.desencolar() #Procesar siguiente vértice | |
if u == t: return P, F[t] #Camino encontrado | |
for v in G[u]: marcar(G[u][v] - f[u,v]) #Marcar arcos salientes | |
for v in H[u]: marcar(f[v,u]) #Marcar arcos entrantes | |
return None, 0 #No hay caminos de aumento | |
#Método de Ford-Fulkerson para encontrar flujo máximo de s a t | |
def ford_fulkerson(G, s, t, camino_aum = aumento_en_anchura): | |
H = G.voltear() #Grafo al reves | |
f = {(u, v):0 for u in G for v in G[u]} #Iniciar con el flujo cero | |
while True: | |
P, c = camino_aum(G, H, s, t, f) #Camino de aumento y su valor | |
if c == 0: return f #¿Sin caminos? Terminamos | |
u = t #Comenzar aumento | |
while u != s: #Vuelta atrás hasta s | |
u, v = P[u], u #Retroceder un paso | |
if v in G[u]: f[u, v] += c #¿Arista de avance? Añadir f. | |
else: f[v, u] -= c #¿Ar. de retroceso? Cancelar f. | |
def emparejamiento(R): | |
G, s, t = Grafo(pesado = True), object(), object() #Crear red de flujo | |
for (x, y) in R: G.trazar(s, 1, x, 1, y, 1, t) #Reducir el problema | |
f = ford_fulkerson(G, s, t) #Resolver flujo maximo | |
return {(x, y) for (x, y) in R if f[x, y] > 0} #Recuperar solucion | |
if __name__ == '__main__': | |
from random import random, randint, getrandbits | |
n = 5 | |
G = Grafo.aleatorio(n, 1, pesos = range(1, 6), dirigido = True) | |
for u in list(G): | |
if random() <= 0.5: G.trazar('S', randint(1, 5), u) | |
if random() <= 0.5: G.trazar(u, randint(1, 5), 'T') | |
G.trazar('S') | |
G.trazar('T') | |
print('Una red de flujo aleatoria:') | |
print(G) | |
f = ford_fulkerson(G, 'S', 'T') | |
print('Flujo maximo:') | |
print(Grafo(E = {e: f[e] for e in f if f[e] > 0}, pesado = True)) | |
print() | |
X = ['Alejandro', 'Bruno', 'Carlos', 'Diego'] | |
Y = ['Alicia', 'Beatriz', 'Carolina', 'Daniela'] | |
R = [(x, y) for x in X for y in Y if random() <= 4/9] | |
print('Una relacion aleatoria:') | |
for x, y in R: | |
print(x, '──', y) | |
print() | |
print('Emparejamiento maximo') | |
for x, y in emparejamiento(R): | |
print(x, '──', y) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
## Los grafos en Python pueden ser implementados como se describe en | |
## www.python.org/doc/essays/graphs/ | |
## | |
## Este módulo contiene un intérprete de comandos que permite capturar | |
## dicha estructura de datos a partir de sucesiones de caminos, así como | |
## varias funciones de gran utilidad. | |
## La implementación de la clase Grafo que aparece aquí no está orientada a | |
## objetos; y está diseñada para funcionar como un dict con operaciones extras | |
## que son específicas de la creación y manipulación de grafos. | |
## | |
## Autor: Mario Abarca | |
## Licencia: creativecommons.org/licenses/by-nc-sa/3.0/deed.es | |
## Fecha: 27 de febrero de 2015 | |
import cmd | |
from collections import Counter | |
from collections.abc import KeysView as VistaDeVertices | |
from collections.abc import MappingView as _MappingView | |
from itertools import combinations | |
from random import choice, getrandbits, random | |
class VistaDeAristas(_MappingView): | |
def __len__(self): | |
return self._mapping._tamano | |
def __contains__(self, arista): | |
u, v = arista | |
return u in self._mapping and v in self._grafo[u] | |
def __iter__(self): | |
if self._mapping.dirigido: | |
for u in self._mapping: | |
for v in self._mapping[u]: | |
yield (u, v) | |
else: | |
indice = {u:i for i, u in enumerate(self._mapping.vertices)} | |
for u in self._mapping: | |
for v in self._mapping[u]: | |
if indice[u] < indice[v]: | |
yield (u, v) | |
class Grafo(dict): | |
def __init__(self, V = None, E = None, pesado = False, dirigido = True): | |
self._pesado = pesado | |
self._dirigido = dirigido | |
self._tamano = 0 | |
if V: | |
for u in V: | |
self.trazar(u) | |
if E: | |
if pesado: | |
for (u, v) in E: | |
self.trazar(u, E[u, v], v) | |
else: | |
for (u, v) in E: | |
self.trazar(u, v) | |
@property | |
def vertices(self): | |
return VistaDeVertices(self) | |
@property | |
def aristas(self): | |
return VistaDeAristas(self) | |
def vecinos(self, u): | |
return VistaDeVertices(self[u]) | |
def copia(self): | |
G = Grafo() | |
G.update({u:self[u].copy() for u in self}) | |
G._pesado = self._pesado | |
G._dirigido = self._dirigido | |
G._tamano = self._tamano | |
return G | |
def trazar(self, *camino): | |
def agregar_vertice(u): | |
if u not in self: | |
self[u] = dict() if self.pesado else set() | |
def agregar_arista(u, v, w): | |
if v not in self[u]: self._tamano += 1 | |
if self.pesado: | |
self[u][v] = w | |
if not self.dirigido: self[v][u] = w | |
else: | |
self[u].add(v) | |
if not self.dirigido: self[v].add(u) | |
elementos, w = iter(camino), None | |
u = next(elementos, None) | |
if u is not None: agregar_vertice(u) | |
while True: | |
if self._pesado: w = next(elementos, None) | |
v = next(elementos, None) | |
if v is not None: | |
agregar_vertice(v) | |
else: break | |
agregar_arista(u, v, w) | |
u = v | |
def borrar(self, *camino): | |
def quitar_arista(u, v): | |
if self.pesado: | |
if v in self[u]: | |
del self[u][v] | |
if not self.dirigido: del self[v][u] | |
else: | |
if v in self[u]: | |
self[u].remove[v] | |
if not self.dirigido: self[v].remove[u] | |
def quitar_vertice(u): | |
if self.pesado: | |
for v in self: | |
if u in self[v]: | |
del self[v][u] | |
else: | |
for v in self: | |
if u in self[v]: | |
self[v].remove(u) | |
del self[u] | |
if len(camino) == 1: | |
quitar_vertice(camino[0]) | |
elif camino: | |
for i in range(len(camino) - 1): | |
quitar_arista(camino[i], camino[i + 1]) | |
@property | |
def dirigido(self): | |
return self._dirigido | |
@property | |
def pesado(self): | |
return self._pesado | |
def voltear(self): | |
if not self.dirigido: | |
return self.copia() | |
H = Grafo(self.vertices, pesado = self.pesado, dirigido = self.dirigido) | |
if self.pesado: | |
for u in self: | |
for v in self[u]: | |
H[v][u] = self[u][v] | |
else: | |
for u in self: | |
for v in self[u]: | |
H[v].add(u) | |
H._tamano = self._tamano | |
return H | |
@staticmethod | |
def arbol(pred): | |
'''Genera un árbol (o bosque) a partir del diccionario de predecesores | |
de cada vértice. Una raíz tiene como predecesor a sí mismo (pred[r] == r)''' | |
T = Grafo() | |
for u in pred: | |
if pred[u] == u: | |
T.trazar(u) | |
else: T.trazar(pred[u], u) | |
return T | |
@staticmethod | |
def aleatorio(n, p, pesos = None, dirigido = False): | |
'''Crea un Grafo con n vértices donde cada arista tiene una probabilidad | |
p ∈ [0, 1] de aparecer. Si se proporciona una lista de pesos, el grafo será | |
pesado y cada arista generada se le asignará un peso aleatorio de la lista.''' | |
V = [chr(i) for i in range(ord('A'), ord('A') + n)] | |
if pesos is not None: pesos = list(pesos) | |
G = Grafo(dirigido = dirigido, pesado = bool(pesos)) | |
for u in V: G.trazar(u) | |
for u, v in combinations(V, 2): | |
if random() > p: continue | |
if dirigido and getrandbits(1): u, v = v, u | |
if pesos: | |
G.trazar(u, choice(pesos), v) | |
else: G.trazar(u, v) | |
return G | |
def __repr__(self): | |
if self: | |
args = [repr(set(self.vertices)), repr(set(self.aristas))] | |
else: args = [] | |
if self.pesado: | |
args.append('pesado = True') | |
if not self.dirigido: | |
args.append('dirigido = False') | |
return 'Grafo({})'.format(', '.join(args)) | |
def __str__(self): | |
## ¿El caso no dirigido se reduce a encontrar una orientaion adecuada? | |
## ¿Este algoritmo encuentra el número mínimo de trazos? | |
def factorizar(u): | |
c = [u] | |
while G[u]: | |
v = G[u].pop() | |
if not G.dirigido: G[v].remove(u) | |
c.append(v) | |
u = v | |
return c | |
def extender(c): | |
i = 0 | |
while True: | |
while i < len(c) and not G[c[i]]: | |
i += 1 | |
if i == len(c): return c | |
c[i:i + 1] = factorizar(c[i]) | |
def descomponer(): | |
if G.dirigido: | |
H = G.voltear() | |
L = [u for u in G if not (G[u] or H[u])] | |
Q = list(Counter({u:len(G[u]) - len(H[u]) for u in G})\ | |
.elements()) | |
else: | |
L = [u for u in G if not G[u]] | |
Q = {u for u in G if len(G[u]) % 2} | |
while Q: | |
L.append(factorizar(Q.pop())) | |
if not G.dirigido: Q.remove(L[-1][-1]) | |
for c in L: extender(c) | |
while True: | |
u = next((u for u in G if G[u]), None) | |
if u is None: break | |
L.append(extender(factorizar(u))) | |
return L | |
def aristas(camino): | |
for i in range(len(camino) - 1): | |
yield camino[i], camino[i + 1] | |
G = Grafo(self.vertices, self.aristas, dirigido = self.dirigido) | |
caminos = descomponer() | |
lineas = [] | |
cabeza = '►' if self.dirigido else '─' | |
if self.pesado: | |
for camino in caminos: | |
abajo = [str(camino[0])] | |
arriba = [' '*len(abajo[0])] | |
for (u, v) in aristas(camino): | |
arriba.append(' ' + str(self[u][v])) | |
abajo.append('─'*len(arriba[-1])) | |
abajo.append(cabeza + str(v)) | |
arriba.append(' '*len(abajo[-1])) | |
lineas.append(''.join(arriba)) | |
lineas.append(''.join(abajo)) | |
else: | |
arista = '─' + cabeza | |
for camino in caminos: | |
lineas.append(arista.join(camino)) | |
return '\n'.join(lineas) | |
class Programa(cmd.Cmd): | |
intro = '''Bienvenido al intérprete de comandos para la creación \ | |
de grafos en Python. | |
Teclea «?» para enlistar los comandos disponibles.''' | |
prompt = '▷ ' | |
doc_header = 'Comandos documentados (escriba help <comando>):' | |
misc_header = 'Topicos de ayuda misceláneos:' | |
undoc_header = 'Comandos sin documentación:' | |
nohelp = '* Sin ayuda para %s' | |
nosintax = '* Sintaxis desconocida: {}' | |
def __init__(self): | |
super().__init__() | |
self.rango = None | |
self.G = Grafo() | |
def do_trazar(self, args): | |
'''SINOPSIS: | |
• En grafos/digrafos simples: | |
trazar v₀ v₁ v₂ … vₖ — Agrega al grafo/digrafo el camino v₀─►v₁─►v₂─►…─►vₖ | |
• En grafos/digrafos pesados: | |
trazar v₀ w₀ v₁ w₁ v₂ w₂ … wₖ₋₁ vₖ — Agrega al grafo/digrafo el camino pesado | |
w₀ w₁ w₂ wₖ₋₁ | |
v₀──►v₁──►v₂──► … ──►vₖ | |
EJEMPLOS: | |
trazar A B C D A — Agrega los vértices A, B, C, y D al grafo actual así como | |
el ciclo A─►B─►C─►D─►A''' | |
camino = args.split() | |
if self.rango: | |
for i in range(1, len(camino), 2): | |
try: | |
camino[i] = self.rango(camino[i]) | |
except ValueError: | |
print('Error de dominio.') | |
return None | |
self.G.trazar(*camino) | |
def do_borrar(self, args): | |
'''SINOPSIS: | |
• borrar v₀ v₁ v₂ … vₖ — borra las aristas del camino v₀─►v₁─►v₂─►…─►vₖ | |
• borrar v — borra el vértice v, así como todas sus aristas incidentes. | |
EJEMPLOS: | |
borrar A B C D A — borra las aristas del ciclo A─►B─►C─►D─►A, pero conserva | |
los vértices A, B, C, y D | |
borrar A — borra el vértice A del grafo actual''' | |
self.G.borrar(*args.split()) | |
def do_nuevo(self, args): | |
'''SINOPSIS: | |
nuevo [di]grafo (simple|entero|real) — deshecha el grafo actual y lo reemplaza | |
por un grafo/digrafo simple o pesado, | |
con pesos enteros/reales, sin vértices | |
ni aristas. | |
EJEMPLOS: | |
nuevo grafo simple — crea un nuevo grafo simple | |
nuevo digrafo entero — crea un digrafo vacío con pesos enteros''' | |
args = args.split() | |
if len(args) != 2: | |
print('Se esperaban dos argumentos.') | |
return None | |
if args[0] == 'grafo': | |
dirigido = False | |
elif args[0] == 'digrafo': | |
dirigido = True | |
else: | |
print('Se esperaba "grafo" o "digrafo".') | |
return None | |
if args[1] == 'simple': | |
self.rango = None | |
elif args[1] == 'entero': | |
self.rango = int | |
elif args[1] == 'real': | |
self.rango = float | |
else: | |
print('Se esperaba "simple", "entero" o "real".') | |
self.G = Grafo(dirigido = dirigido, pesado = bool(self.rango)) | |
def do_imprimir(self, args): | |
'''SINOPSIS: | |
imprimir — Muestra en pantalla la representación por trazos del grafo actual.''' | |
print(self.G) | |
def do_representar(self, args): | |
'''SINOPSIS: | |
representar [lista] — Muestra en pantalla el código en Python que representa al | |
grafo actual. Por defecto el grafo es representado en la | |
clase Grafo. El argumento opcional “lista” muestra la | |
representación estándar de Python de listas de \ | |
adyacencia.''' | |
if args == 'lista': | |
print(repr(dict(self.G))) | |
else: print(repr(self.G)) | |
def do_vecinos(self, args): | |
'''SINOPSIS: | |
vecinos v — Muestra los vecinos del vértice v en el grafo actual.''' | |
if not args: print('Se esperaba un vértice.') | |
if args in self.G: | |
print(', '.join(self.G[args])) | |
else: print() | |
def do_salir(self, args): | |
return True | |
Programa.do_help.__doc__ = 'Muestra los comandos disponibles con "help" o \ | |
ayuda detallada con "help cmd"' | |
if __name__ == '__main__': | |
Programa().cmdloop() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from grafos import Grafo | |
from functools import lru_cache | |
from conectividad import postorden | |
inf = float('inf') | |
def mochila(v, w, C): #Valores, Pesos y Capacidad | |
n = len(w) | |
K = [[0]*(n+1) for i in range(C+1)] #Matriz de valor de los subproblemas | |
P = [[False]*(n+1) for i in range(C+1)] #Matriz de selección | |
for j in range(1, n): #Usando los primeros j objetos | |
i = j - 1 #Objeto en consideración | |
for c in range(1, C+1): #Para cada capacidad positiva | |
K[c][j] = K[c][i] #Valor sin seleccionar objeto i | |
if w[i] > c: continue #¿No cabe? Ignorarlo | |
tomar = K[c - w[i]][j-1] + v[i] #Valor al seleccionar objeto i | |
if K[c][j] < tomar: #¿Mejora la sol. al tomar el ob. i? | |
K[c][j] = tomar #Actualizar solución | |
P[c][j] = True #Recordar la selección | |
return K, P | |
def conjunto_mochila(P, w): #Construir la selección de mochila | |
c, j, S = len(P) - 1, len(P[0]) - 1, [] #Capacidad, objeto, conjunto | |
while c > 0 and j > 0: | |
if P[c][j]: | |
S.append(j - 1) | |
c -= w[j - 1] | |
j -= 1 | |
S.reverse() | |
return S | |
def floyd_warshall(G): | |
D, P = dict(), dict() #Matrices de distancias y caminos | |
for u in G: #Inicializar caminos | |
for v in G: | |
if v in G[u]: #¿v es vecino de u? | |
D[u, v], P[u, v] = G[u][v], u #Distancia y camino inicial | |
else: D[u, v], P[u, v] = inf, None #No hay camino inicial | |
for k in G: #Vértice k en consideración | |
for u in G: #Iterar sobre toda pareja de vért. | |
for v in G: | |
atajo = D[u, k] + D[k, v] #Distancia de u a v pasando por k | |
if atajo < D[u, v]: #¿Pasar por k forma un atajo? | |
D[u, v] = atajo #Actualizar distancias | |
P[u, v] = P[k, v] #Actualizar caminos | |
return D, P | |
def camino(P, u, v): #Camino u⤳v dado por Floyd-Warshall | |
lista = [v] #El camino termina en v | |
while v != u: #Hasta no llegar a u | |
v = P[u, v] #…retrocedemos un paso | |
lista.append(v) | |
lista.reverse() #Enlistamos el recorrido en reversa | |
return lista | |
def nietos(T, u): #Calcula el conjunto de nietos del vértice u en el árbol T | |
S = [] | |
for v in T[u]: | |
S.extend(T[v]) | |
return S | |
def wilf(T, r): #Conjunto independiente en árboles | |
I, P = dict(), dict() #Soluciones parciales | |
for u in postorden(T): #calculando de las hojas a la raíz | |
con_u = 1 + sum(I[w] for w in nietos(T, u)) #Valor con u en el conjunto: | |
sin_u = sum(I[h] for h in T[u]) #Valor sin u en el conjunto | |
I[u] = max(con_u, sin_u) #Seleccionar mejor valor | |
P[u] = (con_u > sin_u) #Almacenar si u pertenece a la sol. | |
return I, P #Devolver resultados parciales | |
def independiete_arbol(T, r, P): #Construye el conj. indep. de Wilf | |
S = set() #Iniciar con conjunto vacío | |
if P[r]: #¿r fue seleccionado? | |
S.add(r) #Agregar r | |
for w in nietos(T, r): #…y los subconjuntos de los nietos | |
S.update(independiete_arbol(T, w, P)) | |
else: | |
for h in T[r]: #Agrgar subconjuntos de los hijos | |
S.update(independiete_arbol(T, h, P)) | |
return S | |
if __name__ == '__main__': | |
from random import randint, shuffle | |
from itertools import combinations | |
from estructuras import ConjuntosDisjuntos | |
from caminos import recorrido_a_lo_ancho | |
print('== Problema de la mochila ==') | |
print('Objetos, peso y valor:') | |
n = 10 | |
w = [randint(1, 10) for k in range(n)] | |
v = [100*randint(1, 9) for k in range(n)] | |
C = 30 | |
for i in range(n): | |
print(i, ':', '█'*w[i], ' $', v[i]) | |
print('Capacidad:') | |
print(' ', '░'*C) | |
K, P = mochila(v, w, C) | |
S = conjunto_mochila(P, w) | |
peso = sum(w[j] for j in S) | |
print('Selección de objetos:', S) | |
print('Peso y valor seleccionado:') | |
print(' ', '█'*peso + '░'*(C-peso), '$', K[C-1][n-1]) | |
print() | |
print('== Problema de caminos más cortos entre todos los pares de v. ==') | |
print('Un digrafo pesado aleatorio:') | |
G = Grafo.aleatorio(4, 1.0, pesos = range(1, 6), dirigido = True) | |
print(G) | |
print('Caminos más cortos y distancias encontradas por Floyd-Warshall:') | |
D, P = floyd_warshall(G) | |
for u in G: | |
for v in G: | |
if u != v and D[u, v] < inf: | |
print('─►'.join(camino(P, u, v)), ':', D[u, v]) | |
print() | |
print('== Problema del conjunto independiente en árboles ==') | |
##Crear un arbol aleatorio usando Kruskal con aristas en orden aleatorio | |
n = 20 | |
V = list(map(chr, range(ord('A'), ord('A') + n))) | |
E = list(combinations(V, 2)) | |
shuffle(E) | |
F = ConjuntosDisjuntos() | |
T = Grafo(dirigido = False) | |
for v in V: F.hacer_conjunto(v) | |
for (u, v) in E: | |
if F.hallar_conjunto(u) != F.hallar_conjunto(v): | |
T.trazar(u, v) | |
F.unir(u, v) | |
print('Un árbol:') | |
print(T) | |
##Enraizar el arbol en A mediante un recorrido a lo ancho | |
dist, padre = recorrido_a_lo_ancho(T, 'A') | |
T = Grafo.arbol(padre) | |
I, P = wilf(T, 'A') | |
print('Conjunto independiente:', ', '.join(independiete_arbol(T, 'A', P))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from fractions import Fraction | |
inf = float('inf') | |
def dual(A, b, c): | |
m, n = len(b), len(c) | |
At = [[-A[i][j] for i in range(m)] for j in range(n)] #At = -transpuesta(A) | |
bt = [-c[j] for j in range(n)] #bt = -c | |
ct = [-b[i] for i in range(m)] #ct = -b | |
return At, bt, ct | |
def cuadro(A, b, c, K = Fraction): #Crea un cuadro para Simplex | |
m, n = len(b), len(c) | |
M = [[K(0)]*(1 + m + n) for i in range(m + 1)] #Crear matriz M de ceros | |
for j in range(n): M[0][j + 1] = K(c[j]) #Función objetivo en renglón M[0] | |
for i in range(m): | |
M[i + 1][0] = K(b[i]) #Constantes b[i] en columna M[i][0] | |
for j in range(n): | |
M[i + 1][j + 1] = K(A[i][j]) #Copia de A en M[1..m][1..n] | |
M[i + 1][n + i + 1] = K(1) #Agregar variables de holgura | |
return M, list(range(n + 1, m + n + 1)) #Devolver cuadro y base inicial | |
def pivotar(A, B, h, e): | |
m, n = len(A), len(A[0]) | |
r = A[h][e] #Hacer 1 en A[h,e] | |
for j in range(n): A[h][j] /= r #…dividiendo todo A[h] entre A[h,e] | |
for i in range(m): #Para todo renglón A[i] | |
if i == h: continue #…excepto A[h], | |
r = A[i][e] #hacer ceros en A[i,e] | |
for j in range(n): | |
A[i][j] -= A[h][j]*r #…restando A[i,e] veces A[h] de A[i] | |
B[h - 1] = e #Meter x[e] en la base | |
def simplex(A, B): | |
m, n = len(A), len(A[0]) | |
while True: | |
e = 1 #Buscar variable entrante x[e] | |
while e < n and A[0][e] <= 0: e += 1 #elegiendo primer e con A[0][e] > 0 | |
if e >= n: break #¿No hay? Terminamos | |
d, h, s = inf, m, n #Buscar var. más apretada x[s] | |
for i, j in enumerate(B, 1): | |
q = A[i][0]/A[i][e] if A[i][e] > 0 else inf #Holgura de x[j] | |
if q < d or (q == d and j < s): | |
d, h, s = q, i, j #x[s] tiene holgura e índice mínimos | |
if d == inf: raise ValueError('Programa no acotado.') | |
pivotar(A, B, h, e) #Pivotar en A[h][e] (sale x[s] de B) | |
def simplex_dos_fases(A, B, K = Fraction): | |
m, n = len(A), len(A[0]) | |
#Fase 1: Encontrar una sol. básica factible inicial | |
k = 1 #Elegir k que minimiza b[k] | |
for i in range(2, m): | |
if A[i][0] < A[k][0]: k = i | |
if A[k][0] < 0: #¿b[k] es negativo? | |
c = A[0][:] #Guardar función objetivo | |
for j in range(n): A[0][j] = K(0) #Borrar la f.o. del cuadro | |
for i in range(m): A[i].append(K(-1)) #Agregar variable artificial | |
pivotar(A, B, k, n) #Ingresar var. artificial a la base | |
simplex(A, B) #Buscar sol. básica factible inicial | |
if A[0][0] != K(0): #¿Es necesaria la var. artificial? | |
raise ValueError('El programa es infactible.') | |
if n in B: #¿La var. artifical es básica? | |
h, e = B.index(n) + 1, 1 #Sacarla de la base | |
while e < n and A[0][e] <= 0: e += 1 #…metiendo una x[e] no básica | |
pivotar(A, B, h, e) #…mediante un pivoteo degenerado | |
for i in range(m): A[i].pop() #Borrar var. artificial | |
A[0] = c #Recuperar función objetivo | |
for h, e in enumerate(B, 1): #Para cada x[e] en la base | |
r = A[0][e] #…hacer cero c[e] | |
for j in range(n): | |
A[0][j] -= A[h][j]*r #…restando c[e] veces A[h] de c | |
#Fase 2: Iterar simplex hasta encontrar la solución básica factible óptima | |
simplex(A, B) | |
def resolver_pl(A, b, c, K = Fraction): | |
m, n = len(b), len(c) | |
A, B = cuadro(A, b, c, K) #Inicializar | |
simplex_dos_fases(A, B, K) #Resolver mediante Simplex | |
x = [K(0)]*n | |
for i, j in enumerate(B, 1): | |
if j <= n: x[j - 1] = A[i][0] #Vector solución x | |
imprimir_cuadro(A, B) | |
y = [-A[0][j] for j in range(n + 1, n + m + 1)] #Vector solución dual y | |
return x, y, -A[0][0] #Soluciones y valor objetivo | |
def imprimir_cuadro(A, B): | |
m, n = len(A), len(A[0]) | |
x = [list(map(str, r)) for r in A] | |
p = [max(len(x[i][j]) for i in range(m)) for j in range(n)] | |
for i in range(m): | |
for j in range(n): | |
x[i][j] = x[i][j].center(p[j]) | |
x[i] = '│{}│{}│{}'.format(x[i][0], ' '.join(x[i][1:]), | |
B[i - 1] if i > 0 else '') | |
print('┌{0}┬{1}┐\n{2}\n├{0}┼{1}┤\n{3}\n└{0}┴{1}┘'.format( | |
'─'*p[0], '─'*(sum(p[1:]) + n - 2), x[0], '\n'.join(x[1:]))) | |
A = [[1, 0, 0], | |
[0, 1, 0], | |
[1, 1, 1], | |
[0, 1, 3]] | |
b = [200, 300, 400, 600] | |
c = [1, 6, 13] | |
##A = [[1, 1, 3], | |
## [2, 2, 5], | |
## [4, 1, 2]] | |
##b = [30, 24, 36] | |
##c = [3, 1, 2] | |
x, y, z = resolver_pl(A, b, c) | |
print('x =', ', '.join(map(str, x))) | |
print('y =', ', '.join(map(str, y))) | |
print('z =', z) | |
A, b, c = dual(A, b, c) | |
imprimir_cuadro(*cuadro(A, b, c)) | |
x, y, z = resolver_pl(A, b, c) | |
print('x =', ', '.join(map(str, x))) | |
print('y =', ', '.join(map(str, y))) | |
print('z =', z) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
inf = float('inf') #Tratar infinito como número | |
from estructuras import ConjuntosDisjuntos, ColaMin | |
from grafos import Grafo | |
def kruskal(G): | |
E = [(G[u][v], u, v) for u in G for v in G[u]] #Ordenar E(G) por pesos | |
T = set() #Aristas del bosque | |
S = ConjuntosDisjuntos() #Componentes conexas del bosque | |
for u in G: S.hacer_conjunto(u) | |
for _, u, v in sorted(E): | |
#Si u--v no forma un ciclo en T, añadirlo a T y unir componentes | |
if S.hallar_conjunto(u) != S.hallar_conjunto(v): | |
T.add((u, v)) | |
S.unir(u, v) | |
return T | |
def prim(G, s): | |
cost, padre = {u:inf for u in G}, {u:u for u in G} | |
cost[s] = 0 #costo[x] = longitud de la arista más pequeña x--v donde v ∈ T | |
H = ColaMin(cost) | |
while H: #¿Todavía hay vértices por agregar al árbol? | |
u = H.extraer_min() #Elegir el más cercano al árbol | |
for v in G[u]: #Actualizar costo de sus vecinos | |
if v in H and G[u][v] < cost[v]: | |
cost[v], padre[v] = G[u][v], u | |
H.bajar_prioridad(v, cost[v]) | |
return padre #El árbol tiene aristas u--padre[u] | |
def cobertura_voraz(B, S): | |
R, solucion = set(B), set() #R son los elementos restantes por cubrir | |
while R: #Mientras falten elementos por cubrir: | |
#Buscar el conjunto S[k] que cubra más elementos de R | |
indice, aporte = -1, 0 | |
for (i, X) in enumerate(S): | |
if i not in solucion: | |
C = R.intersection(X) | |
if len(C) > aporte: | |
indice, aporte = i, len(C) | |
#... y agregarlo si existe | |
if indice >= 0: | |
R.difference_update(S[indice]) | |
solucion.add(indice) | |
else: break | |
return solucion | |
def voraz(peso, es_independiente): | |
S = [(peso[x], x) for x in peso.keys()] #Ordenar S por pesos | |
A = set() | |
for _, x in sorted(S, reverse = True): | |
if es_independiente(A | {x}): | |
A.add(x) | |
return A | |
def planificar(d, w): | |
def plan_canonico(A): | |
P = list(A) | |
P.sort(key = lambda i: d[i]) #Ordenar por tiempo limite | |
return P | |
def tareas_independientes(A): #Subrutina usada en el algoritmo voraz | |
P = plan_canonico(A) | |
for t, i in enumerate(P, 1): | |
if d[i] < t: #¿La tarea i no se completó a tiempo? | |
return False | |
return True | |
n = len(d) | |
if n != len(w) or any(not 1 <= d[i] <= n for i in range(n)): | |
raise ValueError('Instancia no válida') | |
peso = {i:w[i] for i in range(len(w))} | |
return plan_canonico(voraz(peso, tareas_independientes)) | |
if __name__ == '__main__': | |
from random import shuffle, randint | |
## Árboles generadores de peso mínimo | |
G = Grafo.aleatorio(7, 0.75, dirigido = False, pesos = range(1, 6)) | |
print('Un grafo ponderado aleatorio:') | |
print(G) | |
print() | |
print('Árbol encontrado por el algoritmo de Prim:') | |
print(Grafo.arbol(prim(G, 'A'))) | |
print() | |
print('Árbol encontrado por el algoritmo de Kruskal:') | |
print(Grafo(V = G.vertices, E = kruskal(G), dirigido = False)) | |
print() | |
## El problema de conjunto de cobertura y su aproximación voraz | |
S = [set(randint(0, 7) for j in range(randint(1, 10))) for i in range(10)] | |
print('Instancia del problema de conjunto de cobertura:') | |
B = set() | |
for i, X in enumerate(S): | |
print('S[{}] = {}'.format(i, X)) | |
B.update(X) | |
print('B =', B) | |
print('Conjunto de cobertura elegido vorazmente:') | |
print(', '.join('S[{}]'.format(i) for i in cobertura_voraz(B, S))) | |
print() | |
## El matroide del problema de planificación de tareas de tiempo unitario | |
## con penalizaciones y fechas límite | |
n = 7 | |
d = list(range(1, n + 1)) | |
shuffle(d) | |
w = [randint(1,9) for i in range(n)] | |
print() | |
print('Instancia del problema de planificación:') | |
print('i =', list(range(0, n))) | |
print('d =', d) | |
print('w =', w) | |
print() | |
print('La solución voraz selecciona el siguiente plan de tareas:') | |
print(planificar(d, w)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment