這個謎題中的移動次數是多少？

Question

給出了尺寸爲n x n的二進制矩陣。

在每個步驟中，函數會檢查給定矩陣的每一行和每列是否至少有一個1。如果不是，則選擇純隨機座標，如i, j，其中1 <= i，j <= n，並且如果它是0，則標記爲1，否則保留1。

重複該過程，直到矩陣的每一行和每列都至少有一個1。

請告訴這個算法中移動的「期望數目」是多少。

Answer 1

您可以使用啓發式算法和隨機場模擬來獲得近似輸出。
你可以通過它創建一個輸出文件，這將確保你已經模擬了大量的數據，以確保你的近似答案接近最優化的答案。

Answer 2

for n = 1, 10 do 

    -- prepare matrix of zeroes 
    local P = {} 
    for i = 0, n do 
     P[i] = {} 
     for j = 0, n do 
     P[i][j] = 0 
     end 
    end 
    -- set matrix element at (0,0) = 1 
    P[0][0] = 1 

    local E = 0 -- expected value of number of steps 
    for move = 1, 1000000 do -- emulate one million steps 
     for x = n, 1, -1 do 
     for y = n, 1, -1 do 
     -- calculate probabilities after next move 
     P[x][y] = (
      P[x][y] *x  *y + 
      P[x-1][y] *(n+1-x)*y + 
      P[x][y-1] *x  *(n+1-y) + 
      P[x-1][y-1]*(n+1-x)*(n+1-y) 
     )/(n*n) 
     end 
     end 
     E = E + P[n][n]*move 
     P[0][0] = 0 
     P[n][n] = 0 
    end 

    print(n, E) 

end 

結果（N，E）：

1 1 
2 3.6666666666667 
3 6.8178571428571 
4 10.301098901099 
5 14.039464751085 
6 17.982832900812 
7 22.096912050614 
8 26.357063600653 
9 30.744803580639 
10 35.245774455244 

---

電子商務

精確值可以被計算出，但它需要的矩陣N * N，其中N = N反轉* N