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

Question

我正在研究基于Java的遗传算法代码。我想解决 N 女王问题，需要计算对角线中的冲突/冲突。我无法正确找到对角线中的冲突。

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

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

我已经找到了列和行的冲突。只需要计算对角线冲突。

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

  计数器的循环)。因此，第一个更改应该是删除其中一个内部循环。出于性能原因，这也是有意义的。

• 第二个问题是，目前只计算同一行内的冲突，而不计算同一列内的冲突。

  因此，第二个变化应该是考虑同一栏内的冲突。以编程方式，它类似于前面的情况，但现在您必须在类别的顶部和底部而不是左侧和右侧进行思考。

• 接下来的问题涉及对角线上冲突的考虑(这是原始问题)。

  您关于对角线冲突的伪代码可能来自这里。在这种方法中，候选溶液被视为具有n基因的染色体。每个基因对应于nxn棋盘的一行，并指示女王在该行中的位置。即候选解对应于一个大小为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)。