Is the fuzzy representative system decidable effectively?

Question

We have sets S ₁ , S ₂ , ..., S _n sub>. These sets should not be disjoint. Our task is to choose a representative element for each set so that the total number of selected elements is as small as possible. One element may be present in more than one set and may represent all sets included in it. Is there an algorithm for an effective solution?

Answer 1

It is easier to answer this question after recounting: let the initial sets S ₁ , S ₂ , ..., S _n be elements of the universe and let the initial elements of the set themselves be established: T ₁ , T ₂ , ..., T _m (where T _i contains the elements { S _j }, which are the source sets containing the corresponding element).

Now we need to cover the universe S ₁ , S ₂ , ..., S _n with the sets T ₁ , T ₂ ..., T _m . What exactly Ask a cover issue . This is a well-known NP-hard problem, so there is no algorithm for its effective solution (if only P = NP, as theoreticians usually say). As can be seen on the Wikipedia page, there is an algorithm for greedy approximation; it is effective, but the zoom ratio is not very good.

Answer 2

Not to steal the fame of Eugene, but here is a rather simple way to show, perhaps more strictly, that the general case of problems with the NP-hard poster.

Consider the minimal vertex hull of the problem of finding the minimal set X from vertices V to a simple graph ( V , E ), where each edge in E is adjacent to at least one vertex in X.

An edge can be represented by an unordered two-element set { v _a , v _b } where v _a and v _b are different elements in V. Note that an edge e represented as { v _a , v _b } next to v _c if and only if v _c is an element of { v _a , v _b }.

Therefore, the problem of the minimum coverage of vertices is the same as the search for a subset of the minimum size X of V , where each set of edges { v _a , v _b } defined by an edge in E contains an element that is in X>.

If you have an algorithm for effectively solving the original stated problem, then it has an algorithm for effectively solving the above problem, and therefore you can effectively solve the problem of minimum vertex coverage.

Answer 3

I assume that you mean "efficiently" in polynomial time.

Evgeni Klyuyev is right, the problem is NP-hard. Its version of the solution is known as a problem with a set of problems , and it has been shown that we now call NP-completed shortly after the introduction of this concept.Although it is true that Eugene’s reduction from the problem of getting into a given cover problem, it is easy to see an explicit reverse decrease.

Given the set C = {C ₁ , C ₂ , ... C _m } whose union U = {u ₁ , u ₂ , ..., u _n }, we want to find a subset of the minimal cardinality C 'whose union is also equal to U. Define S _i in your initial problem as {C _j in C | u _i is an element of C _j }. The minimum set of strokes S = {S ₁ , S ₂ , ..., S _n } is then equal to our desired C '.

Answer 4

A few algorithms that you should pay attention to are simulated annealing and genetic algorithms, if you can live with the optimal solution (they can get the optimal solution, but not necessarily). Simulated annealing can be done to work in the production of electronic CAD (as I was part of the Wintek autoplacement developers team).