제약 조건을 위반하지 않고 정수 배열 생성

Question

몇 시간 동안 문제를 겪고 있습니다. 그것은 제약 만족 문제이다. 간단한 예제로 설명하겠습니다.

길이가 8 인 정수 배열이 있다고 가정합니다. 모든 셀에는 특정 값을 사용할 수 있습니다. 처음 4 개의 셀은 0, 1 또는 2를 취하고 나머지 절반은 0 또는 1을 취할 수 있습니다. 이러한 3 개의 배열은 몇 가지 예일 수 있습니다. 다음과 같이

{2,1,0,2,1,1,0,1} 
{2,2,1,0,0,1,0,0} 
{0,0,0,2,0,0,0,1} 

그러나 배열을 구성하는 몇 가지 제약이있다 : 더 나은 이해를 위해

constraint1 = {1,-,-,-,-,1,-,-} // !(cell2=1 && cell6=1) cell2 and cell6 can not be in these format. 
constraint2 = {0,-,-,-,-,-,-,0} // !(cell1=0 && cell8=0) 
constraint3 = {-,-,-,2,1,1,-,-} // !(cell4=2 && cell5=1 && cell6=1) 
constraint4 = {1,1,-,-,-,-,-,-} // !(cell1=1 && cell2=1) 

;

{0,1,1,2,0,1,0,0} // this is not valid, because it violates the constraint2 
{1,1,2,2,1,1,0,1} // this is not valid, because it violates the constraint3 and constraint4 
{1,1,0,0,0,1,0,0} // this is not valid, because it violates the constraint4 

주어진 제약 조건을 위반하지 않는 정수 배열을 생성해야합니다.

내 접근 방식;

1) Create an array (called myArray) and initialize every cell to -1 
2) Count the number of cells which are used in constraints. Above example, cell1 is used 3 times, cell2 is used 1 time, cell3 is not used, so on so forth. 
3) Choose the cell which is used more in constraints (it is cell1, used 3 times) 
4) Find the distribution of numbers in this cell. (In cell1, 1 is used 2 times and 0 is used 1 time) 
5) Change this chosen cell in myArray to the number which is used less. (In cell1, since 0 is used less than 1, cell1 in myArray will be 0) 
6) Delete all the constraints from the list which has 1 or 2 in their cell1. 
7) Go to step 2 and do same steps until all constraints are eliminated 

이 알고리즘의 아이디어는 더 많은 제약 조건을 제거하는 방식으로 셀과 그 값을 선택하는 것입니다.

그러나 제약 조건 수가 높을 때이 알고리즘은 작동하지 않습니다.

중요 사항 : 이것은 단지 간단한 예입니다. 정상적인 경우 배열의 길이는 길어지고 (평균적으로 100) 제약 조건의 수가 더 높아집니다 (200 이상). 내 입력은 배열의 길이, N 제약 및 각 셀이 취할 수있는 값입니다.

이 문제를 해결하는 데 더 좋은 아이디어가있는 사람이 있습니까?

Answer 1

다음은 임의의 행렬을 생성하고 행렬의 제약 조건을 제거하기 위해 C#으로 작성한 코드입니다.

class Program 
{ 
    static void Main(string[] args) 
    { 

     int[] inputData = new int[4] { 3, 7, 3, 3 }; 
     int matrixRowSize = 6; 

     /////////////////////////// Constraints 

     int []constraint1 = new int[4] { 1, -1, -1, 2}; // here is the constaint that i want to remove. 
     // note the constaints could be more than 1, so there could be a generic method 

     Random r = new Random(); 
     int[,] Random_matrix = new int[matrixRowSize, inputData.Length]; 
     ///////////// generate random matrix 
     for (int i = 0; i < inputData.Length; i++) 
     { 
      for (int j = 0; j < matrixRowSize; j++) 
      {  
       int k = r.Next(0, inputData[i]); 


       Random_matrix[j, i] = k; 
      } 
     } 

}