利用可用库求解最小集覆盖

Question

我想解决最小值set cover的一个实例。作为一种可能性，是否有某种方法将问题表述为二部图并使用networkx？在

更新建议使用dlx（跳舞链接）。有谁能举一个小例子来说明如何用dlx解决最小集覆盖问题吗？在

Answer 1

集合覆盖可以映射到图上的任何NP完全问题，但这并不意味着你能够有效地解决它。你不直接关注手头的问题有什么原因吗？在

可能是：https://pypi.org/project/dlx/

可以使用以下方法安装：pip install dlx或easy-_-install-dlx

Answer 2

对于在Python中使用DLX库的每个人，我准备了一个小示例

使用pip install dlx安装，然后按照我在gist中指定的方式进行，它附带了几个示例实例。享受吧！在