查找可以杀死的最大鹿数量

Question

让我们有N X N矩阵，其中网格中的每个元素可以是H或D，H = Hunter和D = Deer。猎人只能杀死1鹿。现在，我们还给出了整数k表示猎人可以杀死鹿的最大单位。此外，如果猎人在同一行，他们可以杀死鹿。查找可以在此网格中杀死的最大鹿数。

示例输入：

3,1
HDH
DHD
DDH

示例输出：

3

说明：每行杀死一只鹿，此处最大整数k为1。

我们如何解决这个问题？这是回溯问题吗？

Answer 1

这是二部图中maximum-cardinality matching problem的实例。该问题要求一种将最大可能的猎人数量与鹿匹配的方法，但要受哪些猎人可以与哪只鹿匹配的约束，以及每个猎人和每只鹿只能匹配一次的约束。

一种简单的解决方案是为每个猎人列表列出猎人可以匹配的鹿，然后列出标准的算法，例如Ford–Fulkerson或Hopcroft–Karp来查找匹配项。

这些算法比回溯解决方案更有效：

• Ford–Fulkerson以O（V·E）时间运行，其中V是顶点数，E是边数。由于存在n²个顶点，并且每个顶点附近只能有O（k）个其他顶点的边，因此算法的时间复杂度将为O（kn²）。
• Hopcroft–Karp在理论上做得更好；它以O（√V·E）时间运行，但是生成图的成本首先是O（kn²），因此总的时间复杂度仍为O（kn²）。

原则上，通过更好的数据结构设计，可以将生成图的时间提高到O（n²）；而不是为每个节点的邻居存储单独的阵列，而是将所有鹿的位置存储在每行的单个阵列中，并将每个猎人的头和尾边缘与该阵列中的位置相关联。这样可以改善算法的最佳情况，但是只有在k大的情况下才值得这样做，而整体算法的最坏情况也没有得到改善，因为总共仍然有O（kn²）条边。