-1

给出一个大小为nx的二进制矩阵n。

在每一步，函数都会检查给定矩阵的每一行和每一列是否至少有一个1. 如果不是，则选择一个纯粹的随机坐标，例如where , i, j，1 <= i并将j <= n其标记为保留。101

重复该过程，直到矩阵的每一行和每一列都具有至少一个1.

请告诉这个算法中移动的“预期数量”是多少。

4

2 回答 2

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

于 2014-03-01T23:04:59.413 回答
2

您可以使用启发式方法并模拟随机场以获得近似输出。
您可以在此基础上创建一个输出文件，这将确保您已经模拟了大量数据，以确保您的近似答案接近优化的结果。

于 2014-10-15T08:55:18.867 回答