Dependency Algorithm - find a minimum set of packa

Question

I'm working on an algorithm which goal is to find a minimum set of packages to install package "X".

I'll explain better with an example:

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

The solution is to install: A E B Y.

Here is an image to describe the example:

Is there an algorithm to solve the problem without using a brute-force approach?

I've already read a lot about algorithms such as DFS, BFS, Dijkstra, etc... The problem is that these algorithms are unable to handle the "OR" condition.

UPDATE

I don't want to use external libraries.

The algorithm doesn't have to handle circular dependencies.

UPDATE

One possible solution could be to calculate all the possible paths of each vertex and, for each vertex in the possible path, doing the same. So, the possible path for X would be (A E),(A C). Now, for each element in those two possible paths we can do the same: A = (E H),(E Y) / E = (B Z),(B Y), and so on... At the end we can combine the possible paths of each vertex in a SET and choose the one with minimum length.

What do you think?

Answer 1

"I dint get the problem with "or" (the image is not loading for me). Here is my reasoning . Say we take standard shortest route algo like Dijkstras and then use equated weightage to find the best path . Taking your example Select the best Xr from below 2 options

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

where Ar = is the best option from the tree A=H(and subsequent child's) or A=Y(and subsequent childs)

The idea is to first assign standard weight for each or option (since and option is not a problem) . And later for each or option we repeat the process with its child nodes till we reach no more or option .

However , we need to first define , what best choice means, assume that least number of dependencies ie shortest path is the criteria . The by above logic we assign weight of 1 for X. There onwards

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

Hope this clears it . Also we need to take care of cyclical dependencies X=>Y=>Z=>X , here we may assign such nodes are zero at parent or leaf node level and take care of dependecy."

Answer 2

My code is here.

Scenario:

Represent the constraints.

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

Prepare two variables target and result. Add the node X to target.

target = X, result=[]

Add single node X to the result. Replace node X with its dependent in the target.

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

Add single node A to result. Replace node A with its dependent in the target.

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

Single node E must be true. So (E|C) is always true. Remove it from the target.

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

Add single node E to result. Replace node E with its dependent in the target.

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

Add single node B to result. Replace node B with its dependent in the target.

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

There are no single nodes any more. Then expand the target expression.

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

Replace Y&Y to Y.

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

Choose the term that has smallest number of nodes. Add all nodes in the term to the target.

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

Answer 3

This is an example of a Constraint Satisfaction Problem. There are Constraint Solvers for many languages, even some that can run on generic 3SAT engines, and thus be run on GPGPU.

Answer 4

To add to Misandrist's answer: your problem is NP-complete NP-hard (see dened's answer).

Edit: Here is a direct reduction of a Set Cover instance (U,S) to your "package problem" instance: make each point z of the ground set U an AND requirement for X. Make each set in S that covers a point z an OR requirement for z. Then the solution for package problem gives the minimum set cover.

Equivalently, you can ask which satisfying assignment of a monotone boolean circuit has fewest true variables, see these lecture notes.

Answer 5

Unfortunately, there is little hope to find an algorithm which is much better than brute-force, considering that the problem is actually NP-hard (but not even NP-complete).

A proof of NP-hardness of this problem is that the minimum vertex cover problem (well known to be NP-hard and not NP-complete) is easily reducible to it:

Given a graph. Let's create package P_v for each vertex v of the graph. Also create package X what "and"-requires (P_u or P_v) for each edge (u, v) of the graph. Find a minimum set of packages to be installed in order to satisfy X. Then v is in the minimum vertex cover of the graph iff the corresponding package P_v is in the installation set.

Answer 6

Another (fun) way to solved this issue is to use a genetic algorithm.

Genetic Algorithm is powerful but you have to use a lot of parameters and find the better one.

Genetic Step are the following one :

a . Creation : a number of random individual, the first generation (for instance : 100)

b. mutation : mutate of low percent of them (for instance : 0,5%)

c. Rate : rate (also call fitness) all the individual.

d. Reproduction : select (using rates) pair of them and create child (for instance : 2 child)

e. Selection : select Parent and Child to create a new generation (for instance : keep 100 individual by generation)

f. Loop : Go back to step "a" and repeat all the process a number of time (for instance : 400 generation)

g. Pick : Select an individual of the last generation with a max rate. Individual will be your solution.

Here is what you have to decide :

1. Find a genetic code for your individual

You have to represent a possible solution (call individual) of your problem as a genetic code.

In your case, it could be a group of letter representing the node which respect constraint OR and NOT.

For instance :

[ A E B Y ], [ A C K H ], [A E Z B Y] ...

2. Find a way to rate individual

To know if an individual is a good solution, you have to rate it, in order to compare it to other individual.

In your case, it could be pretty easy : individual rate = number of node - number of individual node

For instance :

[ A E B Y ] = 8 - 4 = 4

[ A E Z B Y] = 8 - 5 = 3

[ A E B Y ] as a better rate than [ A E Z B Y ]

3. Selection

Thanks to individual's rate, we can select Pair of them for reproduction.

For instance by using Genetic Algorithm roulette wheel selection

4. Reproduction

Take a pair of individual an create some (for instance 2) child (other individual) from them.

For instance :

Take a node from the first one and swap it with a node of the second one.

Make some adjustment to fit "or, and" constraint.

[ A E B Y ], [ A C K H ] => [ A C E H B Y ], [ A E C K B Y]

Note : that this is not the good way to reproduct it because the child are worth than the parent. Maybe we can swap a range of node.

5. Mutation

You have just to change genetic code of select individual.

For instance :

• Delete a node

• Make some adjustment to fit "or, and" constraint.

As you can see, it's not hard to implements but a lot of choice has to be done for designing it with a specific issue and to control the different parameters (percent of mutation, rate system, reproduction system, number of individual, number of generation, ...)