Inicio / Apuntes / Diseño e Ingeniería /

Algoritmos de Ordenamiento y Grafos: Eficiencia y Aplicaciones

Diseño e Ingeniería9,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:

  1. Mochila y Archivos: Problemas de optimización donde se busca maximizar el valor de los objetos seleccionados sin exceder una capacidad.
  2. Cambio y ANA: Problemas de programación dinámica para encontrar la combinación óptima de monedas o recursos.
  3. Cómic y PDF: Podría relacionarse con la compresión o el procesamiento de archivos.
  4. Cultivos y Calorías: Optimización de la selección de cultivos para maximizar el valor nutricional o calórico.
  5. Agua: Podría referirse a problemas de flujo de redes o distribución de recursos hídricos.
  6. Partición Mitad y Cambio: Algoritmos para problemas de división equitativa y cambio de monedas.
  7. Ruta Aérea con Menos Escalas: Aplicación de algoritmos de grafos para encontrar la ruta óptima.
  8. Procesadores y Tareas: Problemas de asignación de tareas a procesadores para minimizar el tiempo total.
  9. Hamiltonianos: Encontrar ciclos hamiltonianos en un grafo (ciclo que visita cada nodo una sola vez).

Descargar

PDF Word HTML