在 3n − ⌊lg n⌋ − 3 的二进制矩阵中找到所需的索引

Question

给定一个 n×n 矩阵 M，其中每个条目要么是 0 要么是 1。提出一个算法来确定是否 ∃i, 1 ≤ i ≤ n，使得 M[i,j] = 0 和 M [j,i] = 1, ∀j, 1 ≤j≤ n ∧ j!=i, 以检查 M 的一个条目作为关键操作。你的算法最多只能检查 3n − ⌊lg n⌋ − 3 个条目 M.

提示：将“检查 M[i, j]”与比较 i 与 j 联系起来。最初，每个索引都可能是所需的索引 i。将潜在索引i的个数从n减为1。然后验证该索引是否确实是想要的索引i。

有聪明的人可以遮挡更多的灯光或提示来解决这个问题吗？我是这个领域的新手，想到的任何方法都以 O(n^2) 结束。有什么建议吗？

我考虑过寻找任何模式的基本案例：

2×2 矩阵 M，将每个条目视为比较，那么我们有 4-2（对角线 elts）= 2 次比较。如果我们用所需的运行时间 T(n) 进行验证，我们有 3n - floor(lgn)-3 = 3*2 - lg2 -3 = 6-4 = 2comparisons
3 -by 3 M, 9 (entries) - 3 (diagonal etls) = 6 比较所需的 T(n) = 3*3 - floor(lg3) -3 = 9-4=5 比较
4×4 将给出 16-4 = 12 次比较，和 T(n) = 3*4 - lg4 -3 = 12-5 = 7 次比较在这里，我们观察到一个很大的不同，这个想法就崩溃了。但如果我能找到一种方法来配对矩阵条目，那我就很好了。上述基本情况将减少为 1、3 和 6 次比较，并保持在 T(n) 内。

接下来，我想把问题简化为证明M是或不是对称的，这意味着存在i使得Mij != Mji（或Mij = Mji）并且条件将被满足，因为M是二进制的.我的想法是看看我是否可以在线性时间内证明或反驳它，但我还没有找到它的算法。

Answer 1

将您的规则分成两部分。索引 i 有效当且仅当它同时满足：

行条件：M[i, j] = 0 for all j != i
列条件：M[k, i] = 1 for all k != i

这让我们注意到索引 i 的条件为真等同于 i'th 行全为零，而 i'th 列全为 1，除了它们相交于 M[i, i] 的地方，它可以有任何值。

对于具有 i=3 个有效（并且 non-numbered 个条目无关紧要）的插图：

. . . 1 . .
. . . 1 . .
0 0 0 x 0 0
. . . 1 . .
. . . 1 . .
. . . 1 . .

现在，考虑任何一对 i, j 和 i != j。

如果 M[i, j] = 1，我们知道 i 不是有效索引，因为它不符合行条件。
如果 M[i, j] = 0，我们知道 j 不是有效索引，因为它不符合列条件。

因此，对于矩阵元素的每个查询 M[i, j]，我们可以从考虑中排除一个索引。这也意味着最多一个索引是有效的。否则，如果 i1 和 i2 都有效，根据上述规则测试 M[i1, i2]，我们就会产生矛盾。

下面是整个算法在长度为 3 的矩阵上的示例。锦标赛树结构仅取决于叶节点的数量，稍后详述。

0 0 1
1 0 1
0 1 1

这里，第一个匹配（即兄弟叶节点）是(0, 1)。查询M[0, 1] returns 0，所以第二个索引1被淘汰。我们删除叶子的父节点，并用剩余索引的节点替换它，0。然后 (0, 2) 被匹配为新的兄弟叶节点。查询 M[0, 2] returns 1，因此第一个索引 0 被删除。 2 是唯一可能有效的剩余索引。

现在，要测试2是否有效，我们需要知道M[2, 0], M[2, 1], M[0, 2], M[1, 2]的值。我们已经查询了 M[0, 2] 的值，因此我们不再重复该查询。这给了我们 2 + 3 = 5 总查询，正好满足您的限制 3*n - 3 - floor(log_2(n)) = 9 - 3 - 1 = 5.

一旦我们最多拥有一个潜在的有效索引，我们就需要 2n - 2 对其列和行的查询来测试这两个条件。目前，这给了我们 n-1 个查询来消除除一个索引以外的所有索引，然后 2n-2 个查询来测试该索引，总共 3n-3 太多了。

但是，我们可以使用最初的 'elimination' 查询来计算后来的 'test' 查询。创建一个完整的完整二叉树，其中叶节点是索引0, 1, ... n-1。将其用作锦标赛树来确定初始消除查询：每个叶节点与其兄弟叶节点重复配对，直到剩下一个节点。

对于 n 个叶节点，叶节点的最小深度（因此任何索引参与的 matchups/elimination 查询的最小数量）在任何完整的二叉树中总是 floor(lg_2(n))。所以我们要查询的总数最多为
(n-1) + (2n-2) - floor(lg_2(n))，也就是 (3n-3) - floor(lg_2(n)).

这是算法的 Python 实现，应该与命令式伪代码相差不远。它特别冗长，并且分解成小函数，因此对 M 的所有访问都通过特殊的 query 函数完成并记录。这应该更清楚地表明您实际上满足了总查询的限制。

def find_valid_index(matrix: List[List[int]]) -> Optional[int]:
    """Given square binary matrix, return the index i
    such that, for all j != i,
    matrix[i, j] = 0 and matrix[j, i] = 1, or None if none exist."""

    num_rows = len(matrix)
    assert num_rows == len(matrix[0])

    if num_rows == 1:
        return 0

    fulfilled_queries = {}

    def query(i: int, j: int) -> int:
        if (i, j) not in fulfilled_queries:
            fulfilled_queries[i, j] = matrix[i][j]

        return fulfilled_queries[i, j]

    def index_to_eliminate(i: int, j: int) -> int:
        assert i != j

        return j if query(i, j) == 0 else i

    def is_valid_index(i: int) -> bool:
        """Test full row and column for validity"""
        for j in range(num_rows):
            if j == i:
                continue
            if query(i, j) == 1 or query(j, i) == 0:
                return False
        return True

    candidate_indices = list(range(num_rows))

    # Find distance from nearest power of two at most num_rows
    leftover_leafs = num_rows - 2**(math.floor(math.log2(num_rows)))

    if leftover_leafs > 0:
        eliminated_indices = set()
        for k in range(leftover_leafs):
            index1 = candidate_indices[2*k]
            index2 = candidate_indices[2*k+1]
            eliminated_indices.add(index_to_eliminate(index1, index2))

        candidate_indices = [x for x in candidate_indices
                             if x not in eliminated_indices]

    while len(candidate_indices) > 1:
        assert len(candidate_indices) % 2 == 0

        eliminated_indices = set()
        for k in range(0, len(candidate_indices), 2):
            index1 = candidate_indices[k]
            index2 = candidate_indices[k + 1]
            eliminated_indices.add(index_to_eliminate(index1, index2))

        candidate_indices = [x for x in candidate_indices
                             if x not in eliminated_indices]

    if len(candidate_indices) == 0:
        return None

    if is_valid_index(candidate_indices[0]):
        return candidate_indices[0]

    return None

在 3n − ⌊lg n⌋ − 3 的二进制矩阵中找到所需的索引

Find a desired index in a binary matrix in 3n − ⌊lg n⌋ − 3

algorithm

computer-science