我得到了一个程序，它要求我计算一个矩阵的先前状态的数量。

给定的矩阵是一个 boolean 矩阵。我将使用 1 代表 true 和 0 代表 false 来解释这个程序。

矩阵中一个单元格的下一个状态是 1，如果考虑到这四个单元格:

• 细胞本身
• 右边的单元格
• 它下面的单元格
• 它下方和右侧的单元格，

这4个单元格中只有一个1，即这4个单元格中正好有3个0和正好有1个1细胞。

如果给定的矩阵 (M) 是:
1 1 0 0 0 0 0 1 0 0 1 0

然后对于第一个单元格(M[0][0])，要考虑的四个单元格是 M[0][0]、M[0][1]、M[1][0] 和 M [1][1]。所以，第一个单元格的下一个状态是 0，因为我们在这 4 个单元格中有 2 个 1。

对于第二个单元格(M[0][1])，要考虑的四个单元格是 M[0][1]、M[0][2]、M[1][1]、M[ 1][2]。所以这个单元格的下一个状态是 1 因为这四个单元格中只有 1 个 1。

这样下去，这个矩阵 (M) 的下一个状态就是矩阵 (N):

0 1 1 0 1 0

显然，下一个状态将比前一个状态少 1 行和 1 列。因此，矩阵的一个给定状态可以有许多先前的状态，例如除了矩阵M之外，给定矩阵:

1 0 1 0 1 0 0 0 1 1 0 0

也会有下一个状态N。

我必须计算给定矩阵具有的先前状态的数量。

我写了下面的代码:

public class Answer2 {

static boolean[][] main_array,answer_array; // answer_array is the 2D array given to me. main_array is the 2D array which I recurse through, and then find its solution to compare with answer_array.
static int c; // counter
static int answer_array_height,answer_array_width; // matrix height and matrix width
public static int answer(boolean[][] boolean_array)
{       
    answer_array = boolean_array;
    main_array = new boolean[answer_array.length+1][answer_array[0].length+1];
    c=0;
    answer_array_height = answer_array.length;
    answer_array_width = answer_array[0].length;
    recurse(1,1);
    main_array[0][0] = true;
    recurse(1,1);
    return c;
}

public static String pad(String s, int l){ //Add 0's to the beginning of the string till its length equals l
    for(int i=s.length(); i<l; i++)
        s='0'+s;
    return s;
}

public static void recurse(int w, int h){
    if(w==answer_array_width+1 && h==answer_array_height+1){        
        c++;
        return;
    }  
    //System.out.println(java.util.Arrays.deepToString(main_array).replace("],","],\n").replace("true","1").replace("false","0"));        
    if(h==answer_array_height+1 || h>=w){//Add column
        int x = 0;           
        for(int i=0; i<h; i++) x+=(int)Math.pow(2,i); //This will give me the integer representation of max value(whose binary representation will be used to put values in the matrix) to handle.

        for(int i=0; i<=x; i++){
            String str = pad(Integer.toBinaryString(i),h);
            for(int j=0; j<h; j++){
                main_array[j][w]= str.charAt(j)=='1'; //set main_array[j][w] true wherever the binary representation of i has 1. This recurses through all the combinations.
            }
            if(check(w+1,h,false)){   
                recurse(w+1, h);     
            }else{        
                for(int j=0; j<h; j++){    
                    main_array[j][w]=false;       
                }              
            }          
        }      
    }else{//Add row            
        int x = 0;           
        for(int i=0; i<w; i++) x+=(int)Math.pow(2,i);
        for(int i=0; i<=x; i++){
            String str = pad(Integer.toBinaryString(i),w); 
            for(int j=0; j<w; j++){
                main_array[h][j]= str.charAt(j)=='1';      
            }              
            if(check(w,h+1,true)){         
                recurse(w, h+1);          
            }else{              
                for(int j=0; j<w; j++){    
                    main_array[h][j]=false;         
                }              
            }          
        }      
    }   
}

// w is the effective width, h is the effective height, height_was_increased is true if height was increased, false if width was increased.
//height_was_increased helps to shorten the time used for comparison as the matrix was correct before the width or height was increased. So it just needs to check the increased portion.
public static boolean check(int w, int h, boolean height_was_increased){
    if(height_was_increased){         
        for(int j=0; j<w-1; j++){    
            //I know this part is complex. It just finds out the answer of the four cells to be considered and matches it with the given matrix.
            if(answer_array[h-2][j] != (main_array[h-2][j]^main_array[h-2+1][j]^main_array[h-2][j+1]^main_array[h-2+1][j+1] && !(main_array[h-2][j] && main_array[h-2+1][j]) && !(main_array[h-2][j+1] && main_array[h-2+1][j+1]))) return false;    
        }       
    }else{     
        for(int i=0; i<h-1; i++){      
            if(answer_array[i][w-2] != (main_array[i][w-2]^main_array[i+1][w-2]^main_array[i][w-2+1]^main_array[i+1][w-2+1] && !(main_array[i] [w-2] && main_array[i+1][w-2]) && !(main_array[i][w-2+1] && main_array[i+1][w-2+1]))) return false;   
        }
    }     
    return true; 
}

}

它基本上做的是，它从一个空矩阵开始(其大小适合其下一个状态，给出所要求的矩阵)并从左上角开始，将有效宽度和高度交替增加 1，并检查矩阵的下一个状态到现在是否对应于给定状态。如果不是，它会跳过矩阵的其余部分。然后，如果找到下一个状态与给定状态相同的矩阵，它将计数器加 1。

此代码适用于小矩阵(单元格数 <40)，但对于大矩阵需要花费大量时间。矩阵的最大宽度可以是>50，最大高度可以是 9。所以这段代码不太适合这个目的。

我知道我必须在这里使用内存(做 c++ 几千次是不对的!)但我无法想象如何实现它。我以前用动态规划写过程序，但不知道它会在这里用在哪里。任何帮助将不胜感激。

最佳答案

有很多可能的矩阵可以产生给定的下一个状态。如果给出下一个状态矩阵 N 并且初始矩阵 M 被部分填充，例如元素 m[x][y+1], m[x+1 ][y] 和 m[x+1][y+1] 被填充，然后检查元素 m[x][y] 的可能性 s = m[x][y+1] + m[x+1][y] + m[x+1][y+1]，在某种程度上:

if n[x][y] == 1:
  if s == 0 than m[x][y] = 1
  if s == 1 than m[x][y] = 0
  if s > 1 than m[x][y] can't be filled
if n[x][y] == 0:
  if s == 0 than m[x][y] = 0
  if s == 1 than m[x][y] = 1
  if s > 1 than m[x][y] = 0 or 1

它看起来像 N 中的值 1“过滤”组合和 N 中的值 0“相乘”它们。

由于高度受较小值的限制，我建议首先使用可能的方法填充最后一列 值，而不是向后传递列，填充最后一列元素，然后通过上层检查逐个元素填充。

Python 实现:

import numpy
from itertools import product

num_results = 0

def fill_xy(m, s, x, y):
    if y < 0:
        fill_x_last(m, s, x-1)
        return
    _sum = s[x+1, y] + s[x+1, y+1] + s[x, y+1]
    if m[x, y] == 1:
        if _sum == 0:
            s[x, y] = 1
        elif _sum == 1:
            s[x, y] = 0
        else:
            return
    else:
        if _sum == 0:
            s[x, y] = 0
        elif _sum == 1:
            s[x, y] = 1
        else:
            s[x, y] = 0
            fill_xy(m, s, x, y-1)
            s[x, y] = 1
    fill_xy(m, s, x, y-1)

def fill_x_last(m, s, x):
    global num_results
    if x < 0:
        print s
        num_results += 1
    else:
        s[x, s.shape[1]-1] = 0
        fill_xy(m, s, x, s.shape[1]-2)
        s[x, s.shape[1]-1] = 1
        fill_xy(m, s, x, s.shape[1]-2)

def solve(m):
    global num_results
    height = m.shape[1]+1
    s = numpy.zeros((m.shape[0]+1, height), dtype=numpy.uint8)
    for p in product((0, 1), repeat=height):
        s[-1, :] = p
        fill_x_last(m, s, s.shape[0]-2)
    print num_results

solve(numpy.array([[0, 1, 1], [0, 1, 0]], dtype=numpy.uint8))

关于java - 如何在计算大量矩阵时使用内存，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41923054/