python - 使用可用库解决最小集覆盖

Question

我想解决一个最小集覆盖的实例。作为一种可能性，是否有某种方法可以将问题表述为二分图并使用 networkx？

评论中建议使用 dlx（跳舞链接）进行更新。谁能给出一个小的工作示例来说明如何使用 dlx 解决最小集覆盖问题？

Answer 1

集合覆盖可以映射到图上的任何 NP 完全问题，但这并不意味着您将能够有效地解决它。您是否有理由不直接关注手头的问题（即设置掩护）？

也许是这样的：https ://pypi.org/project/dlx/

这可以使用安装： pip install dlx 或 easy_install dlx

Answer 2

对于每个DLX在 Python 中苦苦挣扎的人，我准备了一个小例子

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