ESIT ULL Grado de Informática

DISEÑO Y ANÁLISIS DE ALGORITMOS. Implementación de algoritmos constructivos y búsquedas por entornos para el Max-Mean Dispersion Problem.

Realizada por Eduardo Escobar Alberto.

Descripción del Max-Mean Dispersion Problem

Sea dado un grafo completo G = (V, E), donde V es el conjunto de vértices (|V| = n) y E es el conjunto de aristas (|E| = n(n − 1)/2. Cada arista (i, j) ∈ E tiene asociada una distancia o afinidad d(i, j). En el Max-Mean Dispersion Problem se desea encontrar el subconjunto de vértices S ⊆ V que maximiza la dispersión media dada por

Formato de las intancias del problema

Las instancias del problema se suministrarán en un fichero de texto con el siguiente formato:

• PRIMERA FILA: Se encuentra el número de vértices, n.
• SIGUIENTES FILAS: Se enumeran las afinidades, d(i, j), entre los pares de vértices (se asume que las afinidades son simétricas, es decir, que d(i, j) = d( j, i), ∀i, j ∈ V. Además, d(i, i) = 0, ∀i ∈ V).

Algoritmos implementados

• Constructivo voraz.
• Destructivo voraz.
• GRASP.
• Método Multiarranque.
• Búsqueda por Entorno Variable.

Las tablas y gráficas con los resultados se encuentran en el fichero Informe.pdf