我有一个像这里的二分图
我试图找到图右侧的最小节点集,使得图左侧的每个节点都恰好连接到图右侧的一个节点。对于上图,看起来像这样。
我不太确定我该怎么做。我有一种感觉,它类似于图论或基础 CS 中的一些常见问题,并且通过一些转换变得等同于具有已知解决方案的问题。
最佳答案
你的问题是 NP-hard,因为 set cover problem (或者更确切地说,大卫指出的 exact cover problem )可以简化为它。一种简单的指数时间算法适用于节点子集上的动态规划。它可以在时间 O(2^m * n) 内实现,其中 m 是左侧的节点数,n 是右侧的节点数。
基于 Branch & Bound 的算法在实践中可能更有效。
关于algorithm - 在二部图的一侧找到支配的顶点集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23619566/