这个谜题中的移动次数是多少？

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