遗传算法 - N 皇后问题 - 对角线冲突

Question

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

我找到了一种算法，但无法正确理解它是如何在我的代码中实现的。我生成一个 8x8

的二维数组

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 计数器的循环）。

因此，第一个更改应该是删除一个内部循环。出于性能原因，这也是有意义的。
第二个问题是目前只统计同一行内的冲突，不统计同一列.

因此，第二个变化应该是考虑到同列内的冲突。从编程上讲，它与之前的情况类似，但现在您必须考虑类别 top 和 bottom 而不是 left 和 right。
下一道题是考虑对角线上的冲突（原题）。

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

遗传算法 - N 皇后问题 - 对角线冲突

Genetic Algorithms - N Queen Problem - Diagonal Conflicts

java

genetic-algorithm

n-queens