dry*_*hip 9 java performance matrix memoization dynamic-programming
我得到了一个程序,它要求我计算矩阵先前状态的数量.
给定矩阵是布尔矩阵.我将使用1的true并0为false解释程序.
矩阵中单元格的下一个状态是1,考虑到这四个单元格:
1在所有这4个细胞中只有一个,即在这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,因为我们1在这4个细胞中有2 个.
对于第二个小区(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.因此,此代码不能用于此目的.
我知道我必须在这里使用memoization(做了c++几千次是不对的!)但是我无法想象如何实现它.我以前使用动态编程编写程序,但不知道在这里使用它的位置.任何帮助,将不胜感激.
有很多可能的矩阵可以产生给定的下一个状态。如果给定下一个状态矩阵N并且初始矩阵M被部分填充，例如 elementsm[x][y+1], m[x+1][y]和m[x+1][y+1]
被填充，则m[x][y]用 value 检查element 的可能性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))