Categoría: NPHard

Problema de cobertura de vértices | Set 2 (Solución de Programación Dinámica para Tree)

Posted on by Rudeus Greyrat

Una cubierta de vértices de un gráfico no dirigido es un subconjunto de sus vértices, de modo que para cada borde (u, v) del gráfico, ‘u’ o ‘v’ están en la cubierta de vértices. Aunque el nombre es Vertex Cover, el conjunto cubre todos los bordes del gráfico dado. El problema para encontrar la cobertura de … Continue reading «Problema de cobertura de vértices | Set 2 (Solución de Programación Dinámica para Tree)»

Problema de la supercuerda más corta

Posted on by Rudeus Greyrat

Dado un conjunto de n strings arr[], encuentra la string más pequeña que contiene cada string en el conjunto dado como substring. Podemos suponer que ninguna string en arr[] es una substring de otra string. Ejemplos:  Input: arr[] = {«geeks», «quiz», «for»} Output: geeksquizfor Input: arr[] = {«catg», «ctaagt», «gcta», «ttca», «atgcatc»} Output: gctaagttcatgcatc Algoritmo … Continue reading «Problema de la supercuerda más corta»

Prueba de que la cobertura de vértices es NP completa

Posted on by Rudeus Greyrat

Requisito previo: problema de cobertura de vértices , problema de NP-completitud : dado un gráfico G (V, E) y un número entero positivo k, el problema es encontrar si hay un subconjunto V ‘de vértices de tamaño como máximo k, tal que cada borde en el gráfico está conectado a algún vértice en V’. Explicación: … Continue reading «Prueba de que la cobertura de vértices es NP completa»

Prueba de que el conjunto independiente en la teoría de grafos es NP completo

Posted on by Rudeus Greyrat

Requisito previo: NP-Completo , Conjunto independiente . Un Conjunto Independiente S del gráfico G = (V, E) es un conjunto de vértices tales que no hay dos vértices en S adyacentes entre sí. Consta de vértices no adyacentes. Problema: Dada una gráfica G(V, E) y un entero k, el problema es determinar si la gráfica … Continue reading «Prueba de que el conjunto independiente en la teoría de grafos es NP completo»

NP-Completitud | Serie 1 (Introducción)

Posted on by Rudeus Greyrat

  Hemos estado escribiendo sobre algoritmos eficientes para resolver problemas complejos, como la ruta más corta , el gráfico de Euler , el árbol de expansión mínimo , etc. Todas esas fueron historias de éxito de diseñadores de algoritmos. En esta publicación, se discuten las historias de fallas de la informática.  ¿Todos los problemas computacionales … Continue reading «NP-Completitud | Serie 1 (Introducción)»

Implementación del problema del viajante de comercio (TSP)

Posted on by Rudeus Greyrat

Problema del viajante de comercio (TSP): dado un conjunto de ciudades y distancias entre cada par de ciudades, el problema es encontrar la ruta más corta posible que visite cada ciudad exactamente una vez y regrese al punto de partida. Tenga en cuenta la diferencia entre el ciclo hamiltoniano y TSP. El problema del ciclo hamiltoniano … Continue reading «Implementación del problema del viajante de comercio (TSP)»

Problema de cobertura de vértices | Conjunto 1 (Introducción y Algoritmo Aproximado)

Posted on by Rudeus Greyrat

Una cubierta de vértices de un gráfico no dirigido es un subconjunto de sus vértices, de modo que para cada borde (u, v) del gráfico, ‘u’ o ‘v’ están en la cubierta de vértices. Aunque el nombre es Vertex Cover, el conjunto cubre todos los bordes del gráfico dado. Dado un gráfico no dirigido, el … Continue reading «Problema de cobertura de vértices | Conjunto 1 (Introducción y Algoritmo Aproximado)»

Problema de Cobertura Exacta y Algoritmo X | Serie 1

Posted on by Rudeus Greyrat

Si alguna vez ha intentado crear un programa para resolver Sudoku , es posible que se haya topado con el problema de Exact Cover . En este artículo, discutiremos cuál es el problema de la cobertura exacta y un algoritmo “Algoritmo X” propuesto por Donald Knuth para resolver este problema. Dada una colección S de … Continue reading «Problema de Cobertura Exacta y Algoritmo X | Serie 1»

Problema de Cobertura Exacta y Algoritmo X | Set 2 (Implementación con DLX)

Posted on by Rudeus Greyrat

En el artículo Problema de Cobertura Exacta y Algoritmo X | En el Conjunto 1 discutimos el problema de Cobertura Exacta y el Algoritmo X para resolver el problema de Cobertura Exacta. En este artículo, discutiremos los detalles de implementación del Algoritmo X usando la Técnica de Enlaces Danzantes (DLX) propuesta por el Dr. Donald … Continue reading «Problema de Cobertura Exacta y Algoritmo X | Set 2 (Implementación con DLX)»

Prueba de que el problema de decisión de camarilla es NP-Completo

Posted on by Rudeus Greyrat

Requisito previo: NP-Completitud Una camarilla es un subgrafo de un grafo tal que todos los vértices en este subgrafo están conectados entre sí, es decir, el subgrafo es un grafo completo. El problema de la camarilla máxima es encontrar la camarilla de tamaño máximo de un gráfico G dado, que es un gráfico completo que … Continue reading «Prueba de que el problema de decisión de camarilla es NP-Completo»