Algoritmos de Ordenamiento y Grafos: Eficiencia y Aplicaciones
Clasificado en Diseño e Ingeniería
Escrito el en 
español con un tamaño de 9,05 KB
Algoritmos de Ordenamiento
QuickSort
QuickSort tiene una complejidad en el peor caso de O(n2), que ocurre cuando el pivote elegido resulta ser el elemento más pequeño o más grande del subconjunto. La ecuación de recurrencia es T(n-1) + n + c.
Pseudocódigo:
Si (#S = 0 o #S1 = 1)
res <- S
Sino
pivote <- S[1]
Para cada Valor de S[2...inf]
Si Valor < pivote
S1 <- S1 + Valor
Sino
S2 <- S2 + Valor
res <- QuickSort(S1) + pivote + QuickSort(S2)
MergeSort
MergeSort tiene una complejidad de O(n log n). La ecuación de recurrencia es 2T(n/2) + n + c.
Pseudocódigo Merge (O(n)):
S3 <- []
I <- 1
J <- 1
Para k <- 1 hasta (#S1 + #S2)
Si S1aux[i] < S2aux[j]
S3 <- S3 + S1aux[i]
i <- i + 1
Sino
S3 <- S3 + S2aux[j]
j <- j + 1
Fin Si
Fin Para
Devolver S3
Pseudocódigo MergeSort:
Entrada: S: Vector, inicio: entero, fin: entero
Si inicio < fin
medio <- (fin + inicio) / 2
MergeSort(S, inicio, medio)
MergeSort(S, medio + 1, fin)
Merge(S, inicio, fin)
Fin Si
Algoritmos de Grafos
Algoritmo de Floyd
El algoritmo de Floyd encuentra la distancia mínima entre todos los pares de vértices en un grafo. Se basa en la programación dinámica.
Pseudocódigo (versión simplificada):
Se parte de una matriz M0 donde tenemos la mejor forma de llegar de cada vértice a todos los demás sin pasar por ningún vértice intermedio e iremos encontrando las matrices intermedias M1, M2 hasta llegar a Mn, donde n es la cantidad de vértices del grafo. M0 estará inicializado con 0 en su diagonal, el valor de la arista en el grafo original cuando exista arista o ∞ si no existe arista. Luego Mk se calculará como sigue: Mk[i,j] = min(Mk-1[i, j], Mk-1[i, k] + Mk-1[k, j]) El costo de este algoritmo está dado por el costo de los tres ciclos, que está en O(n3)
Pseudocódigo (versión detallada):
Entrada: G (grafo de entrada)
Salida: R (grafo con una arista con la distancia mínima entre cada par de vértices)
inicializarGrafo(R)
copiarGrafo(G, R)
VerticesK = Vertices(G)
Para cada k de VerticesK
VerticesI = Vertices(G)
Para cada i de VerticesI
VerticesJ = Vertices(G)
Para cada j de VerticesJ
Si i != j Y existeArista(R, i, k) Y existeArista(R, k, j)
Si existeArista(R, i, j)
Si pesoArista(R, i, k) + pesoArista(R, k, j) < pesoArista(R, i, j)
agregarArista(R, i, j, pesoArista(R, i, k) + pesoArista(R, k, j))
Fin Si
Sino
agregarArista(R, i, j, pesoArista(R, i, k) + pesoArista(R, k, j))
Fin Si
Fin Si
Fin Para
Fin Para
Fin Para
Devolver R
Algoritmo de Kruskal
El algoritmo de Kruskal encuentra el árbol de expansión mínima (MST) de un grafo. Se basa en la idea de ir uniendo árboles más pequeños hasta formar un único árbol.
Pseudocódigo:
Entrada: Grafo G(V, A) // V: vértices, A: aristas
Salida: Grafo (árbol de expansión mínima)
Dic <- {}
Particion <- {}
Para cada vértice en G.V
Dic[Vertice] <- Particion
Fin Para
Aristas <- OrdenarAristas(G.A) // Ordenar aristas por peso de menor a mayor
Gaux <- (V[], A[])
Para cada arista en Aristas
Si Dic[arista.origen] != Dic[arista.destino]
Dic <- UnirParticiones(Dic, arista)
Gaux.A <- Gaux.A + [arista]
// Gaux.V <- Gaux.V + [arista.origen, arista.destino] // No es necesario añadir explícitamente los vértices
Fin Si
Fin Para
// *Verificar si es conexo (opcional)*
// esConexo <- Verdadero
// Para cada val en Dic[2..inf]
// Si valor != val[1]
// esConexo <- Falso
// Fin Si
// Fin Para
Devolver Gaux // o pesoAcumulado (si se calcula) o esConexo
Pseudocódigo de la función UnirParticiones:
Entrada: Diccionario DIC (vértice como clave, número de partición como valor), arista a (con origen y destino)
Salida: Diccionario actualizado
MIN <- min(Dic[arista.origen], Dic[arista.destino]) // Opcional: optimización
Para cada vértice en DIC
Si Dic[vértice] = Dic[arista.origen] o Dic[vértice] = Dic[arista.destino]
Dic[vértice] <- MIN
Fin Si
Fin Para
Devolver Dic
Algoritmo de Dijkstra
El algoritmo de Dijkstra encuentra el camino más corto desde un nodo origen a todos los demás nodos en un grafo con pesos no negativos.
Pseudocódigo (camino mínimo a todos los nodos):
Entrada: Grafo G(V, A), Vértice origen
Salida: Diccionario (costo mínimo para llegar a cada vértice)
Dic <- {}
Para cada v en G.V
Dic[v] <- ∞
Fin Para
Dic[origen] <- 0
Visitados <- []
Mientras #Visitados < #G.V
min <- ∞
vertice <- null
Para cada val en DIC
Si (DIC[val] < min) Y (val no en Visitados)
min <- DIC[val]
vertice <- val
Fin Si
Fin Para
Visitados <- Visitados + [vertice]
Para cada a en G.A
Si a.origen = vertice
Si Dic[vertice] + a.peso < Dic[a.destino]
Dic[a.destino] <- Dic[vertice] + a.peso
Fin Si
Fin Si
Fin Para
Fin Mientras
Devolver DIC
Pseudocódigo (camino mínimo a un nodo destino específico):
Entrada: Grafo G(V, A), Vértice origen, Vértice destino
Salida: Diccionario (costo mínimo para llegar al destino)
Dic <- {}
DicAux <- {}
Para cada v en G.V
Dic[v] <- ∞
Fin Para
Dic[origen] <- 0
Visitados <- []
Mientras #Visitados < #G.V
min <- ∞
vertice <- null
Para cada val en DIC
Si (DIC[val] < min) Y (val no en Visitados)
min <- DIC[val]
vertice <- val
Fin Si
Fin Para
Visitados <- Visitados + [vertice]
Si vertice = destino
devolver DicAux
finsi
Para cada a en G.A
Si a.origen = vertice
Si Dic[vertice] + a.peso < Dic[a.destino]
DicAux[a.destino] <- Dic[vertice] + a.peso
Dic[a.destino] <- Dic[vertice] + a.peso
Fin Si
Fin Si
Fin Para
Fin Mientras
Devolver DicAux
Algoritmo de Prim
El algoritmo de Prim encuentra el árbol de expansión mínima (MST) de un grafo, similar a Kruskal. La diferencia principal radica en cómo se construye el árbol.
Pseudocódigo:
Entrada: G(V, A)
Salida: Grafo (árbol de expansión mínima) // o PesoAcumulado o esConexo
Gaux <- (G.V, [])
F <- [un vértice inicial de G.V] // Conjunto de vértices en el árbol en construcción
PI <- G.V - F // Conjunto de vértices restantes
Mientras #PI > 0
min <- ∞
mejorArista <- null
Para cada origen en F
Para cada destino en PI
Para cada arista en G.A
Si arista.orig = origen Y arista.dest = destino
Si arista.peso < min
min <- arista.peso
mejorArista <- arista
Fin Si
Fin Si
Fin Para
Fin Para
Fin Para
F <- F + [mejorArista.destino]
Gaux.A <- Gaux.A + [mejorArista]
PI <- PI - [mejorArista.destino]
Fin Mientras
// *Verificar si es conexo (opcional)*
// Si #PI > 0
// res <- No es conexo
Devolver Gaux // o pesoAcumulado o esConexo
Tabla Resumen de Aplicaciones
Se presentan a continuación posibles aplicaciones de los algoritmos vistos:
- Mochila y Archivos: Problemas de optimización donde se busca maximizar el valor de los objetos seleccionados sin exceder una capacidad.
- Cambio y ANA: Problemas de programación dinámica para encontrar la combinación óptima de monedas o recursos.
- Cómic y PDF: Podría relacionarse con la compresión o el procesamiento de archivos.
- Cultivos y Calorías: Optimización de la selección de cultivos para maximizar el valor nutricional o calórico.
- Agua: Podría referirse a problemas de flujo de redes o distribución de recursos hídricos.
- Partición Mitad y Cambio: Algoritmos para problemas de división equitativa y cambio de monedas.
- Ruta Aérea con Menos Escalas: Aplicación de algoritmos de grafos para encontrar la ruta óptima.
- Procesadores y Tareas: Problemas de asignación de tareas a procesadores para minimizar el tiempo total.
- Hamiltonianos: Encontrar ciclos hamiltonianos en un grafo (ciclo que visita cada nodo una sola vez).