遗传算法 - N女王问题 - 对角线冲突

Question

我正致力于基于Java的遗传算法代码。我想解决N-queen问题并需要计算对角线中的冲突/冲突。我无法正确找到对角线上的冲突。

我找到了一个算法，但无法正确理解它如何在我的代码上实现。我生成一个8x8的二维数组

char Queens[][]={
                    {'.','.','.','.','.','.','.','.'},
                    {'.','.','.','.','.','.','.','.'},
                    {'.','.','.','.','.','.','.','.'},
                    {'.','.','.','.','.','.','.','.'},
                    {'.','.','.','.','.','.','.','.'},
                    {'.','.','.','.','.','.','.','.'},
                    {'.','.','.','.','.','.','.','.'},
                    {'.','.','.','.','.','.','.','.'},

            };

我已经找到了Columns and Rows的冲突。只需要计算对角线冲突。

 for(int i=0;i<8;i++){
            Queens[myarr[i]][i] = 'q';
        }

int conflict=0;
        for (int i=0;i<8;i++){
            for (int j=0;j<8;j++){
                if(Queens[i][j]=='q'){




                    for(int left=j-1;left>=0;left--){
//                        System.out.print(left+"      "+j);
                        if(Queens[i][left]=='q'){
                            conflict++;
                        }
                    }


                        for(int right=j+1;right<8;right++)
                        {
                               if(Queens[i][right]=='q'){
                                conflict++;
                            }
                        }

这是我发现的算法但无法在我的Queens[][]数组上实现它

# calculate diagonal clashes
for i in range(len(chromosome)):
    for j in range(len(chromosome)):
        if ( i != j):
            dx = abs(i-j)
            dy = abs(chromosome[i] - chromosome[j])
            if(dx == dy):
                clashes += 1


return 28 - clashes

Answer 1

您的代码存在一些问题：

• 代码对冲突进行两次计算。这不是必要的，因为如果q1和q2之间存在冲突，由于对称性原因，q2和q1之间也存在冲突。原则上，仅向左或向右计算一个方向就足够了。以编程方式，这意味着只应使用两个内部循环中的一个（具有right计数器的那个或具有left计数器的那个）。 因此，第一个更改应该是删除其中一个内部循环。出于性能原因，这也是有意义的。
• 第二个问题是，目前只计算同一行内的冲突，但不计算同一列内的冲突。 因此，第二个变化应该是考虑同一列内的冲突。它以编程方式与前一种情况类似，但现在您必须在类别顶部和底部而不是左侧和右侧进行思考。
• 接下来的问题涉及对角线冲突的考虑（这是最初的问题）。 关于对角冲突的伪代码可能来自here。在该方法中，候选溶液被认为是具有n基因的染色体。每个基因对应于nxn-chessboard的一行，并指示女王在该行中的位置。即候选解决方案对应于大小为n的数组，其中每个元素包含属于相应元素的行中的后者的位置。 相反，您的代码使用直接表示棋盘的nxn矩阵。这意味着候选解决方案对应于nxn矩阵，其中对应于具有女王的字段的每个元素包含字符q。 我不知道如何将伪代码与您的方法结合起来。这就是为什么我建议以下与您的方法兼容的替代方案： 对角线分为两类： 一类包括从左上到右下的对角线。这种情况可以按如下方式处理：

  for (int bottom = i + 1, right = j + 1; bottom < 8 && right < 8; bottom++, right++) {
      if (Queens[bottom][right] == 'q') {
          conflict++;
      }
  }

  另一类包括从右上到左下的对角线。在编程上，这类似于先前的情况，因此可以以类似的方式实现。

完成所有更改后，总共有四个内部循环。第一个考虑了行内的冲突，列中的第二个冲突以及对角线内的第三个和第四个冲突。使用以下矩阵进行测试......

{ 'q', '.', '.', '.', '.', '.', '.', 'q' }, 
{ '.', '.', '.', '.', '.', '.', '.', '.' },
{ '.', '.', 'q', '.', '.', 'q', '.', '.' }, 
{ '.', '.', '.', '.', '.', '.', '.', '.' },
{ '.', '.', '.', '.', '.', '.', '.', '.' }, 
{ '.', '.', 'q', '.', '.', 'q', '.', '.' },
{ '.', '.', '.', '.', '.', '.', '.', '.' }, 
{ 'q', '.', '.', '.', '.', '.', '.', 'q' },

...应该导致20次冲突（2个对角线，每个冲突6 = 3 + 2 + 1个冲突，4个冲突，每个冲突1个冲突，4个冲突，每个冲突1个冲突：2 * 6 + 4 * 1 + 4 * 1 = 20 ）。