Prerrequisito: NP Completo Problema : dado un conjunto base X de elementos y también una colección de agrupación C de subconjuntos disponibles en X y un número entero k , la tarea es encontrar el subconjunto más pequeño de X , tal que el subconjunto más pequeño, H ,coincida con todos los conjuntos comprendidos en … Continue reading «El problema del conjunto de golpes es NP completo»
Problema de isomorfismo de subgrafos : Tenemos dos grafos no dirigidos G 1 y G 2 . El problema es comprobar si G 1 es isomorfo a un subgrafo de G 2 . Isomorfismo de grafos: dos grafos A y B son isomorfos entre sí si tienen el mismo número de vértices y aristas, y … Continue reading «Prueba de que el problema de isomorfismo de subgrafo es NP-Completo»
Requisito previo: NP-Completo , problema de camarilla . Una camarilla en un gráfico es un conjunto de vértices donde cada vértice comparte un borde con todos los demás vértices. Así, una camarilla en un grafo es un subgrafo que es un grafo completo. Problema: Dada una gráfica G(V, E) y un entero K, el problema … Continue reading «Prueba de que el problema de decisión de camarilla es NP-Complete | conjunto 2»
Prerrequisito: Conjunto Dominante de un Gráfico , NP-Completo Un conjunto dominante en un grafo G = (V, E) es un subconjunto de vértices V’ siguiendo la condición de que los vértices que no pertenecen a V’ sean adyacentes a algún vértice en V’ . Problema: Dado un grafo G(V, E) y un entero k, el … Continue reading «Prueba de que el conjunto dominante de un gráfico es NP-completo»
Requisito previo: NP-Completitud Problema NP: El conjunto de problemas NP cuyas soluciones son difíciles de encontrar pero fáciles de verificar y se resuelven mediante una máquina no determinista en tiempo polinomial. Problema NP-Difícil : Un problema X es NP-Difícil si hay un problema NP-Completo Y, tal que Y es reducible a X en tiempo polinomial. … Continue reading «Diferencia entre problema NP difícil y NP completo»
Descripción del problema : El Problema de la Galería de Arte se formula en geometría como el número mínimo de guardias que deben colocarse en un polígono simple de n vértices de manera que todos los puntos del interior sean visibles. Un polígono simple es una región cerrada conectada cuyo límite está definido por un … Continue reading «Problema de la galería de arte»
Problema del viajante de comercio (TSP): Dado un conjunto de ciudades y la distancia 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 … Continue reading «Problema del vendedor ambulante | Set 1 (Programación Ingenua y Dinámica)»
Problema : Dado un Conjunto base X , un entero k , y una colección de subconjuntos Si de X , el problema es identificar si existe una colección de subconjuntos cuya unión sea X , con tamaño a lo sumo k . Prueba: una instancia del problema es una entrada especificada para el problema. … Continue reading «La cubierta del juego es NP Complete»
Presentamos el problema del vendedor ambulante y discutimos las soluciones de programación ingenua y dinámica para el problema en la publicación anterior . Ambas soluciones son inviables. De hecho, no existe una solución de tiempo polinomial disponible para este problema, ya que se trata de un problema NP-Hard conocido. Sin embargo, existen algoritmos aproximados para … Continue reading «Problema del vendedor ambulante | Conjunto 2 (Aproximado usando MST)»
Dado un universo U de n elementos, una colección de subconjuntos de U digamos S = {S 1 , S 2 …,S m } donde cada subconjunto S i tiene un costo asociado. Encuentre una subcolección de costo mínimo de S que cubra todos los elementos de U. Ejemplo: U = {1,2,3,4,5} S = {S1,S2,S3} … Continue reading «Establecer problema de portada | Conjunto 1 (algoritmo aproximado codicioso)»