Как создать задачу N-Queens с дочерним алгоритмом Geneti c с ограниченными строкой и столбцом?

Question

Для найденной проблемы N-Queen здесь я пытаюсь реализовать алгоритм geneti c для ее решения.

Однако, скажем, я пытаюсь ограничить проблема. Мы знаем, что для получения атакующего значения 0 у вас не должно быть королев в одной строке и столбце. Я ограничиваю доски, чтобы всегда иметь разные строки и столбцы для каждой королевы. Я хочу, чтобы алгоритм geneti c нашел решение, при котором диагонали также не атакуют.

Моя проблема заключается в создании дочернего элемента для этого решения с использованием алгоритма geneti c. Какой хороший способ создать дочерний элемент из двух родительских плат состоит в том, что дочерние элементы не должны иметь ферзей в перекрывающихся строках и столбцах?

Answer 1

Избежать перекрывающихся строк и столбцов сложно в алгоритме genti c. Типичный подход состоит в том, чтобы неявно представлять столбцы индексом в массиве, а затем иметь королевы, представленные числами 1..N.

Таким образом, решение проблемы 8-королевы будет представлено как ( 5 1 8 4 2 7 3 6).

Если вы возьмете любое подмножество массива, вы можете смешать его с другим массивом и быть уверенным, что в каждом столбце (или строке) есть один ферзь, однако вы предпочитаете подумайте об этом).

Вы можете избежать наложения столбцов и строк, используя комбинаторику (так что вместо N ^ N есть N!), но проблема в том, что для этого требуется представление (вы можете по существу используют целые числа для представления полных конфигураций) не работает так же хорошо для операций кроссовера. Вы также столкнетесь с пределом целочисленных представлений. Использование массива, как описано выше, работает довольно хорошо, поэтому я бы предложил сначала изучить этот подход.