Algoritmo de dependencia: encuentre un conjunto mínimo de paquetes para instalar

Estoy trabajando en un algoritmo cuyo objective es encontrar un conjunto mínimo de paquetes para instalar el paquete “X”.

Te lo explicaré mejor con un ejemplo:

X depends on A and (E or C) A depends on E and (H or Y) E depends on B and (Z or Y) C depends on (A or K) H depends on nothing Y depends on nothing Z depends on nothing K depends on nothing 

La solución es instalar: AEB Y.

Aquí hay una imagen para describir el ejemplo:

¿Existe un algoritmo para resolver el problema sin utilizar un enfoque de fuerza bruta?

    Ya he leído mucho sobre algoritmos como DFS, BFS, Dijkstra, etc. El problema es que estos algoritmos no pueden manejar la condición “O”.

    ACTUALIZAR

    No quiero usar bibliotecas externas.

    El algoritmo no tiene que manejar dependencias circulares.

    ACTUALIZAR

    Una posible solución podría ser calcular todas las rutas posibles de cada vértice y, para cada vértice en la ruta posible, hacer lo mismo. Por lo tanto, el camino posible para X sería (AE), (AC). Ahora, para cada elemento en esos dos caminos posibles podemos hacer lo mismo: A = (EH), (EY) / E = (BZ), (BY), y así sucesivamente … Al final podemos combinar lo posible Rutas de cada vértice en un SET y elija la que tenga la longitud mínima.

    ¿Qué piensas?

    Desafortunadamente, hay pocas esperanzas de encontrar un algoritmo que sea mucho mejor que la fuerza bruta, considerando que el problema es en realidad NP-duro (pero ni siquiera NP-completo ).

    Una prueba de la dureza NP de este problema es que el problema de cobertura de vértice mínimo (bien conocido por ser NP-duro y no NP-completo) es fácilmente reducible:

    Dada una gráfica. Vamos a crear el paquete P v para cada vértice v de la gráfica. También cree el paquete X que “y” -requiere ( P u o P v ) para cada borde (u, v) del gráfico. Encuentre un conjunto mínimo de paquetes a instalar para satisfacer X. Entonces v está en la cubierta de vértice mínima del gráfico si el paquete correspondiente P v está en el conjunto de instalación.

    “No quiero resolver el problema con” o “(la imagen no se está cargando para mí). Aquí está mi razonamiento. Supongamos que tomamos una ruta estándar más corta como Dijkstras y luego usamos un peso equivalente para encontrar el mejor camino. Tomando su ejemplo Seleccione el mejor Xr de debajo de 2 opciones

     Xr= X+Ar+Er Xr= X+Ar+Cr 

    donde Ar = es la mejor opción del árbol A = H (y subsiguiente del niño) o A = Y (y subsiguientes del niño)

    La idea es asignar primero el peso estándar para cada opción u (ya que la opción no es un problema). Y más adelante, para cada opción o opción, repetimos el proceso con sus nodos secundarios hasta que no alcanzamos más opciones.

    Sin embargo, primero debemos definir qué significa la mejor elección, asumir que el criterio es el menor número de dependencias, es decir, la ruta más corta. A la lógica anterior le asignamos un peso de 1 para X. A partir de ahí

     X=1 X=A and E or C hence X=A1+E1 and X=A1+C1 A= H or Y, assuming H and Y are leaf node hence A get final weight as 1 hence , X=1+E1 and X=1+C1 Now for E and C E1=B1+Z1 and B1+Y1 . C1=A1 and C=K1. Assuming B1,Z1,Y1,A1and K1 are leaf node E1=1+1 and 1+1 . C1=1 and C1=1 ie E=2 and C=1 Hence X=1+2 and X=1+1 hence please choose X=>C as the best route 

    Espero que esto se aclare. También debemos cuidar las dependencias cíclicas X => Y => Z => X, aquí podemos asignar que los nodos son cero en el nivel del nodo principal o del nodo de hoja y cuidamos la dependencia “.

    Realmente creo que los gráficos son la estructura apropiada para este problema. Tenga en cuenta que A y (E o C) <==> (A y E) o (A y C). Por lo tanto, podemos representar X = A y (E o C) con el siguiente conjunto de bordes dirigidos:

     A <- K1 E <- K1 A <- K2 C <- K2 K1 <- X K2 <- X 

    Básicamente, solo estamos descomponiendo la lógica de la statement y usando nodos "ficticios" para representar los AND.

    Supongamos que descomponemos todas las declaraciones lógicas de esta manera (nodos Ki ficticios para ANDS y bordes dirigidos de lo contrario). Entonces, podemos representar la entrada como un DAG y recorrer recursivamente el DAG. Creo que el siguiente algoritmo recursivo podría resolver el problema:

    Definiciones:
    Nodo u - Nodo actual.
    S - El conjunto de nodos visitados.
    children (x) - Devuelve los vecinos de x.

    Algoritmo:

     shortestPath u S = if (u has no children) { add u to S return 1 } else if (u is a dummy node) { (a,b) = children(u) if (a and b are in S) { return 0 } else if (b is in S) { x = shortestPath a S add a to S return x } else if (a in S) { y = shortestPath b S add b to S return y } else { x = shortestPath a S add a to S if (b in S) return x else { y = shortestPath b S add b to S return x + y } } } else { min = Int.Max min_node = m for (x in children(u)){ if (x is not in S) { S_1 = S k = shortestPath x S_1 if (k < min) min = k, min_node = x } else { min = 1 min_node = x } } return 1 + min } 

    Análisis: este es un algoritmo completamente secuencial que (creo) atraviesa cada borde como máximo una vez.

    Muchas de las respuestas aquí se centran en cómo este es un problema teóricamente difícil debido a su estado NP-difícil. Si bien esto significa que experimentará un rendimiento asintóticamente deficiente al resolver el problema exactamente (dadas las técnicas de solución actuales), es posible que aún pueda resolverlo rápidamente (lo suficiente) para los datos de su problema en particular. Por ejemplo, somos capaces de resolver exactamente enormes casos de problemas de vendedores ambulantes a pesar de que el problema es teóricamente desafiante.

    En su caso, una forma de resolver el problema sería formularlo como un progtwig lineal de enteros mixtos, donde hay una variable binaria x_i para cada paquete i . Puede convertir los requisitos A requires (B or C or D) and (E or F) and (G) a restricciones de la forma x_A <= x_B + x_C + x_D ; x_A <= x_E + x_F ; x_A <= x_G x_A <= x_B + x_C + x_D ; x_A <= x_E + x_F ; x_A <= x_G x_A <= x_B + x_C + x_D ; x_A <= x_E + x_F ; x_A <= x_G , y puede requerir que se incluya un paquete P en la solución final con x_P = 1 . Resolver un modelo así exactamente es relativamente sencillo; por ejemplo, puedes usar el paquete de pulpa en python:

     import pulp deps = {"X": [("A"), ("E", "C")], "A": [("E"), ("H", "Y")], "E": [("B"), ("Z", "Y")], "C": [("A", "K")], "H": [], "B": [], "Y": [], "Z": [], "K": []} required = ["X"] # Variables x = pulp.LpVariable.dicts("x", deps.keys(), lowBound=0, upBound=1, cat=pulp.LpInteger) mod = pulp.LpProblem("Package Optimization", pulp.LpMinimize) # Objective mod += sum([x[k] for k in deps]) # Dependencies for k in deps: for dep in deps[k]: mod += x[k] <= sum([x[d] for d in dep]) # Include required variables for r in required: mod += x[r] == 1 # Solve mod.solve() for k in deps: print "Package", k, "used:", x[k].value() 

    Esto genera el conjunto mínimo de paquetes:

     Package A used: 1.0 Package C used: 0.0 Package B used: 1.0 Package E used: 1.0 Package H used: 0.0 Package Y used: 1.0 Package X used: 1.0 Package K used: 0.0 Package Z used: 0.0 

    Para casos de problemas muy grandes, esto puede llevar demasiado tiempo resolverlo. Puede aceptar una solución potencialmente subóptima usando un tiempo de espera (consulte aquí ) o puede pasar de los solucionadores de código abierto predeterminados a un solucionador comercial como gurobi o cplex, que probablemente sea mucho más rápido.

    Para agregar a la respuesta de Misandrist: su problema es NP-completo NP-duro (vea la respuesta de dened).

    Edición: aquí hay una reducción directa de una instancia de Cobertura de conjunto (U, S) a su instancia de “problema de paquete”: haga que cada punto z del conjunto de tierra U sea un requisito AND para X. Realice cada conjunto en S que cubra un punto z un requisito de OR para z. Entonces, la solución para el problema del paquete da la cobertura mínima establecida.

    De manera equivalente, puede preguntar qué asignación satisfactoria de un circuito booleano monótono tiene la menor cantidad de variables verdaderas, consulte estas notas de clase .

    Dado que el gráfico consta de dos tipos diferentes de bordes (relación AND y OR), podemos dividir el algoritmo en dos partes: buscar todos los nodos que sean sucesores requeridos de un nodo y buscar todos los nodos de los que tenemos que seleccionar un solo nodo (O).

    Los nodos contienen un paquete, una lista de nodos que deben ser sucesores de este nodo (AND), una lista de nodos que pueden ser sucesores de este nodo (OR) y una marca que marca en qué paso del algoritmo estaba el nodo. visitó.

     define node: package p , list required , listlist optional , int visited[default=MAX_VALUE] 

    La rutina principal convierte la entrada en un gráfico y comienza el recorrido en el nodo inicial.

     define searchMinimumP: input: package start , string[] constraints output: list //generate a graph from the given constraint //and save the node holding start as starting point node r = getNode(generateGraph(constraints) , start) //list all required nodes return requiredNodes(r , 0) 

    requiredNodes busca todos los nodos que son sucesores requeridos de un nodo (que están conectados a n través de la relación AND en 1 o múltiples bordes).

     define requiredNodes: input: node n , int step output: list //generate a list of all nodes that MUST be part of the solution list rNodes list todo add(todo , n) while NOT isEmpty(todo) node next = remove(0 , todo) if NOT contains(rNodes , next) AND next.visited > step add(rNodes , next) next.visited = step addAll(rNodes , optionalMin(rNodes , step + 1)) for node r in rNodes r.visited = step return rNodes 

    optimalMin busca la solución más corta entre todas las soluciones posibles para vecinos opcionales (OR). Este algoritmo es de fuerza bruta (se inspeccionarán todas las selecciones posibles para vecinos).

     define optionalMin: input: list nodes , int step output: list //find all possible combinations for selectable packages listlist optSeq for node n in nodes if NOT n.visited < step for list opt in n.optional add(optSeq , opt) //iterate over all possible combinations of selectable packages //for the given list of nodes and find the shortest solution list shortest int curLen = MAX_VALUE //search through all possible solutions (combinations of nodes) for list seq in sequences(optSeq) list subseq for node n in distinct(seq) addAll(subseq , requiredNodes(n , step + 1)) if length(subseq) < curLen //mark all nodes of the old solution as unvisited for node n in shortest n.visited = MAX_VALUE curLen = length(subseq) shortest = subseq else //mark all nodes in this possible solution as unvisited //since they aren't used in the final solution (not at this place) for node n in subseq n.visited = MAX_VALUE for node n in shorest n.visited = step return shortest 

    La idea básica sería la siguiente: comience desde el nodo de inicio y busque todos los nodos que deben formar parte de la solución (nodos a los que se puede acceder desde el nodo de inicio solo atravesando las relaciones AND). Ahora, para todos estos nodos, el algoritmo busca la combinación de nodos opcionales (OR) con la menor cantidad de nodos necesarios.

    NOTA: hasta ahora este algoritmo no es mucho mejor que la fuerza bruta. Lo actualizaré tan pronto como encuentre un mejor enfoque.

    Mi código está aquí .

    Guión:

    Representar las restricciones.

     X : A&(E|C) A : E&(Y|N) E : B&(Z|Y) C : A|K 

    Preparar dos variables de destino y resultado. Agregue el nodo X al objective.

     target = X, result=[] 

    Agregue un solo nodo X al resultado. Reemplace el nodo X con su dependiente en el objective.

     target = A&(E|C), result=[X] 

    Agregue un solo nodo A al resultado. Reemplace el nodo A con su dependiente en el objective.

     target = E&(Y|N)&(E|C), result=[X, A] 

    El nodo único E debe ser verdadero. Entonces (E | C) siempre es cierto. Quítalo del objective.

     target = E&(Y|N), result=[X, A] 

    Agregue un solo nodo E al resultado. Reemplace el nodo E con su dependiente en el objective.

     target = B&(Z|Y)&(Y|N), result=[X, A, E] 

    Agregue un solo nodo B al resultado. Reemplace el nodo B con su dependiente en el objective.

     target = (Z|Y)&(Y|N), result=[X, A, E, B] 

    Ya no hay nodos individuales. A continuación, expanda la expresión de destino.

     target = Z&Y|Z&N|Y&Y|Y&N, result=[X, A, E, B] 

    Reemplace Y&Y por Y.

     target = Z&Y|Z&N|Y|Y&N, result=[X, A, E, B] 

    Elija el término que tenga el menor número de nodos. Agregue todos los nodos en el término al objective.

     target = , result=[X, A, E, B, Y] 

    Le sugeriría que primero transforme la gráfica en un árbol AND-OR . Una vez hecho esto, puede realizar una búsqueda en el árbol de la mejor (donde puede elegir qué significa “mejor”: la más corta, la menor ocupación de memoria de los paquetes en los nodos, etc.).

    Una sugerencia que haría, ya que la condición para instalar X sería algo como install(X) = install(A) and (install(E) or install(C)) , es agrupar los nodos OR (en este caso : E y C) en un solo nodo, digamos EC, y transforme la condición en install(X) = install(A) and install(EC) .

    Como alternativa, según la idea del árbol AND-OR, puede crear un gráfico AND-OR personalizado utilizando la idea de agrupación. De esta manera, podría utilizar una adaptación de un algoritmo de recorrido de gráficos , que podría ser más útil en ciertos escenarios.

    Otra solución más podría ser usar Forward Chaining . Tendrías que seguir estos pasos:

    1. Transformar (reescribiendo las condiciones aquí):

      A y (E o C) => X

      E y (H o Y) => A

      B y (Z o Y) => E

    dentro

     (A and E) or (A and C) => X (E and H) or (E and Y) => A (B and Z) or (B and Y) => E 
    1. Establecer X como objective.
    2. Inserte B, H, K, Y, Z como hechos.
    3. Ejecute el encadenamiento hacia adelante y deténgase en la primera aparición de X (el objective). Ese debería ser el camino más corto para lograr la meta en este caso (solo recuerde llevar un registro de los hechos que se han utilizado).

    Déjame saber si algo no está claro.

    Este es un ejemplo de un problema de satisfacción de restricciones . Existen solucionadores de restricciones para muchos idiomas, incluso algunos que pueden ejecutarse en motores generics 3SAT y, por lo tanto, ejecutarse en GPGPU.

    Otra forma (divertida) de resolver este problema es usar un algoritmo genético.

    El algoritmo genético es poderoso, pero tienes que usar muchos parámetros y encontrar el mejor.

    Los pasos genéticos son los siguientes:

    a . Creación : un número de individuos aleatorios, la primera generación (por ejemplo: 100)

    segundo. mutación : mutar de bajo porcentaje de ellos (por ejemplo: 0,5%)

    do. Tarifa : tasa (también llamada fitness) a todo el individuo.

    re. Reproducción : seleccione (use las tasas) par de ellas y cree un niño (por ejemplo: 2 niños)

    mi. Selección : seleccione Padre e hijo para crear una nueva generación (por ejemplo: mantener 100 individuos por generación)

    F. Bucle : vuelva al paso “a” y repita todo el proceso varias veces (por ejemplo: generación 400)

    sol. Selección : seleccione un individuo de la última generación con una tasa máxima. El individuo será su solución.

    Esto es lo que tienes que decidir:

    1. Encuentra un código genético para tu individuo

    Tienes que representar una posible solución (llamada individual ) de tu problema como un código genético.

    En su caso, podría ser un grupo de letras que representan el nodo que respeta la restricción OR y NOT.

    Por ejemplo :

    [AEBY], [ACKH], [AEZBY] …

    1. Encuentra una manera de calificar individual

    Para saber si una persona es una buena solución, debe calificarla para poder compararla con otra persona.

    En su caso, podría ser bastante sencillo: tasa individual = número de nodo – número de nodo individual

    Por ejemplo :

    [AEBY] = 8 – 4 = 4

    [AEZBY] = 8 – 5 = 3

    [AEBY] como una mejor tasa que [AEZBY]

    1. Selección

    Gracias a la tarifa individual, podemos seleccionar Par de ellos para su reproducción.

    Por ejemplo, utilizando la selección de la rueda de ruleta de algoritmo genético

    1. Reproducción

    Tome un par de individuos y cree algunos (por ejemplo, 2) hijos (otros individuos) de ellos.

    Por ejemplo :

    Tome un nodo del primero y cámbielo por un nodo del segundo.

    Realice algunos ajustes para ajustar “o, y” restricción.

    [A E BY], [AC K H] => [AC E HBY], [AEC K BY]

    Nota: esta no es la mejor manera de reproducirla porque el niño vale más que el padre. Tal vez podamos intercambiar un rango de nodo.

    1. Mutación

    Solo tienes que cambiar el código genético del individuo seleccionado.

    Por ejemplo :

    • Eliminar un nodo

    • Realice algunos ajustes para ajustar “o, y” restricción.

    Como puede ver, no es difícil implementarlo, pero se debe hacer mucha elección para diseñarlo con un problema específico y para controlar los diferentes parámetros (porcentaje de mutación, sistema de velocidad, sistema de reproducción, número de individuos, número de generaciones). , …)