Генетические алгоритмы - проблема королевы N - диагональные конфликты - PullRequest
Новая
       44

Генетические алгоритмы - проблема королевы N - диагональные конфликты

0 голосов
/ 06 апреля 2019

Я работаю над Java-кодом на основе генетических алгоритмов.Я хочу решить проблему N-королевы и должен вычислить конфликты / столкновения по диагонали.Я не могу правильно найти столкновения в диагонали.

Я нашел алгоритм, но не могу понять, как он реализован в моем коде.Я генерирую 2d массив 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

1 Ответ

2 голосов
/ 07 апреля 2019

Есть несколько проблем с вашим кодом:

  • Код подсчитывает конфликты дважды. В этом нет необходимости, потому что если существует конфликт между 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).

...