Генетический алгоритм для задачи о n ферзях

Обзор методов решения задачи удовлетворения ограничений

Генетический алгоритм для задачи о n ферзях

Ключевые слова: искусственный интеллект, задача удовлетворения ограничений, поиск с возвратом, генетический алгоритм, распространение ограничений, алгоритм Вальца, разметка изображений.

По современным научным данным человеческий мозг содержит огромное число нейронов, он производит и обрабатывает огромное количество логически связанных электрохимических импульсов.

Результатами этих процессов являются способность адаптироваться к новым ситуациям, способность к обучению на основе опыта, понимание и применение абстрактных концепций и использование своих знаний для управления окружающей средой.

Ученые пытаются приблизить возможности компьютера к уровню развития человеческого мозга, пытаясь создать интеллектуальные машины и интеллектуальные компьютерные программы. Искусственный интеллект должен думать и действовать рационально, вести и мыслить, как человек.

Обратите внимание

Одной из важных задач искусственного интеллекта (ИИ) является задача удовлетворения ограничений (УО) (constraint satisfaction problem). Теория УО предлагает удобный аппарат и простую формальную схему для представления и решения комбинаторных задач ИИ.

В искусственном интеллекте парадигма УО признана в качестве удобного и эффективного способа моделирования и решения многих прикладных комбинаторных задач. Важная задача оценки конъюнктивных запросов в теории баз данных может рассматриваться как задача УО.

Кроме того, задачи УО привлекают большое внимание в теории сложности, так как различные версии задач УО находятся в середине многих стандартных классов сложности.

Задача УО состоит из множества переменных, множества доменов значенийдля каждой переменной, и множества ограничений и отношений. Каждый домен значений является конечным множеством значений, которые может принимать соответствующая переменная.

Состояние задачи определяется путем присваивания значений некоторым или всем этим переменным. Присваивание, которое не нарушает никаких ограничений, называется совместимым, или допустимым присваиванием.

Полным называется такое присваивание, в котором участвует каждая переменная, а решением задачи CSP является полное присваивание, которое удовлетворяет всем ограничениям.

Для решения задачи УО применяются различные методы: методы поиска на графах, методы согласования, методы распространения ограничений, генетические методы, итерационные методы и многие другие. В данной статье будут рассмотрены наиболее простые и наиболее широко применяемые методы: метод поиска с возвратом, генетический метод и метод распространения ограничений.

Поиск с возвратом (Backtrackingsearch).

Решение задачи методом поиска с возвратом строится конструктивно последовательным расширением частичного решения.

Важно

Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются.

Для ускорения перебора с возвратом вычисления всегда стараются организовать так, чтобы была возможность отказаться как можно раньше от как можно большего числа заведомо неподходящих вариантов.

Метод поиска с возвратом является универсальным. Достаточно легко проектировать и программировать алгоритмы решения задач с использованием этого метода. Однако время нахождения решения может быть очень велико даже при небольших размерностях задачи (количестве исходных данных), причём настолько велико, что о практическом применении не может быть и речи.

В качестве примера использования поиска с возвратом возьмем задачу раскраски карты. Формулировка задачи следующая: необходимо раскрасить каждый регион на карте Австралии красным, зеленым или синий цветом таким способом, чтобы ни одна пара соседних регионов не имела одинаковый цвет.

Рис. 1. Задача раскраски карты Австралии

Чтобы сформулировать это задание в виде задачи УО, определим в качестве переменных сокращенные обозначения этих регионов: WA, NT, Q, NSW, V, SA и T. Областью определения каждой переменной является множество цветов {red, green, blue}.

Ограничения требуют, чтобы все пары соседних регионов имели разные цвета, например, допустимыми комбинациями для WA и NT являются следующие пары: {{red, green), {red, blue), {green, red), {green, blue), {blue, red), {blue, green)}

Сначала раскрасим первую область любым цветом, а затем пытаемся раскрасить следующие области так, чтобы соседние регионы не были одинаковых цветов. Если на очередном шаге оказалось, что ограничение не выполняется, возвращаемся на шаг назад и меняем цвет ранее раскрашенной области.

Рис. 2. Граф решения задачи раскраски карты методом поиска с возвратом

Количество возможных решений достаточно велико; например, одним из таких решений является следующее: {WA=red, NT= green, SA=blue, Q=red, NSW=green, V=red, T=red}.

Совет

Генетический метод.

Генетический метод основан на принципах селекции: отбор, скрещивание и мутация. При решении задач проводится аналогия с животным миром. Переменные считаем отдельными особями, а их значения, удовлетворяющие ограничения, полезными генами, которые необходимо передать потомству для получения наилучших особей, т. е. решения поставленной задачи.

В начале решения переменным присваиваются случайные значения. Для того, чтобы узнать, «на сколько особи приспособлены», случайно сгенерированное решение проверяется на удовлетворение ограничения. Следующим шагом «скрещиваем лучших особей» и формируем новое «поколение», заменяя худшие решения.

Новый набор решений заново оценивается и формируются следующие «поколения». Важно отметить, что на определенном этапе решение может зациклиться, для исключения зацикливания генетический алгоритм предусматривает «мутации».

Мутации подразумевают перенимание переменными-потомками свойств переменных-предков с небольшими изменениями.

Рассмотрим применение генетического алгоритма в рамках УО на примере задачи о расстановке N ферзей.

Задача о расстановке N ферзей заключается в том, чтобы расставить на шахматной доске размером N на N клеток фигуры N ферзей так, чтобы они не били друг друга.

Представим в форме ЗУО: переменными являются положения ферзей; областью определения каждой переменной — её координаты на доске; ограничением выступает особенность хода фигуры (королева может ходить по вертикали, горизонтали и по диагонали на любое расстояние):.

Попробуем применить генетический метод на доске 8х8.

Рис. 3. Задача расстановки N ферзей

В начальный момент времени фигуры расположены в случайном порядке. Проверим, сколько угроз имеет каждая фигура и в следующем «поколении» заменим значения координат фигуры с наибольшим количеством угроз на новые.

Обратите внимание

В нашем случае наибольшее количество угроз приходится на фигуры в третьей и шестой строках, а наименьшее на фигуры во второй и пятой строках.

Следующее поколение должно содержать повторяющиеся у родителей наилучшие значения.

Рис. 4. Задача расстановки N ферзей после 1 и 2х итераций

Продолжая выполнять итерацию за итерацией мы получим следующее решение (одно из 92).

Рис. 5. Решение задачи расстановки N ферзей

Генетический алгоритм, конечно, не может решить задачу, если потребуется найти все её решения, но зато он существенно увеличивает скорость нахождения решения в сравнении с методами перебора или поиска с возвратом.

Распространение ограничений.

Данный метод находит решение задачи, сужая пространство возможных решений исключением избыточных значений из доменов переменных за счет распространения ограничений.

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

Алгоритм помогает решить задачу разметки изображений. Цель задачи состоит в распознавании объектов 3-мерного изображения с помощью интерпретации линий на 2-мерных рисунках. Каждое пересечение является переменной. Соседние пересечения накладывают ограничения друг на друга.

Суть метода: разметить все линии и узлы на рисунке с целью упростить процесс идентификации объекта.

Алгоритм решения задачи:

  •                Обозначаем линии на границе рисунка
  •                Нумеруем вершины
  •                Исследуем каждую вершину в порядке нумерации
  • Применяются 4 вида обозначений линий: «», «», «+» и «-». Стрелками обозначаются линии на границе рисунка. Плюс определяет выпуклость, а минус вогнутость.

    Для удобства определения типа фигуры вершины (узлы) фигуры разделяют на 4 типа: L-тип, T-тип, тип Вилка и тип Стрелка.

    Рис. 6. Типы вершин

    В процессе разметки изображения необходимо придерживаться нескольких правил:

  •                Стрелки должны быть направлены так, чтобы отметить границы рисунка путем обхода в направлении часовой стрелки;
  •                Непрерывные линии должны иметь одинаковые метки на обоих концах;
  •                Если вершина типа Вилка не включает границы, то все три линии должны иметь одинаковую метку, т. е. либо все помечены «-», либо «+»;
  •                У вершин типа Стрелка, имеющих на внешних линиях «стрелки» метки границ, ось «стрелки» должна помечаться меткой «+».
  • Следуя правилам, можно получиться некоторые шаблоны для всех типов вершин, которыми будем пользоваться в процессе решения задач. То есть все возможные варианты разметки при узлах.

    Рис. 7. Варианты разметки

    Разберем порядок удовлетворения ограничений на примере конкретной задачи:

    Рис. 7. Пример применения алгоритма Вольца

    Сначала обозначим стрелками границы рисунка и пронумеруем узлы. Теперь необходимо обозначить линии внутри рисунка. Для этого проанализируем вершины по порядку. Первая вершина типа Стрелка имеет уже обозначенные два ребра, что накладывает ограничения на выбор метки для третьего ребра. Посмотрев в шаблоны, увидим, что единственной возможной меткой для оставшегося ребра будет «+».

    Вторая вершина типа L уже имеет все необходимые метки.

    Третья вершина типа Стрелка аналогична вершине первой. Повторяя прошлые шаги, над ребром 3–11 ставим «+».

    Дальше необходимо пройтись по всем вершинам. Результатом будет являться полностью размеченная фигура.

    Рис. 8. Решение задачи разметки изображения

    Литература:

    1.                  О. А. Щербина Удовлетворение ограничений и программирование в ограничениях

    2.                  Журнал «Интеллектуальные системы» Том 15

    3.                  Лекции Патрика Уинстона (МИТ)

    Генетический алгорифм для задачи о N ферзях

    Генетический алгоритм для задачи о n ферзях

    Трудность задачи зависит от метода исходной расстановки ферзей и составляет O(NN) в случае, когда на всякой строке может стоять только одна фигура, и O(N!), если в всякой строке и столбце находится только один ферзь. число вариантов дозволено сократить еще мощнее, анализируя расположения фигур по диагоналям.
    Две королевы в позициях (x1, y1) и (x2, y2) угрожают друг другу по диагонали, если x2 — x1 = |y2 — y1|.

    Генетический алгорифм

    Способы такого рода основаны на 3 биологических тезисах: отбор, скрещивание и мутация. Потенциальные решения представляют собой отдельные ‘особи’, которые ранжируются целевой функцией для селекции особенно приспособленных (близких к требуемому решению).
    Всеобщая схема генетического алгорифма:

  • Генерируется случайная популяция ‘особей’-решений задачи. Все решения ранжируются целевой функцией.
  • Наихудшие решения заменяются решениями-потомками, которые возникают в итоге скрещивания наилучших ‘особей’. К потомкам используется функция мутации.
  • Новая популяция опять оценивается и процесс повторяется.
  • Целевая функция и выбраковка дрянных решений

    Решения задачи предположим в виде кортежа размерности N: индекс — это строка, в которой стоит фигура, а значение — это номер столбца.
    Скажем, для N=8 решение (4, 0, 3, 5, 7, 1, 6, 2) показано рядом на рисунке.

    В качестве ‘особей’ начальной популяции будем генерировать только такие решения, у которых нет раздоров по горизонталям и вертикалям. Функция ранжирования hits будет подсчитывать число раздоров по диагоналям для всякого решения. Чем выше ее значение, тем дрянней ‘особь’.

    Заменим решения, для которых значение целевой функции огромнее медианы каждого поколения. Т.е. на всякой итерации популяция будет обновляться приблизительно на половину.

    Функции скрещивания

    Дозволено придумать различные методы производства потомков. Разглядим две функции:
    crossover (скрещивание) на основе 2-х родителей генерирует потомка, тот, что будет содержать только повторяющиеся у родителей значения, остальные позиции заполняются нечаянно, но без раздора по столбцам.

    Скажем,
    родитель I:  (3, 5, 7, 6, 21, 4);
    родитель II: (3, 4, 6, 5, 21, 7);
    потомок:     (3, 7, 6, 4, 21, 5).

    Важно

    Превосходство этой функции заключено в обмене ‘генетическим’ материалом, но, из-за непрерывной генерации новых значений в потомке, трудиться она будет не крепко стремительно.

    gemmation (почкование) на основе одного родителя генерируется потомок, в котором случайным образом два элемента поменяны местами. Скажем,

    родитель: (3, 0, 5, 7, 6, 2, 1, 4);
    потомок:  (1, 0, 5, 7, 6, 2, 3, 4).
    Такая функция будет трудиться стремительней crossover, но она фактически реализует клонирование (‘генетический’ материал меняется немного).

    Функция мутации

    Функция mutation — примитивна и реализует алгорифм функции gemmation: случайным образом меняются местами два элемента. Вероятность мутации выбрана так, Дабы в всяком поколении, как минимум, одно из решений изменилось. Мутация разрешает в случае сходимости к локальному минимуму выйти из него.

    Тестирование

    Популяция состоит из 75 особей, вероятность мутации 3%. В качестве генератора псевдослучайных чисел использован Mersenne twister (mt19937). Программа распараллелена с поддержкой OpenMP (этапы генерации первого поколения, ранжирования и скрещивания). Итоги тестов на 8 потоках приведены в таблице (медиана в пяти испытаниях).

    N
    Функция crossover
    Функция gemmation

    Время работы, с.
    Поколений, тыс. шт.
    Время работы, с.
    Поколений, тыс. шт.

    500
    663
    43,6
    69
    10,3

    1000
    4269
    94,7
    233
    24,8

    2500
    67180
    297,3
    1780
    53,5

    5000
    Не тестировалось
    87569
    227,6

    Функция gemmation потребляет поменьше источников и обеспечивает больше стремительную сходимость к решению. Применение генератора Мерсенна в crossover все равно не дозволило приблизиться к быстродействию функции размножения gemmation как по времени, так и по числу поколений.

    Их число растет экспоненциально с увеличением N. Скорость работы отличается больше, чем в два раза с учетом числа итераций, а в безусловном исчислении примерно в десять раз даже для N=500. Предположу, что чтение из/dev/random дозволит усовершенствовать быстродействие.

    Что увлекательно, больше трудная функция размножения находит решение за большее число итераций.

    Алгорифм отлично параллелится, что подтверждает рисунок рядом (синий — crossover; зеленый —gemmation). Но на убыстрение оказывает огромное воздействие функция размножения: для gemmationотслеживается примерно линейный рост убыстрения. А crossover этого не показывает, т.к.

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

    Если же для цикла с функцией crossoverизменить порядок приобретения потоками итераций на исполнение (клауза schedule(dynamic), голубым цветом на графике), то убыстрение увеличится и примерно достигнет яруса функции gemmation.

    На примере N=2500 разглядим задачу сходимости (рисунок справа). Примерно половина всех итераций расходуется на то, Дабы убрать последние 30 раздоров.

    Если бы нам предварительно не было вестимо условие останова, то было бы затруднительно достичь точного решения.

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

    Генетический алгоритм для задачи о N ферзях

    Генетический алгоритм для задачи о n ферзях

    21 апреля 2014 в 09:34 (МСК)

    На шахматной доске размера N x N нужно расставить N ферзей так, чтобы они не угрожали друг другу. Поиск с возвратом — стандартный метод решения для небольших N. Ниже рассмотрен генетический алгоритм позволяющий находить решение для N порядка нескольких тысяч.

    Сложность задачи зависит от способа начальной расстановки ферзей и составляет O(NN) в случае, когда на каждой строке может стоять только одна фигура, и O(N!), если в каждой строке и столбце находится только один ферзь. Количество вариантов можно сократить еще сильнее, анализируя положения фигур по диагоналям.

    Две королевы в позициях (x1, y1) и (x2, y2) угрожают друг другу по диагонали, если x2 — x1 = |y2 — y1|.

    Методы такого рода основаны на трех биологических принципах: отбор, скрещивание и мутация. Потенциальные решения представляют собой отдельные 'особи', которые ранжируются целевой функцией для селекции наиболее приспособленных (близких к требуемому решению).

    Общая схема генетического алгоритма:

  • Генерируется случайная популяция 'особей'-решений задачи. Все решения ранжируются целевой функцией.
  • Худшие решения заменяются решениями-потомками, которые появляются в результате скрещивания лучших 'особей'. К потомкам применяется функция мутации.
  • Новая популяция вновь оценивается и процесс повторяется.
  • Решения задачи представим в виде кортежа размерности N: индекс — это строка, в которой стоит фигура, а значение — это номер столбца.
    Например, для N=8 решение (4, 0, 3, 5, 7, 1, 6, 2) показано рядом на рисунке.

    В качестве 'особей' исходной популяции будем генерировать только такие решения, у которых нет конфликтов по горизонталям и вертикалям. Функция ранжирования hits будет подсчитывать количество конфликтов по диагоналям для каждого решения. Чем выше ее значение, тем хуже 'особь'.

    Заменим решения, для которых значение целевой функции больше медианы всего поколения. Т.е. на каждой итерации популяция будет обновляться примерно на половину. Можно придумать разные способы производства потомков.

    Рассмотрим две функции:

    crossover (скрещивание) на основе двух родителей генерирует потомка, который будет содержать только повторяющиеся у родителей значения, остальные позиции заполняются случайно, но без конфликта по столбцам. Например,

    родитель I:  (3, , 5, 7, 6, 2, 1, 4);
    родитель II: (3, , 4, 6, 5, 2, 1, 7);
    потомок:     (3, , 7, 6, 4, 2, 1, 5). Преимущество этой функции заключено в обмене 'генетическим' материалом, но, из-за постоянной генерации новых значений в потомке, работать она будет не сильно быстро.

    gemmation (почкование) на основе одного родителя генерируется потомок, в котором случайным образом два элемента поменяны местами. Например,

    родитель: (3, 0, 5, 7, 6, 2, 1, 4);
    потомок:  (1, 0, 5, 7, 6, 2, 3, 4).
    Такая функция будет работать быстрее crossover, но она практически реализует клонирование ('генетический' материал меняется мало).
    Функция mutation — проста и реализует алгоритм функции gemmation: случайным образом меняются местами два элемента. Вероятность мутации выбрана так, чтобы в каждом поколении, как минимум, одно из решений изменилось. Мутация позволяет в случае сходимости к локальному минимуму выйти из него. Популяция состоит из 75 особей, вероятность мутации 3%. В качестве генератора псевдослучайных чисел использован Mersenne twister (mt19937). Программа распараллелена с помощью OpenMP (этапы генерации первого поколения, ранжирования и скрещивания). Результаты тестов на 8 потоках приведены в таблице (медиана в пяти испытаниях).

    N
    Функция crossover
    Функция gemmation

    Время работы, с.
    Поколений, тыс. шт.
    Время работы, с.
    Поколений, тыс. шт.

    500
    663
    43,6
    69
    10,3

    1000
    4269
    94,7
    233
    24,8

    2500
    67180
    297,3
    1780
    53,5

    5000
    Не тестировалось
    87569
    227,6

    Функция gemmation потребляет меньше ресурсов и обеспечивает более быструю сходимость к решению. Использование генератора Мерсенна в crossover все равно не позволило приблизиться к быстродействию функции размножения gemmation как по времени, так и по количеству поколений. Их число растет экспоненциально с увеличением N. Скорость работы отличается более, чем в два раза с учетом количества итераций, а в абсолютном исчислении почти в десять раз даже для N=500. Предположу, что чтение из /dev/random позволит улучшить быстродействие. Что интересно, более сложная функция размножения находит решение за большее число итераций.

    Алгоритм хорошо параллелится, что подтверждает рисунок рядом (синий — crossover; зеленый — gemmation). Но на ускорение оказывает большое влияние функция размножения: для gemmation наблюдается почти линейный рост ускорения. А crossover этого не показывает, т.к.

    постоянная генерация новых положений и проверка подходит ли оно для данной 'особи' занимает значительное время. От решения к решению время на эту операцию различно, поэтому логично предположить, что некоторые потоки быстрее обрабатывают свою часть популяции.

    Если же для цикла с функцией crossover изменить порядок получения потоками итераций на исполнение (клауза schedule(dynamic), голубым цветом на графике), то ускорение увеличится и почти достигнет уровня функции gemmation.

    Совет

    На примере N=2500 рассмотрим проблему сходимости (рисунок справа). Почти половина всех итераций тратится на то, чтобы убрать последние 30 конфликтов.

    Если бы нам заранее не было известно условие останова, то было бы затруднительно достичь точного решения.

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

  • Алгоритм критичен к быстродействию функции скрещивания, к ее выбору нужно подходить тщательно.
  • Мутация важна не так сильно, т. к. конструктивно почти невозможно попасть в локальный минимум.
  • Использование генетического алгоритма не гарантирует нахождение решения, даже, если доказано его существование (но здесь удалось расставить фигуры во всех случаях). Когда требуется найти все возможные решения этой задачи, то генетический алгоритм становится практически бесполезным.
  • Буду рад замечаниям и дополнениям.
    Решение задачи в случае N = 2500.
    Исходный код.

    Решение задачи о 8 ферзях генетическим алгоритмом на OCaml

    Генетический алгоритм для задачи о n ферзях

    2016-12-09 22:26

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

    Сам алгоритм довольно прост в реализации и больших вопросов не вызывает. По сути, мне нужно было разработать небольшой набор функций:

    • mutate, чтобы проводить небольшие мутации;
    • reproduce, чтобы создавать новые популяции на основе старых;
    • test, чтобы проверять, есть ли в популяции решение задачи;
    • find, чтобы запустить поиск решения.

    Этого небольшого набора вполне достаточно, чтобы запустить поиск.

    Однако для меня интерес представляла не только разработка такого алгоритма, но и хотелось самому проверить эффективность некоторых эвристик при выборе родителей для следующей популяции, а заодно сделать что-то новое в OCaml.

    Из OCaml я выбрал модули, хоть я и применял их раньше, но в привычку не вошло (решение небольших задач на codingame не требует разработки своих модулей, а до больших задач ещё не дошёл). В качестве подопытных эвристик выступили стратегии:

    • брать всех подряд, никого не выкидывать;
    • выбрать одного лучшего (по сути, тут надежда только на мутации);
    • выбирать двух лучших, остальных выбрасывать.

    После того, как я описал базовый алгоритм и удостоверился, что он работает, начал формировать модуль.

    module GA = struct
    end

    Популяция представляет собой список из 4 списков, в каждом по 8 чисел:

    module GA = struct let create_population () = List.init 4 (fun _ -> List.init 8 (fun _ -> Random.int 8))
    end

    Для проверки состояния доски использовал количество пар ферзей, которые не атакуют друг друга. Для 8 ферзей такое число равно 28, если никто не находится под ударом. На этом факте основаны две функции, одна для оценки близости состояния к решению, а вторая, является ли состояние решением (количество неатакующих пар == 28).

    let evaluate population = let under_attack (l1, c1) (l2, c2) = c1 = c2 || (abs (l1 – l2)) = (abs (c1 – c2)) in let rec foldi i accum = function | [] -> assert false | [x] -> accum | x :: xs -> foldi (i + 1) (List.foldi xs ~init:accum ~f:(fun i' accum x' -> accum + if under_attack (i, x) ((i' + i + 1), x') then 0 else 1)) xs in foldi 0 0 population let is_safe population = (* This is only for 8 cells on board, * for other sizes max_value should be ((1 + n) / 2 * n). *) let max_value = 28 in evaluate population = max_value

    Мутация и создание потомков простое и понятное.

    let mutate population = let n = Random.int (List.length population) in List.mapi population ~f:(fun i x -> if i = n then (Random.int 8) else x) let reproduce population1 population2 = let n = Random.int (List.length population1) in let (left, _) = List.split_n population1 n in let (_, right) = List.split_n population2 n in left @ right

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

    let find ?choose_parents population = let choose_parents = match choose_parents with | None -> (fun x -> x) | Some x -> x in let nextgen population = let population_size = List.length population in let population' = choose_parents population in let len = List.length population' in let rec aux i = if i > 0 then ( let n = Random.int len in let a = List.nth_exn population' n in let b = List.nth_exn population' n in let child = reproduce a b in if Random.int 10 List.hd_exn else nextgen population |> find_solution in let solution = find_solution population in (solution, !steps_number)

    В коде, который должен запускать поиск решения, описаны также функции для фильтрации популяции. Чтобы сделать результаты воспроизводимыми, я везде использовал одни и те же числа для инициализации генератора случайных чисел.

    let () = Random.init 10; (* Always init by the same number for testibility. *) let population = GA.create_population () in List.iter population ~f:(fun i -> printf “%s –> evaluate = %d
    ” (GA.to_string i) (GA.evaluate i)); printf ”
    “; let cmp a b = -(compare (GA.evaluate a) (GA.evaluate b)) in let choose_better_two population = match List.sort population ~cmp with | a :: b :: _ -> [a; b] | _ -> assert false in let choose_better_one population = [List.sort population ~cmp |> List.hd_exn] in let choices = [ None, “all”; Some (choose_better_one), “only better one”; Some (choose_better_two), “get best two” ] in let inits = [1; 10; 100; 42] in List.iter inits ~f:(fun init -> printf “Init by: %d
    ” init; List.iter choices ~f:(fun (choose_parents, name) -> Random.init init; (* Always init by the same number for testibility. *) let solution, steps_number = match choose_parents with | None -> GA.find population | Some choose_parents -> GA.find ~choose_parents population in printf “%s — Solved by in %d steps.
    ” (GA.to_string solution) name steps_number ); printf ”
    “; )

    0 4 1 5 2 7 1 1 –> evaluate = 23
    7 7 7 6 6 0 2 2 –> evaluate = 18
    7 2 2 1 7 2 0 4 –> evaluate = 20
    6 3 5 6 3 2 0 0 –> evaluate = 17 Init by: 1
    7 1 4 2 0 6 3 5 — Solved by in 36126 steps.
    5 3 6 0 7 1 4 2 — Solved by in 1180 steps.
    2 4 1 7 5 3 6 0 — Solved by in 505 steps. Init by: 10
    6 4 2 0 5 7 1 3 — Solved by in 48993 steps.
    1 4 6 0 2 7 5 3 — Solved by in 57 steps.
    0 4 7 5 2 6 1 3 — Solved by in 199 steps. Init by: 100
    4 0 7 3 1 6 2 5 — Solved by in 27041 steps.
    4 7 3 0 2 5 1 6 — Solved by in 527 steps.
    0 4 7 5 2 6 1 3 — Solved by in 185 steps. Init by: 42
    2 5 3 0 7 4 6 1 — Solved by in 2339 steps.
    3 5 7 1 6 0 2 4 — Solved by in 2834 steps.
    4 6 0 3 1 7 5 2 — Solved by in 1353 steps.

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

    Ну и ссылка на сам репозиторий – ocaml-genetic-algorithm

    Параллельное программирование для многоядерных процессоров Курс лекций Май 2009 Содержание

    Генетический алгоритм для задачи о n ферзях

    Задача расстановки ферзей на шахматной доске (N-Queens)

    Хорошо известной задачей в учебниках по элементарному программированию, структурам данных и алгоритмам, является задача о расстановке на шахматной доске восьми ферзей таким образом, чтобы ни один из них не находился под боем какого-либо другого из ферзей. То, что эта задача имеет решение, было продемонстрировано Карлом Фридрихом Гауссом и Францем Науком в 1850 году. На самом деле, имеется 92 различных способа расставить указанным образом ферзей на обычной шахматной доске.

    Вычисление количества решений и всех их перечисление для данной задачи является одной из базовых проблем компьютерного программирования. Задача о 8 ферзях естественным образом обобщается до задачи об N ферзях, когда задается число N – размер шахматной доски, и требуется найти все способы расстановки N ферзей на этой доске, чтобы они попарно не атаковали друг друга.

    Для решения этой задачи предлагались различные методы – некоторые из них можно найти в известной книге Н. Вирта “Алгоритмы + Структуры Данных = Программы”. Далее будут рассмотрены теоретические основы и реализация эффективного алгоритма решения задачи N ферзей (N-Queens), эффективность которого достигается

  • во-первых, представлением текущих расстановок ферзей на шахматной доске в виде битовых векторов и, соответственно, использованием только битовых операций,

  • во-вторых, распараллеливанием алгоритма, использующего битовые векторы.

  • Типичные методы решения.

    Далее, при объяснении методов решения, будет использоваться пример с 8 ферзями (т.е., доской 8 x 8).

    Прямая проверка. Предположим, что ферзь находится на i-ой горизонтали (строке) и на j-ой вертикали (столбце), т.е., на клетке (i,j).

    Тогда, клетки, которые находятся под боем данного ферзя, включают в себя: все клетки i-ой строки и все клетки j-го столбца, а также все клетки (k,l), где k –l = i – j, или k + l = i + j.

    Последние две группы клеток располагаются на двух диагоналях, которые находятся под боем ферзя, расположенного в клетке (i,j).

    Если на доске уже расположены безопасным образом несколько ферзей и их число меньше, чем 8, то поиск позиции для очередного ферзя сводится к проверке пустых клеток и проверке для них вышеупомянутых условий относительно каждого из ферзей, уже находящихся на доске. Если ни одна из таких клеток не подходит, то мы должны снять с доски последнего из поставленных ферзей и попробовать для него другие возможности.

    Обратите внимание

    Эта процедура может быть представлена алгоритмически в виде последовательности проверок, при которых вначале делается попытка выставить ферзя в первой строке, затем второго ферзя – во второй строке, и т.д. Если для очередного ферзя в i-ой строке безопасная позиция отсутствует, то необходима процедура бектрекинга.

    Метод на основе контрольных массивов. Недостатком метода прямых проверок являются повторные вычисления проверок для каждого из ферзей, находящихся на доске. Эти повторные вычисления могут быть устранены.

    В усовершенствованном методе используются три массива column, left и right для хранения информации о текущей конфигурации ферзей, которые состоят из 8, 15 и 15 элементов соответственно (так как 15 = 8 + ( 8 – 1 ) при N = 8 ).

    Пусть column[i] равно 1, если имеется ферзь в i-ом столбце доски, и 0 – в противном случае.

    Если ферзь находится в позиции (i,j), то left [ i + j ] и right [ 7 – j + i ] будут равны 1, в противном случае – 0 (как обычно, мы предполагаем, что нумерация элементов массива начинается с 0).

    Имея такие массивы, проверка очередной клетки на возможность размещения в ней очередного ферзя, становится прямой и эффективной. Для проверки позиции (i’,j’), нам необходимо только проверить элементы column[i’], left[i’+j’] и right[7-j’+i’].

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

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

    В следующем разделе приводится решение, которое для работы с битовыми векторами использует только битовые операции. Сам алгоритм представляет собой универсальную процедуру поиска с бектрекингом, состоящую в последовательных попытках расставить ферзи, начиная с 1-го ряда и заканчивая последним.

    Метод решения на основе битовых векторов.

    Предположим, что b1является битовым вектором для первого ряда доски, и j-й бит в b1 содержит 1, представляющую размещенного в этой позиции ферзя.

    Важно

    Тогда, (j-1)-ая позиция во втором ряду атакуется (контролируется) данным ферзем, и соответствующая отметка в битовом векторе может быть получена сдвигом вектора b1на один бит влево.

    Аналогичным образом, (j+1)-ая позиция во втором ряду, которая также контролируется данным ферзем, определяется сдвигом вправо вектора b1на один бит.

    Тогда, все контролируемые позиции во втором ряду представляются следующим битовым вектором (мы используем > как обозначения операций сдвига влево и вправо, символ | обозначает побитовое ИЛИ, 1 используется для обозначения занятой или контролируемой позиции, а 0 – для свободных позиций):

    b1 | ( b1> да, все контролируемые позиции во втором ряду представляются следующим битовым вектором (мы используем х попытках расставить > 1)

    Также легко найти позиции, контролируемые первым ферзем в третьей строке: достаточно сдвинуть вектор b1влево или вправо еще на один бит. Т.е.:

    b1 | ( b1> да, все контролируемые позиции во втором ряду представляются следующим битовым вектором (мы используем х попытках расставить > 2)

    В общем случае, позиции, контролируемые первым ферзем в k-ой строке, могут быть определены путем сдвига вектора b1на k – 1 битов влево и вправо и выполнением побитовой операции ИЛИ над этими тремя векторами.

    Ферзь в первой строке контролирует в каждой строке ниже самое большее три позиции. Отметим также, что при сдвиге биты, содержащие 1, могут выходить за пределы векторов, размер которых совпадает с размером доски.

    Пусть Bi[k] обозначает вектор, представляющий контролируемые позиции в строке k ферзем, находящимся в строке i ( k > i ). Тогда, очевидно, имеем:

    Bi[k] = bi| ( bi> да, все контролируемые позиции во втором ряду представляются следующим битовым вектором (мы используем х попытках расставить > ( ki ) )

    Существуют различные способы представления задачи о расстановке ферзей на доске 8 х 8 с помощью битовых векторов. Например, прямой подход состоит в том, чтобы использовать 8 векторов, представляющих занятые и свободные клетки, по одному для каждой строки. В таких векторах, только один бит отличается от битов в других векторах, представляющий позицию ферзя в данной строке.

    Совет

    Однако, существует естественный способ объединить все эти управляющие векторы в три рабочих вектора, которые будут называться left, down и right, соответственно.

    Вектор down представляет столбцы, которые на текущий момент контролируются уже выставленными ферзями. Когда новый ферзь ставится на доску, соответствующий бит вектора down принимает значение 1.

    Вектор left представляет контролируемые выставленными ферзями позиции влево от них по диагонали. На каждом шаге, при переходе к следующей строке вектор left сдвигается на один бит влево.

    Когда новый ферзь ставится на доску, в векторе left соответствующий бит должен получить значение 1.

    Вектор right играет ту же самую роль, что и вектор left, но только для направления вправо по диагонали.

    Такое представление контролируемых позиций достаточно хорошо вписывается в общую процедуру поиска с использованием бектрекинга. Выполнение поиска начинается с первой строки при значениях всех векторов равных нулю. В каждой строке, контролируемые позиции определяются выражением

    B = left | down | right

    На каждом шаге, новый ферзь добавляется в некоторую позицию, для которой бит в векторе B равен 0, и все три рабочих вектора модифицируются в соответствующем бите. После этого, происходит переход к следующему шагу, при котором векторы left и right сдвигаются на 1 бит влево и вправо, соответственно. Тем самым, для каждой строки поддерживается инвариант

    контролируемые позиции = left | down | right,

    который гарантирует корректность процедуры.

    Описанный процесс поиска с бектрекингом легко реализовать в виде (последовательной) рекурсивной процедуры на языке C#:

    using System;public class NQueens {public static int N, MASK, COUNT;public static void Backtrack(int y, int left, int down, int right){int bitmap, bit;if (y == N) {COUNT++;} else {bitmap = MASK & ~(left | down | right);while (bitmap != 0) {bit = -bitmap & bitmap;bitmap ^= bit;Backtrack(y+1, (left | bit)1);}}}public static void Main(String[] args ){N = 10; /*

    Задача о расстановке ферзей. Перебор с возвратом

    Генетический алгоритм для задачи о n ферзях

    Задача о расстановке ферзей.

    Небольшая подсказка к решению задачи о расстановке 8 ферзей.

    Суть задачи. Необходимо было найти такие расстановки восьми ферзей на обычной шахматной доске, чтобы они не били друг друга.

    Стоит сразу заметить, что перебирать все возможные варианты расстановок мы не в состоянии.  Точнее можно конечно написать такую программу, но мы поступим иначе, более оптимально.

    Некоторые замечания о способе хранения расстановки.

    Давайте прикинем, как мы будем хранить расположение ферзей на доске. Очевидным решением было бы завести массив 8Х8 и записывать в него единицу или нуль, в зависимости от того занята ли клетка ферзем или нет.

    Но давайте подумаем, так ли нам нужна вся доска? Оказывается, что нет. Вспоминаем, как ходит ферзь.  На любое количество клеток по вертикали, горизонтали или диагонали. Очевидно, что если на какой-то вертикали имеется ферзь, то поставить на эту вертикаль еще одно ферзя никак не получится, т.к. они будут бить друг друга.  

    Обратите внимание

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

    О проверке, находится ли поле «под боем» или нет.

    Опишем математически, какие клетки шахматной доски находятся «под боем» ферзя,  установленного в клетке [i][j].

    Посмотрите на следующий рисунок.

     

    Пусть [i][j] – позиция ферзя, а [k][m] – координаты проверяемой клетки. 

    k=I – горизонталь,

    m=j – вертикаль,

    k+m =i+j – восходящая диагональ,

    km= ij – нисходящая диагональ.

    Эти условия легко переделать под наш способ хранения расстановки ферзей.

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

    Понятно, что нужно последовательно обработать каждую из предыдущих элементов. Пусть мы хотим поставить ферзя на позицию k.

    Начинаем проверку, с первого элемента, в нём у нас записано значение восемь. Следовательно, k не должно равняться восьми, иначе оба ферзя окажутся на одной горизонтали.

    Кроме того, k+4 != 8+1 (условие зеленой линии), иначе мы пытаемся поставить ферзя на занятую диагональ. И наконец, k-4 != 8-1 (условие синей линии), иначе мы снова попадаем на диагональ, которая бьётся другим ферзем.

    Проверку условия красной линии осуществлять не нужно, так как способ представления расстановок в памяти не позволит на одну горизонталь поставить двух ферзей.

    Важно

    Аналогичные проверки необходимо будем произвести для всех ферзей, которые к этому моменту уже установлены на доске. Логично будет выделить эти проверки в функцию, которая принимает два аргумента – строку и столбик клетки, в которую мы хотим установить ферзя.

    Основной алгоритм решения. Перебор с возвратом.

    Теперь обсудим основной алгоритм реализующий расстановку ферзей. Действовать будем так, как мы действовали бы, если у нас была бы реальная доска перед глазами. 

     

    Поставим первого ферзя в первую клетку первой вертикали. Соответственно в первый элемент нашего массива сохраним единичку. Хорошо, первый ферзь установлен. Самое время попытаться установить второго ферзя.

    Он должен стоять на второй горизонтали.

    Поставим его в первую клетку второй вертикали. Вызов функцию проверки, даст отрицательный результат на первом же условии, так как это строка бьется ранее установленным ферзем.

    Проверим вторую клетку, второй вертикали. Результат проверки неудовлетворительный, это поле тоже бьется ранее установленным ферзем.

    Теперь проверим третью клетку второй вертикали, может быть она нам подойдет? Действительно подходит. Устанавливаем туда ферзя.    Переходим к установке третьего ферзя на третью вертикаль. 

    Проверку начинаем осуществлять с 1 клетки третей вертикали.

    Думаю уже очевидно, что ни первая, ни вторая, ни третья, ни даже четвертая клетки нам не подойдут, так как они бьются ранее установленными ферзями.  А вот пятая клетка, окажется в самый раз, так как её ни первый, ни второй ферзи не бьют. Значит, устанавливаем туда нашего третьего ферзя.

    Аналогичным способом заполняем четвертую, пятую, шестую и седьмую вертикали.  Пока что это всё можно реализовать стандартным перебором в два цикла. Внешний цикл двигается по вертикалям от 1 до 8, а внутренний по горизонталям.

    Отдельно рассмотрим установку ферзя на последней вертикали.

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

    Совет

    Что же делать? Нужно вернуться на шаг назад и попытаться установить седьмого ферзя в другое место. 

    Это операция называется возврат.

    Нет необходимости, снова проверять для седьмого ферзя клетки с 1 по 6, так как они уже были проверены ранее, и первые шесть ферзей остались на своих местах.

    Проверив седьмую и восьмую клетки, убеждаемся, что установить в них седьмого ферзя не получится, а поэтому снова делаем возврат, и теперь уже пробуем поставить на другое место шестого ферзя. 

     Будем проверять лишь клетки с 5 по 8.

    Нетрудно убедиться, что ни одна из них не подходит. А значит, выполняем еще один возврат и пытаемся установить пятого ферзя на новое место.

    Проверку, как вы уже наверное догадались будем начинать с третьей клетки пятой вертикали. Она нам не подойдет, так как находится под боем, причем от двух ферзей сразу, от второго и третьего. А вот четвертая клетка свободна, и поэтому в неё и будем ставить нашего ферзя.

    Продолжая в таком духе (чередуя установки с возвратами), рано или поздно мы наткнемся на такую расстановку ферзей, которая удовлетворяет всем нашим требованиям.

    Другими словами на доске будет размещено 8 ферзей, которые не будут бить друг друга. Наткнувшись на такую расстановку, мы сохраним её в отдельный массив, или же сразу можем вывести на экран.

    После чего, нам необходимо будет продолжить выполнение перебора.

    Такая вот огромная подсказка. Используя полученные знания, попытайтесь теперь написать соответствующую программу.

    Решение задачи о 8 ферзях (стр. 1 из 2)

    Генетический алгоритм для задачи о n ферзях

    КУРСОВАЯ РАБОТА

    Тема:

    «Решение задачи о 8 ферзях»

    Харьков 2007

    Цель работы: разработать программу, которая бы наглядно продемонстрировала варианты размещения ферзей на шахматной доске, удовлетворяя правилам задачи.

    Метод исследования: изучение литературы, составление и отладка программ на компьютере, проверка решений.

    Программа размещения ферзей на практике может применяться в в образовательных целях. Также ее можно использовать для изучения математической модели поставленной задачи. Ведь задача особенно интересна, при увеличении размера шахматной доски.

    Задача звучит следующим образом:

    «Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?»

    Задача о восьми ферзях

    Обратите внимание

    Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко (на рисунке представлены четыре искомые расстановки). Значительно труднее подсчитать общее число расстановок и вывести их, в чем, собственно, и состоит задача.

    Любопытно, что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Доктор Ф. Наук нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г.

    Лишь после этого Гаусс заинтересовался задачей и нашел 72 решения, которые он сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук. Он привел их в упомянутой газете от 21 сентября 1850 г.

    Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.

    Строгое доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Забегая вперед, отметим, что существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.

    Известно много способов организовать эффективный поиск расположения восьми мирных ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.).

    Эти способы описаны в многочисленной литературе по занимательной математике. В наш век ЭВМ задача такого сорта не вызвала бы столь живой интерес.

    Ведь достаточно составить несложную программу, и уже через несколько минут после ее введения в машину все 92 необходимые позиции будут выданы на печать.

    Важно

    Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам. Например, из расстановки, показанной на рис.

    а, при повороте доски на 90° по часовой стрелке мы получаем расстановку на рис. в, а при отражении доски относительно линии, разделяющей королевский и ферзевый фланги, – на рис. г.

    При помощи других поворотов и отражений доски можно получить еще пять решений.

    Итак, указанные операции с шахматной доской позволяют из одного расположения мирных ферзей получить, вообще говоря, семь новых. Доказано, что в общем случае на доске nхn (при n > 1) для любой расстановки n мирных ферзей возможны три ситуации:

    1) при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается;

    2) новое решение возникает при повороте доски на 90°, а ее отражения дают еще две расстановки;

    3) три поворота доски и четыре отражения приводят к семи различным расстановкам (а если считать и исходную, то всего имеем восемь позиций).

    В случае 1) исходное решение называется дважды симметрическим, в случае 2) – симметрическим, а в случае 3) – простым. Для обычной доски каждое решение является либо простым, либо симметрическим, а дважды симметрических не существует.

    Набор расстановок восьми мирных ферзей называется основным, если, во-первых, эти расстановки не переходят друг в друга при поворотах и отражениях доски, и, во-вторых, любая другая расстановка получается из какой-нибудь основной при помощи данных преобразований доски. Доказано, что всякий основной набор решений задачи содержит ровно 12 расстановок. Вот один из таких наборов:

    1) см. рис. а;

    2) см. рис. б;

    3) a4, b1, c5, d8, e6, f3, g7, h2;

    4) a4, b2, c5, d8, e6, f1, g3, h7;

    5) a4, b2, c7, d3, e6, f8, g1, h5;

    6) a4, b2, c7, d3, e6, f8, g5, h1;

    7) a3, b5, c2, d8, e6, f4, g7, h1;

    8) a4, b1, c5, d8, e2, f7, g3, h6;

    9) a4, b7, c3, d8, e2, f5, g1, h6;

    10) a6, b4, c2, d8, e5, f7, g1, h3;

    11) a4, b8, c1, d5, e7, f2, g6, h3;

    12) a4, b2, c7, d5, e1, f8, g6, h3.

    Совет

    Остальные 80 расстановок получаются из этих двенадцати при помощи поворотов и отражений доски. Основная расстановка на рис. б является симметрической, другие одиннадцать основных расстановок – простыми. Итак, всего на доске имеем 11·8+1·4=92 расстановки восьми ферзей, не угрожающих друг другу.

    Отметим несколько интересных свойств расстановок мирных ферзей. Симметрическая расстановка на рис. б как ей и положено, обладает внешней симметрией. Она характеризуется также тем, что центральная часть доски (квадрат 4х4) не занята ферзями.

    Свободны здесь и обе главные диагонали доски (этим свойством обладает и восьмая основная расстановка). В первой расстановке (рис.

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

    Всякое решение задачи о восьми ферзях можно записать как набор (t1, t2, ј, t8), представляющий собой перестановку чисел 1, 2, ј, 8. Здесь ti – номер горизонтали, на которой стоит ферзь i-й вертикали. Так как ферзи не стоят на одной горизонтали, то все числа ti различны, а поскольку ферзи не стоят и на одной диагонали, то для любых i, j (i < j Ј 8) имеем: |tj-ti| № j-i.

    Запишем числа 1, 2, ј, 8 сначала по возрастанию, а затем по убыванию. После этого сложим числа каждой из этих двух перестановок с числами произвольной перестановки восьми чисел, например такой – (3, 7, 2, 8, 5, 1, 4, 6): 1, 2, 3, 4, 5, 6, 7, 8

    + 3, 7, 2, 8, 5, 1, 4, 6

    4,9, 8, 7, 6, 5, 4, 3, 2, 1

    + 3, 7, 2, 8, 5, 1, 4, 6

    11,14,8,13,9,4, 6, 7.

    Полученные суммы образуют два набора: (4, 9, 5, 12, 10, 7, 11, 14) и (11, 14, 8, 13, 9, 4, 6, 7). Рассмотрим следующую задачу.

    Какие перестановки чисел от 1 до 8 дают в результате указанной операции сложения два таких набора, в каждом из которых все элементы различны?

    Обратите внимание

    Задача о восьми ферзях привлекла внимание Гаусса именно в связи с этой чисто арифметической задачей. Оказывается, между решениями этих двух задач существует взаимно однозначное соответствие.

    Другими словами, каждая расстановка восьми ферзей, не угрожающих друг другу, дает решение арифметической задачи, и наоборот.

    Для выбранной перестановки оба набора состоят из различных чисел, и это не случайно – она соответствует первой основной расстановке (см. рис. а).

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

    Задача об n ферзях. На шахматной доске nхn расставить n ферзей так, чтобы они не угрожали друг другу.

    На доске 1х1 один ферзь ставится на одно-единственное поле, и решение существует. На доске 2х2 один ферзь, где бы ни стоял, нападает на три других поля, и второго ферзя поставить некуда.

    На доске 3х3 умещаются только два мирных ферзя. Итак, для досок 2х2 и 3х3 задача не имеет решения. Эти два случая представляют собой исключение.

    Для всех n > 3 на доске nхn можно расставить n не угрожающих друг другу ферзей.

    На доске 4ґ4 существует одна основная расстановка, причем дважды симметрическая: a2, b4, c1, d3, т.е. всего имеется два решения. На доске 5ґ5 основных расстановок две: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4. Общее число расстановок равно десяти, причем из них можно выбрать пять таких, при наложении которых друг на друга 25 ферзей заполняют все поля доски 5х5.

    Важно

    Заметим, что в общем случае n расстановок (решений задачи) могут заполнить при наложении всю доску nхn только при тех n, которые не кратны двум и трем. Из этого, в частности, следует, что для обычной доски подобрать восемь расстановок, накрывающих все 64 поля доски, невозможно.

    Обобщая алгебраическое свойство решений задачи о восьми ферзях, получаем, что расстановка n ферзей (t1, t2, ј, tn) на доске nґn является искомой, если для любых i, j (i < j Ј n) имеет место: |tj-ti| № j-i.

    Таким образом, задача об n ферзях сводится к чисто математической задаче о нахождении перестановки чисел 1, 2, ј, n, удовлетворяющей указанному условию. Известно много решений этой задачи, некоторые из них опубликованы в серьезных математических журналах.

    Один из методов расстановки n ферзей, не угрожающих друг другу на произвольной доске nґn (n і 5), можно найти в книге «Математика на шахматной доске».

    Описание алгоритма и структуры программы:

    В данной программе реализован рекурсивный метод решения задачи о 8 ферзях.

    У нас имеется функция (int put_queen (int x)), которая ставит очередного ферзя на поле и вызывает саму себя для, того чтобы поставить следующего, если очередного ферзя поставить нельзя, то она возвращает управление в функцию, из которой была вызвана, а та в свою очередь пробует поставить своего ферзя в другое место, и опять рекурсивно вызвать себя. Когда функция ставит последнего ферзя, то результат расстановки выводится пользователю.

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

    Для сохранения положения ферзей используется массив из 8 элементов целочисленного типа (int queens[8]). Порядок элемента в этом массиве означает номер ферзя и его x’овую координату, то есть столбец, а его значение – y’овую координату, или строку. Мы используем то свойство, что на одном столбце не могут находиться несколько ферзей.

    Оцените статью
    Просто о технологиях
    Добавить комментарии

    ;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: