Posts tagged with DLX


DLX算法入门文……主要说一下我对这个算法的理解。 问题描述 精确覆盖问题: 以矩阵模型介绍,给你一个矩阵,其每个格子的权值范围是 [0,1] ,让你选出若干行,使得选出的行的 1 覆盖了一行的所有格子,且不能有重叠。 重复覆盖问题: 与精确覆盖问题基本相同,但是所选的行集合中,同一列的 1 允许重叠。 这个问题当然不可能让你输出可行方案,输出的应该是行数最小的方案。 算法理解 精确覆盖和重复覆盖都是NP问题,通常的,…