Current location - Training Enrollment Network - Mathematics courses - Combinatorial mathematical algorithm
Combinatorial mathematical algorithm
This is a NP-complete problem.

It can be restored from another NP-complete problem, Set Cover.

Set cover page:

There are n elements in total, forming a complete set U. There are subsets S 1, S2, ... Find the smallest subset, so that their sum contains n elements in all U.

Back to our question:

A has n points and represents n elements.

B has m points representing m subsets.

If the subset contains elements, connect an edge.

As you can see, set covering becomes finding the smallest point set in B, thus covering all points in A. ..

BTW: A popular science about NP- complete problems. If a problem is NP complete, then its algorithm is exponential, that is, there is no effective algorithm.