이 퍼즐에서 예상되는 이동 수는 얼마입니까?

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 

---

E의

정확한 값을 산출 할 수 있지만, 행렬 N * N, N = N 반전을 필요 * N