給定一個 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 (entry) - 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 是二進制的，因此條件將被滿足。這個想法是看看我是否可以在線性時間內證明或反駁它，但我還沒有找到它的演算法。
uj5u.com熱心網友回復：
把你的規則分成兩部分。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有效（和非編號條目無關）的插圖：
. . . 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
Here, the first matchup (i.e. sibling leaf nodes) is (0, 1). The query M[0, 1] returns 0, so the second index, 1, is eliminated. We delete the parent node of the leafs, and replace it with the remaining index's node, 0. Then (0, 2) are matched up as new sibling leaf nodes. The query M[0, 2] returns 1, so the first index, 0, is eliminated. 2 is the only potentially valid index remaining.
Now, to test whether 2 is valid, we need to know the values of M[2, 0], M[2, 1], M[0, 2], M[1, 2]. We already queried the value of M[0, 2], so we don't repeat that query. This gives us 2 3 = 5 total queries, exactly meeting your bound of 3*n - 3 - floor(log_2(n)) = 9 - 3 - 1 = 5.
Once we have at most one potential valid index, we need 2n - 2 queries of its column and row to test both conditions. This currently gives us n-1 queries to eliminate all but one index, then 2n-2 queries to test that index, for a total of 3n-3 which is too many.
However, we can use the initial 'elimination' queries to count against the later 'test' queries. Create a full and complete binary tree, where the leaf nodes are the indices 0, 1, ... n-1. Use this as a tournament tree to determine the initial elimination queries: each leaf node is paired up against its sibling leaf node repeatedly, until one node remains.
With n leaf nodes, the smallest depth of a leaf node (and thus the smallest number of matchups/elimination queries any index participates in) in any full, complete binary tree is always floor(lg_2(n)). So the total number of queries we have to make is at most
(n-1) (2n-2) - floor(lg_2(n)), which is just (3n-3) - floor(lg_2(n)).
Here's a Python implementation of the algorithm, which shouldn't be far from imperative pseudocode. It's especially verbose, and broken up into small functions, so that all accesses to M are done through a special query function and logged. This should make it clearer that your bound for total queries is in fact met.
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/442747.html
下一篇：MySQL 中如何歸檔資料