Cách sử dụng ghi nhớ khi đếm số lượng lớn ma trận

Question

Tôi đã được cấp một chương trình yêu cầu tôi đếm số các trạng thái trước cho ma trận.

Ma trận đã cho là ma trận boolean. Tôi sẽ sử dụng 1 cho true và 0 cho false để giải thích chương trình.

Các trạng thái tiếp theo của một tế bào trong một ma trận là 1 nếu, xem xét bốn tế bào:

• tế bào tự
• tế bào quyền nó
• ô bên dưới nó
• sự ô bên dưới và bên phải,

chỉ có một 1 trong tất cả 4 ô này, i .e., có chính xác 3 0 s và chính xác 1 1 trong 4 ô này.

Nếu ma trận cho trước (M) là:
1 1 0 0 0 0 0 1 0 0 1 0

Sau đó cho ô đầu tiên (M [0] [0]), bốn tế bào được coi là M [0] [0], M [0] [1], M [1] [0] và M [1] [1]. Vì vậy, trạng thái tiếp theo của ô đầu tiên là 0, bởi vì chúng tôi có 2 1 trong 4 ô này.

Đối với ô thứ hai (M [0] [1]), bốn ô được xem là M [0] [1], M [0] [2], M [1] [1], M [1] [2]. Vì vậy, trạng thái tiếp theo cho ô này là 1 vì chỉ có 1 1 trong bốn ô này.

Đi theo cách này, trạng thái tiếp theo của ma trận này (M) sẽ là ma trận (N):

0 1 1 0 1 0

Nhà nước tiếp theo sẽ, rõ ràng, có 1 hàng và 1 cột ít hơn trạng thái trước đó. Do đó, một trạng thái nhất định của ma trận có thể có nhiều tình trạng trước đó, ví dụ cùng với ma trận M, ma trận đưa ra:

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

cũng sẽ có cơ N. trạng thái tiếp theo

tôi phải đếm số trạng thái trước đó mà một ma trận đã cho có.

Tôi đã viết đoạn mã sau:

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; 
} 

} 

gì nó về cơ bản không có gì, là nó bắt đầu với một ma trận rỗng (kích thước phù hợp với trạng thái tiếp theo của mình để cung cấp cho các ma trận yêu cầu) và bắt đầu từ góc trên cùng bên trái, tăng chiều rộng và chiều cao hiệu dụng cách 1, và kiểm tra nếu trạng thái tiếp theo của ma trận cho đến bây giờ, tương ứng với trạng thái đã cho. Nếu không, nó bỏ qua phần còn lại của ma trận. Sau đó, nếu ma trận như vậy được tìm thấy, trạng thái tiếp theo giống với trạng thái đã cho, nó làm tăng bộ đếm bằng 1.

Mã này hoạt động cho ma trận nhỏ (không có ô < 40), nhưng phải mất rất nhiều thời gian cho các ma trận lớn.Chiều rộng tối đa của ma trận có thể là 50 và chiều cao tối đa có thể là 9. Vì vậy, mã này không hoàn toàn phù hợp cho mục đích đó.

Tôi biết rằng tôi phải sử dụng tính năng ghi nhớ ở đây (thực hiện c++ hàng nghìn lần không đúng!) Nhưng tôi không thể tưởng tượng cách sử dụng nó. Trước đây tôi đã viết các chương trình bằng cách sử dụng lập trình động nhưng không biết nó sẽ được sử dụng ở đâu. Bất kỳ trợ giúp sẽ được đánh giá cao.

---

Edit: Hạn chót nộp hồ sơ đã được vượt qua, và tôi không thể nộp câu trả lời. : '(
Nhưng, tôi vẫn muốn biết câu trả lời để tôi có thể giải quyết các chương trình như vậy trong tương lai. Tôi không cần mã hoàn chỉnh, nhưng thậm chí một số trợ giúp về cách tiếp tục sẽ được hoan nghênh! :)

Answer 1

Có rất nhiều ma trận có thể tạo ra được trạng thái tiếp theo. Nếu tiếp theo ma trận trạng thái N được đưa ra và ma trận ban đầu M được điền hoàn chỉnh, cho các yếu tố ví dụ m[x][y+1], m[x+1][y], và m[x+1][y+1] được làm đầy, hơn khả năng cho các phần tử m[x][y] được kiểm tra với giá trị s = m[x][y+1] + m[x+1][y] + m[x+1][y+1], theo một cách:

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 

Có vẻ như các giá trị 1 trong N kết hợp và giá trị 'bộ lọc' 0 trong số N 'nhân' chúng.

Vì chiều cao bị giới hạn bởi giá trị nhỏ hơn, nên đề xuất cách tiếp cận đầu tiên để điền cột cuối cùng với giá trị có thể, vượt qua cột ngược, điền phần tử cột cuối cùng và hơn phần tử điền kiểm tra phía trên theo phần tử.

Python thực hiện:

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))